Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a way to specialize a function between compile time and run time?

With constexpr, A function can be evaluated at compile time or runtime depending upon the arguments. But usually, the algorithm has to be different between compile time and runtime. Eg. Consider the constexpr version of factorial.

constexpr int fact(int n)
{
return (n)?n*fact(n-1):1;
}

If n happens be at runtime wont the function be inefficient than one forloop? Is there some template magic to determine if the function is being executed at compile time or run time and use different algorithm?

Update:
factorial was just an example. Is all constexpr functions be as efficient as they would be if coded without constexpr restrictions? Eg:

constexpr int combinations(int n, int k)
{
//Assume all error conditions and edge conditions are taken care with ternary operator ?:
return fact(n)/(fact(k)*fact(n-k);
}

If the function is written in runtime, it can benefit from Memoization. Even this was possible, I guess it will be difficult to express the function such that it is both constexpr and also as efficient as possible in runtime.

like image 454
balki Avatar asked Jan 18 '13 07:01

balki


1 Answers

No, as far as I know you can't detect how the compiler is using the function in a given call, or direct the compiler to use different implementations depending on constness.

But first of all, a constexpr function is restricted to a single return statement, which means that the compiler can (most often) easily apply tail recursion optimization, turning a recursive call into a loop. Thus, this question is about how to do premature optimization, which is not a good idea. Low level optimization is the compiler's job: let it.

Secondly, if you really really want to do the compiler's job then you can just name the functions, instead of trying to senselessly cram two different function implementations into a single one. For what purpose would that serve? Only obscurity.


For the particular example given,

constexpr int fact(int n)
{
    return (n)?n*fact(n-1):1;
}

the compiler has to recognize that it can be rewritten as tail-recursive. As I recall from my testing for an earlier SO question about it, even the Visual C++ compiler does that. Although for some inexplicable reason (possibly having to do with the original x86 processor design) it was stumped by use of floating point type: same high level logic, different low level result.

As a slightly less drastic help-the-compiler work effort, after having measured and found that this function is the one that makes your app unacceptably slow, and after having inspected the machine code and found that the compiler fails to recognize the function's tail-recursiveness, you can rewrite it as follows:

constexpr int fact( int multiplier, int n )
{
    return (n != 0? fact( multiplier*n, n-1 ) : multiplier);
}

constexpr int fact( int n )
{
    return fact( 1, n );
}

Disclaimer: code not touched by compiler's dirty hands.

like image 134
Cheers and hth. - Alf Avatar answered Sep 17 '22 15:09

Cheers and hth. - Alf