I'm not sure what the status is on this, I remember Walter saying in a conference (DConf 2014 I think) that he had an idea to remove duplicate template instantiations by comparing their generated code but I had another idea I thought I'd share.

I'm calling the idea "CombinationTypes".  Sort of a "compile-time" concept that allows code to use multiple types that would produce the same binary code but retains type information.  The first combination type I would introduce is the "any*" or "any[]" types. For example, you could write the following function:

any* limitPtr(any[] array) {
  return any.ptr + any.length;
}

The advantage of using a combination type like "any" over say "void" is the compiler knows what you are trying to do and won't require you to perform any awkward casting.  The following code should work fine:

char[] mychars;
string mystring;

auto mycharsLimit = mychars.limitPtr; // mycharsLimit is a char*
auto mystringLimit = mystring.limitPtr; // mystringLimit is a immutable(char)*

The generated code for this function will be identical no matter what the element type is.  The problem with using a template is that different instances of this function could be generated (binary code instances) that are identical.  This will probably be compiler dependent but it would be nice if the programmer could guarantee only one instance of the function gets generated if that's the effect they want to achieve.

Furthermore, a CombinationType is much more limiting than a template which creates less work for the compiler.  The compiler will only need to compile the function once and won't need to compare the generated binary code of each instance to remove duplicates.

Another combination type that would be useful is an "anybyte" type.  This would handle both byte and char types (really any type that uses 1 byte of memory).  I'm sure many of the standard library functions would find this type useful.

I was looking through some of the functions in std.stdio to see which ones could benefit from this and I realized that a useful extension to this would be to have a "sizeof" property on the "any" combination type.  You obviously could not access "any.sizeof" on a function argument inside the function, but the caller of the function could, so you could use "any.sizeof" as a default initializer.  With this functionality you could make std.stdio rawRead/rawWrite functions non-template like this:
  Current: T[] rawRead(T)(T[] buffer);
  New    : size_t rawRead(any[] buffer, size_t elementSize = any.sizeof);

  Current: void rawWrite(T)(in T[] buffer);
  New    : void rawWrite(any[] buffer, size_t elementSize = any.sizeof);

This would add an extra runtime argument to the functions vs having multiple instances each with it's own element size passed to fread/fwrite so you'd be trading off an extra function parameter for only one instance of the function.  So this may or may not be the best solution. However I think most of the time this will be called with 1-byte-element arrays so you could have 2 instances of it, one with the "anybyte" type and one with the "any" type.  I could see a good argument for that solution.

One last comment, when you do have a template function it would be nice if the compiler could guarantee that it would use combination types when it could.  For example, if the original function limitPtr was written using a template, the compiler could see that the array is never dereferenced so it knows that it can use an "any*/any[]" type for the template type so it only needs to generate one instance of it.

There's probably more useful combination types I haven't thought of but I'll bring this initial idea to and end and see if anyone else has anything to say.

On Thursday, 30 October 2014 at 12:51:50 UTC, Jonathan Marler wrote:
> I'm not sure what the status is on this, I remember Walter saying in a conference (DConf 2014 I think) that he had an idea to remove duplicate template instantiations by comparing their generated code but I had another idea I thought I'd share.
>
> I'm calling the idea "CombinationTypes".  Sort of a "compile-time" concept that allows code to use multiple types that would produce the same binary code but retains type information.  The first combination type I would introduce is the "any*" or "any[]" types. For example, you could write the following function:
>
> any* limitPtr(any[] array) {
>   return any.ptr + any.length;
> }

This is basically type erasure. It works well reasonably well as long as only references are allowed. But it seems you want to allow value types, too.

>
> The advantage of using a combination type like "any" over say "void" is the compiler knows what you are trying to do and won't require you to perform any awkward casting.  The following code should work fine:
>
> char[] mychars;
> string mystring;
>
> auto mycharsLimit = mychars.limitPtr; // mycharsLimit is a char*
> auto mystringLimit = mystring.limitPtr; // mystringLimit is a immutable(char)*
>
> The generated code for this function will be identical no matter what the element type is.

Unfortunately not, only if it's an array of byte-sized elements. If you pass a `wchar[]`, the calculation needs to be <pointer + 2*length> instead of <pointer + length>.

It gets more involved if you want to allow copying and assigning, because the types can have non-default `this()`, `this(this)`, `~this()`, `opAssign()`, and so on.

> The problem with using a template is that different instances of this function could be generated (binary code instances) that are identical.  This will probably be compiler dependent but it would be nice if the programmer could guarantee only one instance of the function gets generated if that's the effect they want to achieve.
>
> Furthermore, a CombinationType is much more limiting than a template which creates less work for the compiler.  The compiler will only need to compile the function once and won't need to compare the generated binary code of each instance to remove duplicates.
>
> Another combination type that would be useful is an "anybyte" type.  This would handle both byte and char types (really any type that uses 1 byte of memory).  I'm sure many of the standard library functions would find this type useful.
>
> I was looking through some of the functions in std.stdio to see which ones could benefit from this and I realized that a useful extension to this would be to have a "sizeof" property on the "any" combination type.  You obviously could not access "any.sizeof" on a function argument inside the function, but the caller of the function could, so you could use "any.sizeof" as a default initializer.  With this functionality you could make std.stdio rawRead/rawWrite functions non-template like this:
>   Current: T[] rawRead(T)(T[] buffer);
>   New    : size_t rawRead(any[] buffer, size_t elementSize = any.sizeof);
>
>   Current: void rawWrite(T)(in T[] buffer);
>   New    : void rawWrite(any[] buffer, size_t elementSize = any.sizeof);
>
> This would add an extra runtime argument to the functions vs having multiple instances each with it's own element size passed to fread/fwrite so you'd be trading off an extra function parameter for only one instance of the function.  So this may or may not be the best solution. However I think most of the time this will be called with 1-byte-element arrays so you could have 2 instances of it, one with the "anybyte" type and one with the "any" type.  I could see a good argument for that solution.
>
> One last comment, when you do have a template function it would be nice if the compiler could guarantee that it would use combination types when it could.  For example, if the original function limitPtr was written using a template, the compiler could see that the array is never dereferenced so it knows that it can use an "any*/any[]" type for the template type so it only needs to generate one instance of it.
>
> There's probably more useful combination types I haven't thought of but I'll bring this initial idea to and end and see if anyone else has anything to say.

On Thursday, 30 October 2014 at 13:44:46 UTC, Marc Schütz wrote:
> On Thursday, 30 October 2014 at 12:51:50 UTC, Jonathan Marler wrote:
>> I'm not sure what the status is on this, I remember Walter saying in a conference (DConf 2014 I think) that he had an idea to remove duplicate template instantiations by comparing their generated code but I had another idea I thought I'd share.
>>
>> I'm calling the idea "CombinationTypes".  Sort of a "compile-time" concept that allows code to use multiple types that would produce the same binary code but retains type information.  The first combination type I would introduce is the "any*" or "any[]" types. For example, you could write the following function:
>>
>> any* limitPtr(any[] array) {
>>  return any.ptr + any.length;
>> }
>
> This is basically type erasure. It works well reasonably well as long as only references are allowed. But it seems you want to allow value types, too.
>
Ya, like I said I haven't thought of too many types (value types) that would be useful so I thought I'd throw the idea out there and see if anyone came up with anything.  I think the "anybyte" type could be pretty useful.

>>
>> The advantage of using a combination type like "any" over say "void" is the compiler knows what you are trying to do and won't require you to perform any awkward casting.  The following code should work fine:
>>
>> char[] mychars;
>> string mystring;
>>
>> auto mycharsLimit = mychars.limitPtr; // mycharsLimit is a char*
>> auto mystringLimit = mystring.limitPtr; // mystringLimit is a immutable(char)*
>>
>> The generated code for this function will be identical no matter what the element type is.
>
> Unfortunately not, only if it's an array of byte-sized elements. If you pass a `wchar[]`, the calculation needs to be <pointer + 2*length> instead of <pointer + length>.
>
> It gets more involved if you want to allow copying and assigning, because the types can have non-default `this()`, `this(this)`, `~this()`, `opAssign()`, and so on.
>
Oh woops you are right.  I guess this function would have to be implemented like this:
any* limitPtr(any[] array, size_t elementLength = any.sizeof) {
 return any.ptr + (elementLength * any.length);
}
That actually might be kind of confusing, the '+' operator on an unknown pointer defaulting to size 1 isn't really intuitive. Hmmm...I would have to think on this more.

One more thought that just came to me is maybe it would be useful to add an array/pointer type to the language that held it's element size at runtime.  You could implement that currently using casts and such, but having it as a first class type in the language would make it easy to use.  I don't know how helpful it would be though, maybe not enough benefit for the amount of work it would take to support it.  I might call it something like "dynamic*/dynamic[]" which would be the same as a regular pointer/array except they have an extra size_t field called elementSize.  Just a thought...

Microsoft's linker can reduplicate templates, they call it identical comdat folding.

That is basically generic à la java.

I'd like to see what can be done in term of library on that front
as I suspect that we can get quite far.

On Fri, Oct 31, 2014 at 07:47:29PM +0000, deadalnix via Digitalmars-d wrote:
> That is basically generic à la java.
> 
> I'd like to see what can be done in term of library on that front as I suspect that we can get quite far.

What would be more interesting IMO, is to explore ways of automating this so that a fully-generic template can be factored out into type-dependent parts and type-independent parts. While type erasure is advantageous in some circumstances, they are problematic in other circumstances. Similarly, while D's full templating system works well where type erasure is lacking, it also suffers from template bloat. Ideally, the best of both worlds should lie somewhere in between.


T

-- 
It is the quality rather than the quantity that matters. -- Lucius Annaeus Seneca

On Friday, 31 October 2014 at 20:06:57 UTC, H. S. Teoh via
Digitalmars-d wrote:
> On Fri, Oct 31, 2014 at 07:47:29PM +0000, deadalnix via Digitalmars-d wrote:
>> That is basically generic à la java.
>> 
>> I'd like to see what can be done in term of library on that front
>> as I suspect that we can get quite far.
>
> What would be more interesting IMO, is to explore ways of automating
> this so that a fully-generic template can be factored out into
> type-dependent parts and type-independent parts. While type erasure is
> advantageous in some circumstances, they are problematic in other
> circumstances. Similarly, while D's full templating system works well
> where type erasure is lacking, it also suffers from template bloat.
> Ideally, the best of both worlds should lie somewhere in between.
>
>
> T

Compiler have some capability to merge identical IR, and linker
identical codegen. But that tend to be expensive, and going the
type erasure road is a worthwhile option in many cases.