www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Templates vs CTFE

reply Max Samukha <spambox d-coding.com> writes:
Some of us who have the knack of writing metaprograms in D know that 
many algorithms can be implemented with both recursive templates and 
CTFE. A simple example is map:

Recursive template instantiation:

template staticMap(alias pred, A...)
{
     static if (A.length)
         alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
}

CTFE:

template staticMap(alias pred, A)
{
     mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
}

private string _staticMap(size_t len)
{
     string result;
     if (len)
     {
         result ~= "pred!(A[0])";
         for(size_t i = 1, i < len; ++i)
         {
             result ~= ", pred!(A[" ~ to!string(i) ~ "])";
         }
     }
     return result;
}

It is not easy to decide which approach to implement in a library 
because both have drawbacks.

Can anybody give informed advice as to which one is preferable in 
practice? Or should a library provide both?
Jan 06 2011
next sibling parent Max Samukha <spambox d-coding.com> writes:
On 01/06/2011 07:49 PM, Max Samukha wrote:
 template staticMap(alias pred, A...)
 {
 static if (A.length)
 alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
 }

Should be: template staticMap(alias pred, A...) { static if (A.length) alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap; else alias TypeTuple!() staticMap; }
Jan 06 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Thu, 06 Jan 2011 12:49:19 -0500, Max Samukha <spambox d-coding.com>  
wrote:

 Some of us who have the knack of writing metaprograms in D know that  
 many algorithms can be implemented with both recursive templates and  
 CTFE. A simple example is map:

 Recursive template instantiation:

 template staticMap(alias pred, A...)
 {
      static if (A.length)
          alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
 }

 CTFE:

 template staticMap(alias pred, A)
 {
      mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
 }

 private string _staticMap(size_t len)
 {
      string result;
      if (len)
      {
          result ~= "pred!(A[0])";
          for(size_t i = 1, i < len; ++i)
          {
              result ~= ", pred!(A[" ~ to!string(i) ~ "])";
          }
      }
      return result;
 }

 It is not easy to decide which approach to implement in a library  
 because both have drawbacks.

 Can anybody give informed advice as to which one is preferable in  
 practice? Or should a library provide both?

CTFE is generally easier to write/understand and more generic than doing the same thing in templates. However, there are some serious flaws in how DMD currently handles CT strings (and arrays in general) which can lead extremely complex CTFE code to be incorrect, very slow to compile or crash DMD outright. For example, I initially implemented a compile-time reflection to runtime-time reflection system for an improved std.variant using CTFE, but had to switch to templates/conditional compilation instead. (see https://jshare.johnshopkins.edu/rjacque2/public_html/) See bug 1382 (http://d.puremagic.com/issues/show_bug.cgi?id=1382).
Jan 06 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, January 06, 2011 09:49:19 Max Samukha wrote:
 Some of us who have the knack of writing metaprograms in D know that
 many algorithms can be implemented with both recursive templates and
 CTFE. A simple example is map:
 
 Recursive template instantiation:
 
 template staticMap(alias pred, A...)
 {
      static if (A.length)
          alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
 }
 
 CTFE:
 
 template staticMap(alias pred, A)
 {
      mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
 }
 
 private string _staticMap(size_t len)
 {
      string result;
      if (len)
      {
          result ~= "pred!(A[0])";
          for(size_t i = 1, i < len; ++i)
          {
              result ~= ", pred!(A[" ~ to!string(i) ~ "])";
          }
      }
      return result;
 }
 
 It is not easy to decide which approach to implement in a library
 because both have drawbacks.
 
 Can anybody give informed advice as to which one is preferable in
 practice? Or should a library provide both?

I suppose that in theory, I would say to use templates for things that really are intended to always be used at compile time and CTFE for functions which would make sense both for compile time and runtime. But whether that's actually the best practice (particularly given the current state of dmd and CTFE), I don't know. Personally, I think what generally happens in that when I'm trying to do something which needs to be done at compile time, I use CTFE if a function already exists which will do what I want, and I use a template if it doesn't. Or if it's something that I know that I need to be used both at compile time and runtime, then I make it a function for use with CTFE. I think that in at least one case, I've created a template for use at compile time and a function for use at runtime so that I could have additional checks or different behavior at runtime (I think that I had it throw an exception at runtime, which you can't do at compile time), but that's not the norm. I don't know. I've rarely sat down and tried to decide whether something should be a template or a CTFE-able function. I think that it most cases I've either been creating a function for runtime and possible used it also at compile time, or I've needed something at compile time, so I've created a template. - Jonathan M Davis
Jan 06 2011
prev sibling next sibling parent reply Robert Clipsham <robert octarineparrot.com> writes:
On 06/01/11 17:49, Max Samukha wrote:
 Some of us who have the knack of writing metaprograms in D know that
 many algorithms can be implemented with both recursive templates and
 CTFE. A simple example is map:

 Recursive template instantiation:

 template staticMap(alias pred, A...)
 {
 static if (A.length)
 alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
 }

 CTFE:

 template staticMap(alias pred, A)
 {
 mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
 }

 private string _staticMap(size_t len)
 {
 string result;
 if (len)
 {
 result ~= "pred!(A[0])";
 for(size_t i = 1, i < len; ++i)
 {
 result ~= ", pred!(A[" ~ to!string(i) ~ "])";
 }
 }
 return result;
 }

 It is not easy to decide which approach to implement in a library
 because both have drawbacks.

 Can anybody give informed advice as to which one is preferable in
 practice? Or should a library provide both?

Put each of those implementations in its own file, then call it several times. Look at the binary size for each implementation, also run `strings ctfeTest` if you're on a *nix. This should give you your answer :) -- Robert http://octarineparrot.com/
Jan 06 2011
parent reply Max Samukha <spambox d-coding.com> writes:
On 01/06/2011 09:28 PM, Robert Clipsham wrote:
 Put each of those implementations in its own file, then call it several
 times. Look at the binary size for each implementation, also run
 `strings ctfeTest` if you're on a *nix. This should give you your answer :)

The problem is they are not easy to compare using artificial tests. For example, there is a hard-wired limit to template nesting depth in the compiler. And with the number of input elements less than this limit, the difference in results seems to be insignificant. BTW, if we want to be taken seriously such limits should be configurable. Why the depth of 500 and not 600? I wonder where the value comes from. Ok, I think I will simply implement both variants and let the user choose. Thanks for the responses.
Jan 07 2011
parent reply Don <nospam nospam.com> writes:
Max Samukha wrote:
 On 01/06/2011 09:28 PM, Robert Clipsham wrote:
 Put each of those implementations in its own file, then call it several
 times. Look at the binary size for each implementation, also run
 `strings ctfeTest` if you're on a *nix. This should give you your 
 answer :)

The problem is they are not easy to compare using artificial tests. For example, there is a hard-wired limit to template nesting depth in the compiler. And with the number of input elements less than this limit, the difference in results seems to be insignificant. BTW, if we want to be taken seriously such limits should be configurable. Why the depth of 500 and not 600? I wonder where the value comes from.

It's about the largest value it can be before a compiler stack overflow occurs.
Jan 07 2011
parent Max Samukha <spambox d-coding.com> writes:
On 01/07/2011 03:12 PM, Don wrote:
 Max Samukha wrote:
 On 01/06/2011 09:28 PM, Robert Clipsham wrote:
 Put each of those implementations in its own file, then call it several
 times. Look at the binary size for each implementation, also run
 `strings ctfeTest` if you're on a *nix. This should give you your
 answer :)

The problem is they are not easy to compare using artificial tests. For example, there is a hard-wired limit to template nesting depth in the compiler. And with the number of input elements less than this limit, the difference in results seems to be insignificant. BTW, if we want to be taken seriously such limits should be configurable. Why the depth of 500 and not 600? I wonder where the value comes from.

It's about the largest value it can be before a compiler stack overflow occurs.

I meant the value should not be a magical number hard-coded somewhere in template.c. One can configure stack size and it should be possible to configure a dmd build with adjusted nesting value.
Jan 07 2011
prev sibling next sibling parent so <so so.do> writes:
Actually they are not that related, you may solve a problem with each of  
them but this is different.
What makes CTFE awesome is that you use same function for runtime and  
compile-time, without a single change.
The answer to your question is just in this very definition i believe.

 It is not easy to decide which approach to implement in a library  
 because both have drawbacks.

 Can anybody give informed advice as to which one is preferable in  
 practice? Or should a library provide both?

Between your two implementations it is obvious which one, after you answer the question: What you want it to be, runtime? compile-time? both?
Jan 07 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 06 Jan 2011 12:49:19 -0500, Max Samukha <spambox d-coding.com>  
wrote:

 Some of us who have the knack of writing metaprograms in D know that  
 many algorithms can be implemented with both recursive templates and  
 CTFE. A simple example is map:

 Recursive template instantiation:

 template staticMap(alias pred, A...)
 {
      static if (A.length)
          alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
 }

 CTFE:

 template staticMap(alias pred, A)
 {
      mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
 }

 private string _staticMap(size_t len)
 {
      string result;
      if (len)
      {
          result ~= "pred!(A[0])";
          for(size_t i = 1, i < len; ++i)
          {
              result ~= ", pred!(A[" ~ to!string(i) ~ "])";
          }
      }
      return result;
 }

 It is not easy to decide which approach to implement in a library  
 because both have drawbacks.

 Can anybody give informed advice as to which one is preferable in  
 practice? Or should a library provide both?

You should prefer CTFE IMO. Templates can leave a trail of instantiated templates in the exe. The compiler does not trim anything out that's only used at compile time, but I think with CTFE it does not instantiate as many templates. I'd guess the exe size would be significantly larger for the template solution for a large number of elements. -Steve
Jan 07 2011