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.


And one fills the holes of the other.


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


I can't guarantee the "informed" part but,
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