Friday, May 13, 2016

C# math is fast

I was reading an article on neural networks that mentioned the usual sigmoid activation function when the inputs are real numbers in the [0, 1) interval:

1 / (1 + e−x)

The article mentions that this is probably where the program would spend at least half of its time so I thought "why not pre-compute a bunch of values and trade memory and precision for time"? It turns out, C# math is quite fast and the gain might not be worth it. (I haven't tested it yet with a NN.)

This is the code I wrote to benchmark the two options, using LinqPad 5:

void Main()
{
    const int STEPS = 1 * 1000 * 1000;
    
    Func<double, double> activation = x => 1.0 / (1.0 + Math.Exp(-x));
    var cache = Precompute(0.0, 1.0, STEPS, activation);
    
    Benchmark("Using the cache", x => cache[(int) Math.Truncate(x * STEPS)]);
    Benchmark("Calling the function each time", activation);
}

double[] Precompute(double lower, double upper, int steps, Func<double, double> func)
{
    var result = new List<double>();
    
    For(0.0, 1.0, 1.0 / steps, value => result.Add(func(value)));
    
    return result.ToArray();
}

void Benchmark(string message, Func<double, double> func)
{
    const int COUNT = 100 * 1000 * 1000;
    
    var dummy = 0.0;
    var ts = ComputeBenchmark(() => For(0.0, 1.0, 1.0 / COUNT, value => dummy += func(value)));
    
    Console.WriteLine(message + ": " + ts + " - sum = " + dummy);
}

void For(double lower, double upper, double increment, Action<double> action)
{
    for (var value = lower; value <= upper; value += increment)
        action(value);
}

TimeSpan ComputeBenchmark(Action action)
{
    var sw = new Stopwatch();
    sw.Start();
    
    action();
    
    sw.Stop();
    return sw.Elapsed;
}

These are the results; using the cache takes about 70% of the time required when calling the function every time, at the expense of several MB of memory and some loss of precision. In a large NN, where billions of evaluations are expected in training, the trade-off might be worth it. I don't yet have enough experience to decide.

Using the cache: 00:00:01.9850792 - sum = 62011439.025702
Calling the function each time: 00:00:02.7755272 - sum = 62011450.5899971

As a side-note, I have computed and printed the sum to avoid the compiler from optimizing away the function calls; I don't know if LinqPad would do that but I wanted to avoid it just in case.