Jump to page: 1 2
Thread overview
Static argument optimization
Oct 06, 2008
Vladimir Panteleev
Oct 07, 2008
dsimcha
Oct 07, 2008
Vladimir Panteleev
Oct 07, 2008
Janderson
Oct 07, 2008
Vladimir Panteleev
Oct 07, 2008
Don
Oct 08, 2008
Janderson
Oct 08, 2008
Ary Borenszweig
Oct 08, 2008
Janderson
Oct 08, 2008
Denis Koroskin
Oct 15, 2008
Bruno Medeiros
Oct 07, 2008
dsimcha
Oct 07, 2008
Vladimir Panteleev
Oct 07, 2008
bearophile
October 06, 2008
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
"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
== 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
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
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
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
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
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
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
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