www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Folding similar templates into one

reply "Meta" <jared771 gmail.com> writes:
I apologize for the title, as I couldn't come up with something 
succinct and descriptive enough while still being reasonably 
short. We all know how powerful templates are in C++/D, but they 
have that damning cost of needing to generate new code for each 
new template argument. For example:

string format(string fmtStr)(T data)
{
     ...
}

As fmtStr is a compile-time template argument, the compiler will 
have to generate N nearly-identical format functions for N 
strings that format is instantiated with. This "template bloat" 
increases exponentially as more template arguments are added. 
Take std.exception.assertNotThrown:

void assertNotThrown(T : Throwable = Exception, E)
                     (lazy E expression,
                      string msg = null,

                      //Could be compile-time, but aren't,
                      //because of template bloat worries
                      string file = __FILE__,
                      size_t line = __LINE__)
{
     try
         expression();
     catch(T t)
     {
         immutable message = msg.empty ? t.msg : msg;
         immutable tail = message.empty ? "." : ": " ~ message;
         throw new AssertError(format("assertNotThrown failed: %s 
was thrown%s",
                                      T.stringof,
                                      tail),
                               file,
                               line,
                               t);
     }
}

The arguments file and line are known at compile time, but should 
not be made template arguments because there is a potential to 
create N*M copies of assertNotThrown, given N values of __FILE__ 
and M values of __LINE__.

Adding large numbers of template arguments spuriously can cause 
an explosion in binary size, especially when templates are very 
heavily used, such as in most D code. Furthermore, programmers 
worried about such bloat will undoubtedly take the safe route, 
and try to move as many arguments as possible from the 
compile-time parameter list to run-time. This means that 
generated code will not necessarily be efficient as it should be.

I'd like to ask, however, why should this be? The arguments line 
and file will only ever be strings and ints. They don't vary in 
type, only value, and changing those values will not affect how 
the function works. You could easily substitute out "exception.d" 
with "stdio.d", and the functionality will be unchanged.

This remains true for values of the same type. It doesn't matter 
whether you pass 1000, 10_000, or 100_000 as a template argument. 
The way the function operates is not observably different (note 
that for this to be true, we have to assume that static if does 
not exist). This is in contrast to passing a completely different 
type for T (say, RangeError), which may change how the function 
works.

I'd like to know, are there any template "optimizations" that DMD 
currently implements which mitigates such a situation such as 
with assertNotThrown, where a compile-time argument may vary only 
in value, and not type? Judging from the fact that this function 
was changed so that that __FILE__ and __LINE__ are taking as 
run-time parameters, I guess the answer is no. Is there anything 
we can do about this?
Jun 26 2013
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, June 27, 2013 04:03:34 Meta wrote:
 I'd like to ask, however, why should this be? The arguments line
 and file will only ever be strings and ints. They don't vary in
 type, only value, and changing those values will not affect how
 the function works. You could easily substitute out "exception.d"
 with "stdio.d", and the functionality will be unchanged.

That's _very_ dependent on what the function does. A prime counter-example would be overloaded operators like opBinary which uses their string template arguments in mixins within the function, thereby generating completely different functions. And I believe that that is by far the more common use of strings as template parameters. Also, when using strings and integral values such as __FILE__ and __LINE__, the functions _do_ have different code. auto foo(string file = __FILE__, size_t line = __LINE__)(Bar b) { auto f = file; auto l = line; .... } ends up generating different code depending on the values of file or line. The code is _not_ identical. The only way for the code not to vary is for those arguments to be runtime arguments. If they're compile-time arguments, then by definition, they affect the generated code if they're ever used. Yes, it is theoretically possible for the compiler to use the same template definition under certain circumstances (especially if you're dealing with something like a templated struct that ultimately ends up with exactly the same layout across multiple instantiations), but the only way that the compiler could avoid duplicating the code with something like __FILE__ and __LINE__ being used as template arguments is to translate them into function arguments, because if the function has only one definition, then it can't have different values for the file or line number. - Jonathan M Davis
Jun 26 2013
parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Meta" <jared771 gmail.com> wrote in message 
news:ovlbbsdtyejzpsllfrcb forum.dlang.org...
I'm not an expert on how DMD works, but could this possibly be done after 
the native code is generated, but before optimizations are performed? Just 
throwing out ideas.

The obvious place to do this is at link time - then you get to fold all functions from all compilation units. It becomes something similar to string constant pooling - you fold sections/data based on content, not labels.
Jun 28 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Thursday, 27 June 2013 at 03:47:39 UTC, Jonathan M Davis wrote:
 That's _very_ dependent on what the function does. A prime 
 counter-example
 would be overloaded operators like opBinary which uses their 
 string template
 arguments in mixins within the function, thereby generating 
 completely
 different functions. And I believe that that is by far the more 
 common use of
 strings as template parameters.

This may be true. Any kind of optimization would probably have to ignore most operator functions. Another heavy use of strings, however, is string lambdas. Checking if two string lambdas are the same is a simple string comparison, and then that template can be compiled once and all copies can be ellided. Then it's just a call to that template wherever it is used with that particular lambda in the program. I think this could be done with any template that accepts some kind of lambda function, but it may be somewhat tricky currently to figure out if two non-string lambda are equal, and I believe that DMD currently generates a unique lambda wherever one is used.
 Also, when using strings and integral values such as __FILE__ 
 and __LINE__,
 the functions _do_ have different code.

 auto foo(string file = __FILE__, size_t line = __LINE__)(Bar b)
 {
  auto f = file;
  auto l = line;

  ....
 }

 ends up generating different code depending on the values of 
 file or line. The
 code is _not_ identical. The only way for the code not to vary 
 is for those
 arguments to be runtime arguments. If they're compile-time 
 arguments, then by
 definition, they affect the generated code if they're ever used.

I do know that the code generated is different. Turning compile-time arguments into run-time arguments will, unfortunately, completely defeat the point, as you know. It's a tricky problem, because you can't just partially compile a function and then change the compile-time arguments as you encounter each new instantiation. If we could do that, we wouldn't have this problem, and we would probably be using Common Lisp.
 Yes, it is theoretically possible for the compiler to use the 
 same template
 definition under certain circumstances (especially if you're 
 dealing with
 something like a templated struct that ultimately ends up with 
 exactly the
 same layout across multiple instantiations), but the only way 
 that the
 compiler could avoid duplicating the code with something like 
 __FILE__ and
 __LINE__ being used as template arguments is to translate them 
 into function
 arguments, because if the function has only one definition, 
 then it can't have
 different values for the file or line number.

This is something that could be potentially solved on the binary level, if you're sure that varying the value of a template argument will not affect how it functions. I'm not an expert on how DMD works, but could this possibly be done after the native code is generated, but before optimizations are performed? Just throwing out ideas.
Jun 27 2013
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Thu, 27 Jun 2013 23:24:48 +0200
schrieb "Meta" <jared771 gmail.com>:

 I'm not an expert on 
 how DMD works, but could this possibly be done after the native 
 code is generated

I've thought of that as well, but you have to merge templates at an earlier stage. In case of a compiler such as GCC, the native code is not even generated in the compiler, but an external assembler. That said, DMD does not create duplicate template instances for the same parameters. I'd assume this includes "string lambdas". And I'm not sure what you really want to improve for assertNotThrown. It is a unit testing function and the most important thing at the moment seems to keep DMD's memory consumption low, which more compile-time parameters can only increase. Another point is that today's best compilers are good at detecting compile-time constants already and could inline a function with runtime parameters that are statically known. I've once let DMD create a switch-case with 81 cases for me and used a 100% templated function specialized for all these cases. The result was a major slow-down from all the compile-time arguments. Run-time arguments are just better! -- Marco
Jun 28 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Friday, 28 June 2013 at 12:45:22 UTC, Marco Leise wrote:
 Am Thu, 27 Jun 2013 23:24:48 +0200
 schrieb "Meta" <jared771 gmail.com>:

 I'm not an expert on how DMD works, but could this possibly be 
 done after the native code is generated

I've thought of that as well, but you have to merge templates at an earlier stage. In case of a compiler such as GCC, the native code is not even generated in the compiler, but an external assembler. That said, DMD does not create duplicate template instances for the same parameters. I'd assume this includes "string lambdas".

That's good to know. I wasn't sure if there were some cases when template were ellided or not, even with the same arguments. By string lambdas, I mean lambdas of the form sort!"a <= b" that are heavily used in std.algorithm.
 And I'm not sure what you really want to improve for
 assertNotThrown. It is a unit testing function and the most
 important thing at the moment seems to keep DMD's memory
 consumption low, which more compile-time parameters can only
 increase.

I was only using assertNotThrown as an example of a template function where parameters that could be compile-time arguments become run-time arguments to minimize template bloat.
 Another point is that today's best compilers are good at
 detecting compile-time constants already and could inline a
 function with runtime parameters that are statically known.
 I've once let DMD create a switch-case with 81 cases for me
 and used a 100% templated function specialized for all these
 cases. The result was a major slow-down from all the
 compile-time arguments. Run-time arguments are just better!

That is certainly a corner case. Perhaps finding a way to fold templates in some cases would still provide benefits in more normal cases.
Jun 28 2013
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 28 June 2013 at 12:45:22 UTC, Marco Leise wrote:
 Am Thu, 27 Jun 2013 23:24:48 +0200
 schrieb "Meta" <jared771 gmail.com>:

 I'm not an expert on how DMD works, but could this possibly be 
 done after the native code is generated

I've thought of that as well, but you have to merge templates at an earlier stage. In case of a compiler such as GCC, the native code is not even generated in the compiler, but an external assembler. That said, DMD does not create duplicate template instances for the same parameters. I'd assume this includes "string lambdas".

What is a "string lambda" ? Do you mean "a string alias latter parsed as an expression", or "an actual lambda function". There were talks about this recently in learn: If you *type* the same lambda function twice, it *will* generate two different templates. http://forum.dlang.org/thread/rufkccowcdogctvckzar forum.dlang.org For example: -------- struct S(alias pred){} void main() { auto a = S!(() => 1)(); auto b = S!(() => 1)(); a = b; } -------- DMD v2.064 DEBUG main.d(7): Error: cannot implicitly convert expression (b) of type S!(function int() { return 1; } ) to S!(function int() { return 1; } ) -------- However, -------- enum PRED = () => 1; struct S(alias pred){} void main() { auto a = S!PRED(); auto b = S!PRED(); a = b; } -------- This is fine. From testing, *string* preds don't have this "feature"/"bug" (?), even if you compile time build them, the compiler will "see" that it is the same string (probably true for integrals and whatnot). But for lambdas, only their *name* counts (eg __lambda1__). So if you plan to re-use a lambda, it *must* be stored in a way the compiler can "see" its unicity, and not typed more than once. Furthermore, I'm think this is the correct behavior.
Jun 28 2013
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 27 June 2013 at 02:03:52 UTC, Meta wrote:
 I'd like to ask, however, why should this be? The arguments 
 line and file will only ever be strings and ints. They don't 
 vary in type, only value, and changing those values will not 
 affect how the function works. You could easily substitute out 
 "exception.d" with "stdio.d", and the functionality will be 
 unchanged.

Just because the arguments are known 99% of the time at compile time, doesn't mean they should be parameters. Parameters shouldn't be used to just mean "compile time" anyways, but *specifically* to create different versions of a function or code, which in this case, is not the case at all. Besides, there are scenarios where you could pass these as runtime parameters from higher functions, if you want the exception to "look" like it came from a higher level call. Making these parameters would mean that *any* function that handles lines or filenames would have to be parameterized on that.
Jun 28 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Friday, 28 June 2013 at 13:20:47 UTC, monarch_dodra wrote:

 What is a "string lambda" ? Do you mean "a string alias latter 
 parsed as an expression", or "an actual lambda function".

The former. I didn't think it was *that* obscure of a term (https://www.google.com/search?q=%22string+lambda%22+site:forum.dlang.org).
 There were talks about this recently in learn: If you *type* 
 the same lambda function twice, it *will* generate two 
 different templates.
 http://forum.dlang.org/thread/rufkccowcdogctvckzar forum.dlang.org

I'm not sure if that's due to this bug or not: http://forum.dlang.org/thread/jdbhas$2ftb$1 digitalmars.com?page=2#post-jdcn98:241mg9:244:40digitalmars.com
 However,

 --------
 enum PRED = () => 1;

 struct S(alias pred){}

 void main()
 {
     auto a = S!PRED();
     auto b = S!PRED();
     a = b;
 }
 --------
 This is fine.

If that's all it takes to avoid copies, then maybe it's not so big of a problem for lambdas.
 From testing, *string* preds don't have this "feature"/"bug" 
 (?), even if you compile time build them, the compiler will 
 "see" that it is the same string (probably true for integrals 
 and whatnot). But for lambdas, only their *name* counts (eg 
 __lambda1__). So if you plan to re-use a lambda, it *must* be 
 stored in a way the compiler can "see" its unicity, and not 
 typed more than once.

Ditto.
Jun 28 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Friday, 28 June 2013 at 13:25:54 UTC, monarch_dodra wrote:
 Just because the arguments are known 99% of the time at compile 
 time, doesn't mean they should be parameters. Parameters 
 shouldn't be used to just mean "compile time" anyways, but 
 *specifically* to create different versions of a function or 
 code, which in this case, is not the case at all.

That was probably the idea when templates were conceived of for C++, but I think their usage has evolved far beyond that now, especially in D. With the advent of CTFE, there's an enormous amount that we can do at compile-time, a lot of which isn't strictly related to characterizing a function/struct/class/etc. on a type. Though I suppose it could be argued that with CTFE, doing compile-time template stuff isn't as important.
 Besides, there are scenarios where you could pass these as 
 runtime parameters from higher functions, if you want the 
 exception to "look" like it came from a higher level call.

I was just using assertNotThrown as an example to illustrate my point.
 Making these parameters would mean that *any* function that 
 handles lines or filenames would have to be parameterized on 
 that.

I don't think there's anything stopping you from passing __FILE__ and __LINE__ as template parameters to some functions, and as function parameters to other functions.
Jun 28 2013
prev sibling parent "Meta" <jared771 gmail.com> writes:
On Friday, 28 June 2013 at 22:40:14 UTC, Meta wrote:
 With the advent of CTFE, there's an enormous amount that we can 
 do at compile-time, a lot of which isn't strictly related to 
 characterizing a function/struct/class/etc. on a type.

s/characterizing/parameterizing
Jun 28 2013