Fun With Expressions and Math.Pow

Yesterday I hinted at an expression I had evolved from the original "x ^ 3" was actually quicker when it unrolled the power to "x * x * x" (more or less). I spent some time this morning whipping up a program to investigate this a bit further.

First, I created two functions to create a function on the fly. One uses Math.Pow() directly, and the other creates an expression that multiplies the parameter value to itself enough times to give the same result that a Math.Pow() call would give:

private static Func<double, double> CreatePowerExpression(int exponent)
{
    var parameter = Expression.Parameter(typeof(double), "x");
    var body = Expression.Call(typeof(Math).GetMethod("Pow"), parameter, 
        Expression.Constant((double)exponent, typeof(double)));
    return Expression.Lambda<Func<double, double>>(body, parameter).Compile();
}

private static Func<double, double> CreateUnrolledExpression(int exponent)
{
    var parameter = Expression.Parameter(typeof(double), "x");
    Expression body = parameter;

    for(var i = 1; i < exponent; i++)
    {
        body = Expression.Multiply(body, parameter);
    }

    return Expression.Lambda<Func<double, double>>(body, parameter).Compile();
}

Then I call these two functions the same amount of times with an ever-increasing exponent value. When each loop is done, I compare the time it took for both to finish, and I terminate the program when the unrolled implementation is slower than the power one:

private const double Iterations = 10000000d;

static void Main(string[] args)
{
    var powerTime = TimeSpan.Zero;
    var unrolledTime = TimeSpan.Zero;
    var exponent = 1d;

    do
    {
        var powerFunc = Program.CreatePowerExpression((int)exponent);
        powerTime = new Action(() =>
        {
            for(var i = 0d; i < Program.Iterations; i++)
            {
                powerFunc(i);
            }
        }).Time();

        var unrolledFunc = Program.CreateUnrolledExpression((int)exponent);
        unrolledTime = new Action(() =>
        {
            for(var i = 0d; i < Program.Iterations; i++)
            {
                unrolledFunc(i);
            }
        }).Time();

        Console.Out.WriteLine("Exponent: {0}", exponent);
        Console.Out.WriteLine("Power Time: {0}", powerTime);
        Console.Out.WriteLine("Unrolled Time: {0}", unrolledTime);
        Console.Out.WriteLine();

        exponent++;    
    } while(unrolledTime < powerTime);
}

On my computer, the magic crossover number for the exponent is somewhere around 64 - i.e. that's when unrolling the power function isn't the best option anymore.

This was just playing around and having fun with the Expressions API, which I love, love, love. Oh, and if you know you're going to do something like "x ^ 30" in your code, you may want to unroll it (although the function size will be bigger - there's always tradeoffs, right?).

You can get the source code here.

* Posted at 06.30.2010 10:44:22 AM CST | Link *

Blog History