View mode: basic / threaded / horizontal-split · Log in · Help
October 06, 2008
Static argument optimization
Hello,

Often I encounter cases where I have a function taking some arguments, and  
I'd like for the compiler to generate separate code for the function when  
some of the arguments are known at compile time. For example, consider  
this function:

int pow(int n, int power)
{
	return power==0 ? 1 : n*pow(n, power-1);
}

I am looking for a way to make the function work at runtime, while pow(n,  
3) to be inlined as n*n*n, and pow(2, 3) to be precalculated as 8. Is it  
possible to do this with some template trickery without having to write  
three versions of the function? I know macros should be able to do this in  
theory...

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com
October 06, 2008
Re: Static argument optimization
"Vladimir Panteleev" wrote
> Hello,
>
> Often I encounter cases where I have a function taking some arguments, and 
> I'd like for the compiler to generate separate code for the function when 
> some of the arguments are known at compile time. For example, consider 
> this function:
>
> int pow(int n, int power)
> {
> return power==0 ? 1 : n*pow(n, power-1);
> }
>
> I am looking for a way to make the function work at runtime, while pow(n, 
> 3) to be inlined as n*n*n, and pow(2, 3) to be precalculated as 8. Is it 
> possible to do this with some template trickery without having to write 
> three versions of the function? I know macros should be able to do this in 
> theory...

pow(2,3) should be pre-executed as you wish, due to CTFE rules.

Not sure about optimizing pow(n, 3) though.  Pure functions with tail 
recursion should help though when they are implemented.

BTW, you can optimize your function slightly for times when neither argument 
is pre-known:

int pow(int n, int power)
{
  if(power == 0) return 1;
  if(power & 1) return n * pow(n, power - 1);
  auto tmp = pow(n, power / 2)
  return tmp * tmp;
}

-Steve
October 07, 2008
Re: Static argument optimization
== Quote from Vladimir Panteleev (thecybershadow@gmail.com)'s article
> Hello,
> Often I encounter cases where I have a function taking some arguments, and
> I'd like for the compiler to generate separate code for the function when
> some of the arguments are known at compile time. For example, consider
> this function:
> int pow(int n, int power)
> {
> 	return power==0 ? 1 : n*pow(n, power-1);
> }
> I am looking for a way to make the function work at runtime, while pow(n,
> 3) to be inlined as n*n*n, and pow(2, 3) to be precalculated as 8. Is it
> possible to do this with some template trickery without having to write
> three versions of the function? I know macros should be able to do this in
> theory...

Am I missing something, or is the much bigger problem here that you're using
non-tail recursion when iteration would be much more efficient (and less likely to
overflow the stack)?
October 07, 2008
Re: Static argument optimization
Vladimir Panteleev wrote:
> Hello,
> 
> Often I encounter cases where I have a function taking some arguments, 
> and I'd like for the compiler to generate separate code for the function 
> when some of the arguments are known at compile time. For example, 
> consider this function:
> 
> int pow(int n, int power)
> {
>     return power==0 ? 1 : n*pow(n, power-1);
> }
> 
> I am looking for a way to make the function work at runtime, while 
> pow(n, 3) to be inlined as n*n*n, and pow(2, 3) to be precalculated as 
> 8. Is it possible to do this with some template trickery without having 
> to write three versions of the function? I know macros should be able to 
> do this in theory...
> 

Walter has talked about adding the keyword static in the past to 
generate templates ie:

int pow(static int n, static int power)
{

}

I'm not sure if all the params needed to be constant for it to generate 
a template.  I can't see why your proposal wouldn't work with this.

-Joel
October 07, 2008
Re: Static argument optimization
Here's a hack at least for this special case.  It probably only works for D2,
though.  Not sure if this is the kind of (extremely hackish) thing you had in
mind, but at the very least it was a fun little template puzzle.

Also, note that the pragmas are nice for figuring out what this thing is doing,
but not strictly necessary.  This hack has been through some rudimentary testing,
but nothing particularly thorough.

//CTFE can't be forward referenced.
uint runtimePow(uint n, uint power) {
   uint ret = 1;
   for(uint i = 1; i <= power; i++)
       ret *= n;
   return ret;
}

uint pow(alias n, alias power)() {
   static if(__traits(compiles, test!(n)) && __traits(compiles, test!(power))) {
       pragma(msg, "fully static");
       static const uint ret = runtimePow(n, power);  //CTFE
       return ret;  //Almost surely will be inlined, constant folded.
   } else static if(__traits(compiles, test!(power))) {
       pragma(msg, "partially static");
       pragma(msg, raiseToConstPow!(n, power));
       mixin("return " ~ raiseToConstPow!(n, power));  //Again, inlined.
   } else {
       pragma(msg, "runtime");
       return runtimePow(n, power);
   }
}

template raiseToConstPow(alias n, uint power) {
   static if(power == 0) {
       //Compiler should optimize out the last * 1.
       const char[] raiseToConstPow = "1;";
   } else {
       const char[] raiseToConstPow = "n * " ~ raiseToConstPow!(n, power - 1);
   }
}

template test(uint foo) {
   const uint bar = runtimePow(foo, foo);
}
October 07, 2008
Re: Static argument optimization
On Tue, 07 Oct 2008 03:00:38 +0300, dsimcha <dsimcha@yahoo.com> wrote:

>
> Am I missing something, or is the much bigger problem here that you're  
> using
> non-tail recursion when iteration would be much more efficient (and less  
> likely to
> overflow the stack)?

Yeah, power is just an example. In real-life cases, I have non-recursive  
functions that take several arguments and do various calculations with  
them.

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com
October 07, 2008
Re: Static argument optimization
On Tue, 07 Oct 2008 07:24:05 +0300, dsimcha <dsimcha@yahoo.com> wrote:

> Here's a hack at least for this special case.  It probably only works  
> for D2,
> though.  Not sure if this is the kind of (extremely hackish) thing you  
> had in
> mind, but at the very least it was a fun little template puzzle.

That looks like a nice start, thanks. Now, to write a CTFE-mixin to  
generate such templates for any function signature... :P

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com
October 07, 2008
Re: Static argument optimization
On Tue, 07 Oct 2008 04:32:07 +0300, Janderson <ask@me.com> wrote:

> Walter has talked about adding the keyword static in the past to  
> generate templates ie:
>
> int pow(static int n, static int power)
> {
>
> }
>
> I'm not sure if all the params needed to be constant for it to generate  
> a template.  I can't see why your proposal wouldn't work with this.

Thanks. Is this still planned to be implemented?

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com
October 07, 2008
Re: Static argument optimization
Janderson wrote:
> Vladimir Panteleev wrote:
>> Hello,
>>
>> Often I encounter cases where I have a function taking some arguments, 
>> and I'd like for the compiler to generate separate code for the 
>> function when some of the arguments are known at compile time. For 
>> example, consider this function:
>>
>> int pow(int n, int power)
>> {
>>     return power==0 ? 1 : n*pow(n, power-1);
>> }
>>
>> I am looking for a way to make the function work at runtime, while 
>> pow(n, 3) to be inlined as n*n*n, and pow(2, 3) to be precalculated as 
>> 8. Is it possible to do this with some template trickery without 
>> having to write three versions of the function? I know macros should 
>> be able to do this in theory...
>>
> 
> Walter has talked about adding the keyword static in the past to 
> generate templates ie:
> 
> int pow(static int n, static int power)
> {
> 
> }
> 
> I'm not sure if all the params needed to be constant for it to generate 
> a template.  I can't see why your proposal wouldn't work with this.
> 
> -Joel

No, they don't all need to be constant. The classic example is a regexp, 
where the regexp itself is a literal, but the other parameters are all 
variables.
October 07, 2008
Re: Static argument optimization
dsimcha:
> It probably only works for D2, though.
> ...
> uint pow(alias n, alias power)() {
>     static if(__traits(compiles, test!(n)) && __traits(compiles, test!(power))) {
...

Are there ways in D1 to know if a given value is a compile time constant or a runtime variable?

Bye,
bearophile
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home