Thread overview | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vladimir Panteleev | "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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vladimir Panteleev | == 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vladimir Panteleev | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vladimir Panteleev | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to dsimcha | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to dsimcha | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Janderson | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Janderson | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to dsimcha | 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
|
Copyright © 1999-2021 by the D Language Foundation