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 bearophile <bearophileHUGS lycos.com> writes:
Vladimir Panteleev:

 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.


That's named partial compilation, in this newsgroup I have discussed it a
little in the past:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=75312

Bye,
bearophile
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 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
next 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 :)


  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



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 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 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