On 7/24/20 10:08 AM, jmh530 wrote:
> I can't speak to why people don't use them in D, but it is hard to compare to C++ where it is already part of the standard library.

There's a lot more development beyond that (in which I may take a part, too): http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2035r0.pdf

It seems there's a strong recognition within a part of the C++ community that memory allocation is an essential part of fast scalable application. Consequently, there's strong incentive to push for better allocator integration within the language.

On Friday, 24 July 2020 at 14:06:28 UTC, Andrei Alexandrescu wrote:
>
> We need to template all we can of druntime. All those silly C-style functions decaying to void* and dependencies and runtime type information must go.

Reliance on runtime type information for object creation is not good, I agree. But that is easily solved by having the compiler make a call to the ctor (instead of implementing that call in druntime). Another option is to templatize, as you wrote.

I don't agree that everything should be moved to templates in druntime, but I cannot formulate a strong argument against it (I also have not seen strong arguments in favor of it though). Because "careful consideration" is not a strong point of D development, I am wary.

Templatizing will make certain types of functionality _harder_. If a library/program wants to break, or hook into, object creation inside user code, it will be impossible with templatized functions (you cannot predict the templated function names of code that has not yet been written). For example, AddressSanitizer can only work with non-templatized allocation functions. If malloc was a template, it would be _much_ harder to implement AddressSanitizer support (and currently not possible while keeping source location in error messages).

In favor of compiler-implemented code (instead of druntime) is that the compiler is able to add debug information to generated code, linking the instructions to source location in user code. I think this will only be possible for druntime-implemented when: a) the code is force-inlined and b) there is a way to disable debug information tagging of the instructions inside the druntime-implemented function (such that the source-location stays the same as the user's code). (a) is already available in our compilers, (b) is not yet.

Template bloat is a standard concern, because we do not have any defense against it. Did anyone ever look into the array comparison case with template bloat? Force-inlining _and_ not emitting into binary (currently not available to user/druntime code) would fix that, although then maybe someone else starts to argue about instruction count increase...

-Johan

On Fri, Jul 24, 2020 at 05:14:47PM +0000, Johan via Digitalmars-d wrote:
> On Friday, 24 July 2020 at 14:06:28 UTC, Andrei Alexandrescu wrote:
> > We need to template all we can of druntime. All those silly C-style functions decaying to void* and dependencies and runtime type information must go.
[...]
> I don't agree that everything should be moved to templates in druntime, but I cannot formulate a strong argument against it (I also have not seen strong arguments in favor of it though). Because "careful consideration" is not a strong point of D development, I am wary.

I think, as with all things in language development, there's a trade-off. Templates are not a silver bullet. For example, the string-switch fiasco that somebody referred to. Ultimately, IIRC, that was worked around by rewriting std.datetime to refactor away that giant 1000+ (or was it 5000+) case switch statement -- but that did not fix the real problem, which is that when you have a very large number of template arguments, it just introduces a lot of problems, both in the compiler (performance, size of generated symbols, etc) and in the binary (ridiculous size of symbols, template bloat).

Template bloat is also a cause of concern: if your program had arrays of 100 distinct types, but they are all PODs and therefore comparison could be done with memcmp()'s, then it makes little sense for the compiler to instantiate the array comparison template 100 times and emit 100 copies of code that ultimately is semantically identical to memcmp. Ditto for any other array operation that you have have.  Force-inlining only helps to a certain extent -- as Johan said, you merely end up with instruction count bloat in lieu of template function bloat. At some point, the cost of having an overly-large executable will start to outweigh the (small!) performance hit of replacing instruction count bloat with a function call to memcmp, for example.

Another problem is error messages, as someone else has already pointed out.  Although we have seen improvements in template-related error messages, they are still very user-unfriendly, often coming in the form of indirect messages like "this call does not match any of the following 25 overloads", and the user has to sift through pages upon pages of indecipherably-long template symbols and somehow deduce that what the compiler *really* want to say was "you have a typo on line 123".

I think part of the solution is to adopt Stefan's proposed type functions instead of shoe-horning everything into templates. Just because templates are Turing-complete does not necessarily mean they are practical for implementing every computation. A lot of the druntime templates / prospective druntime templates could possibly be implemented as type functions rather than template functions.


T

-- 
Error: Keyboard not attached. Press F1 to continue. -- Yoon Ha Lee, CONLANG

On 7/24/20 1:14 PM, Johan wrote:
> On Friday, 24 July 2020 at 14:06:28 UTC, Andrei Alexandrescu wrote:
>>
>> We need to template all we can of druntime. All those silly C-style functions decaying to void* and dependencies and runtime type information must go.
> 
> Reliance on runtime type information for object creation is not good, I agree. But that is easily solved by having the compiler make a call to the ctor (instead of implementing that call in druntime). Another option is to templatize, as you wrote.

Thanks for answering! I was deliberately exaggerating for dramatic purposes, so it's great to see such an even-keeled analytical response.

> I don't agree that everything should be moved to templates in druntime, but I cannot formulate a strong argument against it (I also have not seen strong arguments in favor of it though). Because "careful consideration" is not a strong point of D development, I am wary.
> 
> Templatizing will make certain types of functionality _harder_. If a library/program wants to break, or hook into, object creation inside user code, it will be impossible with templatized functions (you cannot predict the templated function names of code that has not yet been written). For example, AddressSanitizer can only work with non-templatized allocation functions. If malloc was a template, it would be _much_ harder to implement AddressSanitizer support (and currently not possible while keeping source location in error messages).

I think there's a simple pro-template argument that I've run into often in my C++ projects: template to non-template is a one-way street because from static type information to non-static type information is a one-way street. You can go from a templated approach to a non-templated approach as easy as a one-liner. You can go from static composition to dynamic. You can do type erasure but not type "reconstruction". Going the other way is much more difficult for obvious reasons.

That's why deferring the decision to lose type information is often a good stance for a designer; it offers maximum flexibility because you can easily revisit and override it.

(This argument pattern goes for other things, too: making a fast subsystem safe vs. the converse comes to mind.)

Applied to druntime, if using runtime functions is desirable, the templates can just forward to them. So once we decide to use templates for fundamental runtime support, changing our mind selectively is trivial. Going the opposite way (which is what we're doing now) is a difficult path with compiler changes and all.

> In favor of compiler-implemented code (instead of druntime) is that the compiler is able to add debug information to generated code, linking the instructions to source location in user code. I think this will only be possible for druntime-implemented when: a) the code is force-inlined and b) there is a way to disable debug information tagging of the instructions inside the druntime-implemented function (such that the source-location stays the same as the user's code). (a) is already available in our compilers, (b) is not yet.
> 
> Template bloat is a standard concern, because we do not have any defense against it. Did anyone ever look into the array comparison case with template bloat? Force-inlining _and_ not emitting into binary (currently not available to user/druntime code) would fix that, although then maybe someone else starts to argue about instruction count increase...

I'm tuned to some of the C++ standardization mailing lists. Template bloat has come into discussion about every template-related feature addition since 1990. Occasionally with numbers. Over time these arguments died out: the ease of opting out of templates where appropriate and the many tactical improvements made by compiler writers have simply sent that argument to the dustbin of history. All C++ features of any consequence since decades are imbued with genericity.

It has been undeniable that going templated all the way has worked wonders for C++. We'd do good to learn from that.

On 7/24/20 2:07 PM, H. S. Teoh wrote:
> For example, the
> string-switch fiasco that somebody referred to.

What fiasco?

On 7/24/20 2:07 PM, H. S. Teoh wrote:
> Template bloat is also a cause of concern: if your program had arrays of
> 100 distinct types, but they are all PODs and therefore comparison could
> be done with memcmp()'s, then it makes little sense for the compiler to
> instantiate the array comparison template 100 times and emit 100 copies
> of code that ultimately is semantically identical to memcmp.

We do exactly what you describe would be desirable. All comparisons of arrays of scalars boil down to a small code:

https://github.com/dlang/druntime/blob/master/src/core/internal/array/comparison.d#L50

See generated code:

https://godbolt.org/z/4hjWxq

(dmd does not inline that, hopefully it will in the next release. Does not dilute my argument.)

> Ditto for
> any other array operation that you have have.  Force-inlining only helps
> to a certain extent -- as Johan said, you merely end up with instruction
> count bloat in lieu of template function bloat. At some point, the cost
> of having an overly-large executable will start to outweigh the (small!)
> performance hit of replacing instruction count bloat with a function
> call to memcmp, for example.

As I said, with templates you have precise control over merging implementations, inlining vs. not, certain optimizations etc. Without templates - you don't. It's as simple as that. To paraphrase Steven Wright, going non-templates is a one-way dead-end street.

> Another problem is error messages, as someone else has already pointed
> out.  Although we have seen improvements in template-related error
> messages, they are still very user-unfriendly, often coming in the form
> of indirect messages like "this call does not match any of the following
> 25 overloads", and the user has to sift through pages upon pages of
> indecipherably-long template symbols and somehow deduce that what the
> compiler *really* want to say was "you have a typo on line 123".

There is great opportunity to improve compilers, some of which has been reaped, and much of which is still waiting.

> I think part of the solution is to adopt Stefan's proposed type
> functions instead of shoe-horning everything into templates. Just
> because templates are Turing-complete does not necessarily mean they are
> practical for implementing every computation. A lot of the druntime
> templates / prospective druntime templates could possibly be implemented
> as type functions rather than template functions.

That'd be interesting. In the meantime, there's so much to do with the current template offering it hurts.

On Friday, 24 July 2020 at 18:07:21 UTC, H. S. Teoh wrote:
>
> Another problem is error messages, as someone else has already pointed out.  Although we have seen improvements in template-related error messages, they are still very user-unfriendly, often coming in the form of indirect messages like "this call does not match any of the following 25 overloads", and the user has to sift through pages upon pages of indecipherably-long template symbols and somehow deduce that what the compiler *really* want to say was "you have a typo on line 123".

This we can easily test. What would it look like if there is an error in a user class constructor when it is called by a druntime function versus currently?

-Johan

On Thursday, 23 July 2020 at 00:47:21 UTC, Andrei Alexandrescu wrote:
> One problem I noticed with the current instrumentation of allocations is that it is extremely slow.

Programs compiled with -profile=gc are much faster with this change: https://github.com/dlang/druntime/pull/3164

The problem was, that GC.stats was called for every allocation, but GC.stats does more than necessary for -profile=gc.

Unfortunately this change breaks the ABI of druntime.

On Friday, 24 July 2020 at 18:45:39 UTC, Andrei Alexandrescu wrote:
> On 7/24/20 2:07 PM, H. S. Teoh wrote:
>
>> I think part of the solution is to adopt Stefan's proposed type
>> functions instead of shoe-horning everything into templates. Just
>> because templates are Turing-complete does not necessarily mean they are
>> practical for implementing every computation. A lot of the druntime
>> templates / prospective druntime templates could possibly be implemented
>> as type functions rather than template functions.
>
> That'd be interesting. In the meantime, there's so much to do with the current template offering it hurts.

You (and everyone else) are very welcome to help with the type functions.