www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Less Code Bloat from Templates

reply "Jonathan Marler" <johnnymarler gmail.com> writes:
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.
Oct 30 2014
next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
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.
Oct 30 2014
parent "Jonathan Marler" <johnnymarler gmail.com> writes:
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...
Oct 30 2014
prev sibling next sibling parent "Martin Nowak" <code dawg.eu> writes:
Microsoft's linker can reduplicate templates, they call it 
identical comdat folding.
Oct 31 2014
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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.
Oct 31 2014
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
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
Oct 31 2014
parent "deadalnix" <deadalnix gmail.com> writes:
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.
Oct 31 2014