www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Static argument optimization

reply "Vladimir Panteleev" <thecybershadow gmail.com> writes:
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
Oct 06 2008
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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
Oct 06 2008
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== 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)?
Oct 06 2008
parent "Vladimir Panteleev" <thecybershadow gmail.com> writes:
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
Oct 07 2008
prev sibling next sibling parent reply Janderson <ask me.com> writes:
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
Oct 06 2008
next sibling parent "Vladimir Panteleev" <thecybershadow gmail.com> writes:
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
Oct 07 2008
prev sibling next sibling parent reply Don <nospam nospam.com.au> writes:
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.
Oct 07 2008
parent reply Janderson <ask me.com> writes:
Don wrote:
 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.

That's good to know. I was thinking that something like with regexpr all parameters would be marked as static and it would pick-and-choose which are actually static/constant based on the call. Off-topic: The game I'm working on was finally announced today http://www.leagueoflegends.com/ I'm excited because I can now talk about it :)
Oct 07 2008
parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
Janderson escribió:
 Don wrote:
 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.

That's good to know. I was thinking that something like with regexpr all parameters would be marked as static and it would pick-and-choose which are actually static/constant based on the call. Off-topic: The game I'm working on was finally announced today http://www.leagueoflegends.com/ I'm excited because I can now talk about it :)

I play DOTA every lunch hour since a couple of months with some friends at work! I love it! I'll sure try it. :-)
Oct 07 2008
parent reply Janderson <ask me.com> writes:
Ary Borenszweig wrote:
 Janderson escribió:
 I'm excited because I can now talk about it :)

I play DOTA every lunch hour since a couple of months with some friends at work! I love it! I'll sure try it. :-)

That's good to hear :) I'm surprised every day by how popular DotA is. I'd never heard of it before I'd started at Riot 7months ago but instantly fell in love with LOL. Apparently there where several popular songs written about DotA. Wait, heres one I found on utube: http://www.youtube.com/watch?v=qXKd7uuehlw Now all we need is some D songs :) Oh and by the way another plug: Riotgames is still looking for a couple of talented experienced engineers with a good knowledge of C++/stl or Java. I'm hoping that one day we'll get enough D engineers to write our next game in D. http://www.riotgames.com/careers/ You can contact me or riotgames if your interested. hohums at gmail dot com -Joel
Oct 08 2008
parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Janderson wrote:
 Ary Borenszweig wrote:
 Janderson escribió:
 I'm excited because I can now talk about it :)

I play DOTA every lunch hour since a couple of months with some friends at work! I love it! I'll sure try it. :-)

That's good to hear :) I'm surprised every day by how popular DotA is. I'd never heard of it before I'd started at Riot 7months ago but instantly fell in love with LOL. Apparently there where several popular songs written about DotA. Wait, heres one I found on utube: http://www.youtube.com/watch?v=qXKd7uuehlw

Lol, a new DotA song by Basshunter, nice! :D The previous one was: http://www.youtube.com/watch?v=0OzWIFX8M-Y , still my favorite, although this new is still nice, it shows even some of "teh micro".
 Now all we need is some D songs :)
 
 Oh and by the way another plug: Riotgames is still looking for a couple 
 of talented experienced engineers with a good knowledge of C++/stl or 
 Java.  I'm hoping that one day we'll get enough D engineers to write our 
 next game in D.
 
 http://www.riotgames.com/careers/
 
 You can contact me or riotgames if your interested.
 
 hohums at gmail dot com
 
 -Joel

Cool... wish you were London based. :P -- Bruno Medeiros - Software Developer, MSc. in CS/E graduate http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 15 2008
prev sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Wed, 08 Oct 2008 12:12:50 +0400, Janderson <ask me.com> wrote:

 Ary Borenszweig wrote:
 Janderson escribió:
 I'm excited because I can now talk about it :)

friends at work! I love it! I'll sure try it. :-)

That's good to hear :) I'm surprised every day by how popular DotA is. I'd never heard of it before I'd started at Riot 7months ago but instantly fell in love with LOL. Apparently there where several popular songs written about DotA. Wait, heres one I found on utube: http://www.youtube.com/watch?v=qXKd7uuehlw Now all we need is some D songs :) Oh and by the way another plug: Riotgames is still looking for a couple of talented experienced engineers with a good knowledge of C++/stl or Java. I'm hoping that one day we'll get enough D engineers to write our next game in D. http://www.riotgames.com/careers/ You can contact me or riotgames if your interested. hohums at gmail dot com -Joel

Dota is really nice because it has incredibly high replayability and very good competitive gameplay. Yeah, I'm addicted too :) I'll try LOL for sure!
Oct 08 2008
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
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);
}
Oct 06 2008
next sibling parent "Vladimir Panteleev" <thecybershadow gmail.com> writes:
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
Oct 07 2008
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
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
Oct 07 2008