www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Template specialized functions creating runtime instructions?

reply ads <relay.public.adnan outlook.com> writes:
This piece of code creates a fizzbuzz string with template 
parameters.

auto fizzbuzz(uint N)() {
	string accumulate;
	return fizzbuzz!N(accumulate);
}

auto fizzbuzz(uint N)(ref string result) if (N % 3 && N % 5) {
	import std.conv : to;

	result ~= N.to!string ~ "\n";
	return fizzbuzz!(N - 1)(result);
}

auto fizzbuzz(uint N)(ref string result) if (!(N % 15)) {
	result ~= "FizzBuzz\n";
	return fizzbuzz!(N - 1)(result);
}

auto fizzbuzz(uint N)(ref string result) if (!(N % 3) && N % 5) {
	result ~= "Fizz\n";
	return fizzbuzz!(N - 1)(result);
}

auto fizzbuzz(uint N)(ref string result) if (!(N % 5) && N % 3) {
	result ~= "Buzz\n";
	return fizzbuzz!(N - 1)(result);
}

auto fizzbuzz(uint N : 0)(ref string result) {
	return result;
}

void main() {
	import std.stdio : writeln;

	fizzbuzz!50().writeln();
}


https://godbolt.org/z/hWENgc

In the generated assembly, it looks like it is creating a lot of 
runtime instructions, contrary to my belief that templated codes 
are purely compile-time. I was expecting that the compiler would 
deduce the fizzbuzz string until 50 in compile-time and just 
print it in the run-time. Why is this not the case?
Aug 20 2019
next sibling parent ads <relay.public.adnan outlook.com> writes:
On Tuesday, 20 August 2019 at 23:48:04 UTC, ads wrote:

 https://godbolt.org/z/hWENgc


A somewhat similar translation in C++ also creates a lot of 
runtime instructions
https://godbolt.org/z/psyUtq
Aug 20 2019
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Aug 20, 2019 at 11:48:04PM +0000, ads via Digitalmars-d-learn wrote:
[...]

 In the generated assembly, it looks like it is creating a lot of
 runtime instructions, contrary to my belief that templated codes are
 purely compile-time. I was expecting that the compiler would deduce
 the fizzbuzz string until 50 in compile-time and just print it in the
 run-time. Why is this not the case?


Let's clear up a few things:

1) "Template code" is not the same thing as "compile-time". Templates
are essentially "code stencils", used for generating multiple copies
(usually with variations) of the same *runtime* code.  The *expansion*
of the template is done at compile-time, but the *result* is often
runtime code (e.g., template functions, like you have here).

2) Deducing the string as you describe would require CTFE (compile-time
function evaluation), which usually isn't done unless the result is
*required* at compile-time.  The typical way to force this to happen is
to store the result into an enum:

	enum myStr = fizzbuzz!...(...);
	writeln(myStr);

Since enums have to be known at compile-time, this forces CTFE
evaluation of fizzbuzz, which is probably what you're looking for here.

3) And BTW, don't confuse "templates" and CTFE, because they are not the
same thing, in spite of being both done "at compile-time". See:

	https://wiki.dlang.org/User:Quickfur/Compile-time_vs._compile-time


T

-- 
Those who've learned LaTeX swear by it. Those who are learning LaTeX swear at
it. -- Pete Bleackley
Aug 20 2019
parent reply ads <relay.public.adnan outlook.com> writes:
On Wednesday, 21 August 2019 at 00:04:37 UTC, H. S. Teoh wrote:

 On Tue, Aug 20, 2019 at 11:48:04PM +0000, ads via 
 Digitalmars-d-learn wrote: [...]
 2) Deducing the string as you describe would require CTFE 
 (compile-time function evaluation), which usually isn't done 
 unless the result is *required* at compile-time.  The typical 
 way to force this to happen is to store the result into an enum:

 	enum myStr = fizzbuzz!...(...);
 	writeln(myStr);

 Since enums have to be known at compile-time, this forces CTFE 
 evaluation of fizzbuzz, which is probably what you're looking 
 for here.

 T


Thank you for clearing those up. However even if I force CTFE 
(line 35), it doesn't seem to help much.

https://godbolt.org/z/MytoLF
Aug 20 2019
parent Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Wednesday, 21 August 2019 at 00:11:23 UTC, ads wrote:

 On Wednesday, 21 August 2019 at 00:04:37 UTC, H. S. Teoh wrote:

 On Tue, Aug 20, 2019 at 11:48:04PM +0000, ads via 
 Digitalmars-d-learn wrote: [...]
 2) Deducing the string as you describe would require CTFE 
 (compile-time function evaluation), which usually isn't done 
 unless the result is *required* at compile-time.  The typical 
 way to force this to happen is to store the result into an 
 enum:

 	enum myStr = fizzbuzz!...(...);
 	writeln(myStr);

 Since enums have to be known at compile-time, this forces CTFE 
 evaluation of fizzbuzz, which is probably what you're looking 
 for here.

 T


 Thank you for clearing those up. However even if I force CTFE 
 (line 35), it doesn't seem to help much.

 https://godbolt.org/z/MytoLF


It does.

on line 4113 you have that string

.L.str:
         .asciz  
"Buzz\n49\nFizz\n47\n46\nFizzBuzz\n44\n43\nFizz\n41\nBuzz\nFizz\n38\n37\nFizz\nBuzz\n34\nFizz\n32\n31\nFizzBuzz\n29\n28\nFizz\n26\nBuzz\nFizz\n23\n22\nFizz\nBuzz\n19\nFizz\n17\n16\nFizzBuzz\n14\n13\nFizz\n11\nBuzz\nFizz\n8\n7\nFizz\nBuzz\n4\nFizz\n2\n1\n"

and all main() does is call writeln with that string

_Dmain:
         push    rax
         lea     rsi, [rip + .L.str]
         mov     edi, 203
         call     safe void 
std.stdio.writeln!(immutable(char)[]).writeln(immutable(char)[]) PLT
         xor     eax, eax
         pop     rcx
         ret


You haven't given instruction to the linker to strip unused code 
so the functions generated by the templates are still there.
Aug 21 2019
prev sibling next sibling parent ag0aep6g <anonymous example.com> writes:
On 21.08.19 01:48, ads wrote:

 This piece of code creates a fizzbuzz string with template parameters.
 
 auto fizzbuzz(uint N)() {
      string accumulate;
      return fizzbuzz!N(accumulate);
 }
 
 auto fizzbuzz(uint N)(ref string result) if (N % 3 && N % 5) {
      import std.conv : to;
 
      result ~= N.to!string ~ "\n";
      return fizzbuzz!(N - 1)(result);
 }


[...]

 void main() {
      import std.stdio : writeln;
 
      fizzbuzz!50().writeln();
 }
 
 
 https://godbolt.org/z/hWENgc
 
 In the generated assembly, it looks like it is creating a lot of runtime 
 instructions, contrary to my belief that templated codes are purely 
 compile-time. I was expecting that the compiler would deduce the 
 fizzbuzz string until 50 in compile-time and just print it in the 
 run-time. Why is this not the case?


What you have there are function templates. You're generating functions 
at compile time, and then you're calling those generated functions at 
run time.

To do it all at compile time, you can skip the "functions" part and 
generate the result directly:

     template fizzbuzz(uint N) if (N % 3 && N % 5)
     {
         import std.conv : to;
         enum fizzbuzz = N.to!string ~ "\n" ~ fizzbuzz!(N - 1);
     }
     /* ... etc ... */

You won't be able to use an accumulator, because mutation like that 
doesn't mix with templates.

Alternatively, you can skip the "templates" part and call normal 
functions at compile time (CTFE):

     auto fizzbuzz(uint N)
     {
         string accumulate;
         return fizzbuzz(N, accumulate);
     }
     auto fizzbuzz(uint N, ref string result)
     {
         import std.conv : to;
         if (N % 3 && N % 5) result ~= N.to!string ~ "\n";
         /* ... etc ... */
     }
     void main()
     {
         import std.stdio : writeln;
         enum fz = fizzbuzz(50);
         writeln(fz);
     }
Aug 20 2019
prev sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, August 20, 2019 5:48:04 PM MDT ads via Digitalmars-d-learn 
wrote:

 This piece of code creates a fizzbuzz string with template
 parameters.

 auto fizzbuzz(uint N)() {
   string accumulate;
   return fizzbuzz!N(accumulate);
 }

 auto fizzbuzz(uint N)(ref string result) if (N % 3 && N % 5) {
   import std.conv : to;

   result ~= N.to!string ~ "\n";
   return fizzbuzz!(N - 1)(result);
 }

 auto fizzbuzz(uint N)(ref string result) if (!(N % 15)) {
   result ~= "FizzBuzz\n";
   return fizzbuzz!(N - 1)(result);
 }

 auto fizzbuzz(uint N)(ref string result) if (!(N % 3) && N % 5) {
   result ~= "Fizz\n";
   return fizzbuzz!(N - 1)(result);
 }

 auto fizzbuzz(uint N)(ref string result) if (!(N % 5) && N % 3) {
   result ~= "Buzz\n";
   return fizzbuzz!(N - 1)(result);
 }

 auto fizzbuzz(uint N : 0)(ref string result) {
   return result;
 }

 void main() {
   import std.stdio : writeln;

   fizzbuzz!50().writeln();
 }


 https://godbolt.org/z/hWENgc

 In the generated assembly, it looks like it is creating a lot of
 runtime instructions, contrary to my belief that templated codes
 are purely compile-time. I was expecting that the compiler would
 deduce the fizzbuzz string until 50 in compile-time and just
 print it in the run-time. Why is this not the case?


Function templates create normal functions when they're instantiated. They
aren't going to be removed from the binary any more than a non-templated
function would be. And the compiler has no way of knowing which functions
can be removed from the final executable. It's just creating object files
that get linked into the final executable. It's the linker that would have
to strip unnecessary stuff out. And since fizzbuzz!50 is called at runtime,
even if the linker did strip out functions that weren't needed, it couldn't
strip out any of fizzbuzz!50 or anything that it calls.

The compiler doesn't call functions at compile time unless they're used in a
context where the value must be known at compile time. So,

fizzbuzz!50.writeln();

is not going to involve any fnuctions being called at compile time. Each
function template that needs to be instantiated would be instantiated, but
that just creates a bunch of functions that can be called. For any functions
to be called at compile time, you'd have to force it by calling a function
in a context where the result must be known at compile time. e.g.

enum value = fizzbuzz!50();

would result in fizzbuzz!50 being called at compile time, and then the value
could be passed to writeln at runtime.

If you actually want templates to do all of their work at compile time, then
you wouldn't use functions. You'd just use eponymous templates. e.g.
something like

template factorial(int n)
{
    static if(n == 1)
        enum factorial = n;
    else
        enum factorial = factorial!(n - 1) * n;
}

in which case the you'd use it by doing something like

enum result = factorial!5;

or

int result = factorial!5;

In either case, because factorial is purely a template, the work would be
done at compile time.

Alternatively, you can just call functions at compile time - you just have
to make sure that the call is in a context where the result must be known at
compile time. e.g.

int factorial(int n)
{
    int result = 1;
    foreach(i; 2 .. n + 1)
        result *= i;
    return result;
}

enum result = factorial(5);

There arguably isn't much point in using templated functions the way you
are. It would be simpler to just write a function that calculated the result
normally, and then if you want to have the result at compile time, you just
call the function and use the result to give an enum its value.

- Jonathan M Davis
Aug 20 2019