[ACCEPTED]-Calculating vs. lookup tables for sine value performance?-signal-processing

Accepted answer
Score: 22

Update: read through to the end. It looks like the lookup table is faster than Math.Sin after all.

I would guess that the lookup approach would 51 be faster than Math.Sin. I would also say 50 that it would be a lot faster, but Robert's answer 49 made me think that I would still want to 48 benchmark this to be sure. I do a lot of 47 audio buffer processing, and I've noticed 46 that a method like this:

for (int i = 0; i < audiodata.Length; i++)
{
    audiodata[i] *= 0.5; 
}

will execute significantly 45 faster than

for (int i = 0; i < audiodata.Length; i++)
{
    audiodata[i] = Math.Sin(audiodata[i]);
}

If the difference between Math.Sin 44 and a simple multiplication is substantial, I 43 would guess that the difference between 42 Math.Sin and a lookup would also be substantial.

I 41 don't know, though, and my computer with 40 Visual Studio is in the basement, and I'm 39 too tired to take the 2 minutes it would 38 take to determine this.

Update: OK, it took more 37 than 2 minutes (more like 20) to test this, but 36 it looks like Math.Sin is at least twice as fast as a lookup table (using a Dictionary). Here's 35 the class that does Sin using Math.Sin or 34 a lookup table:

public class SinBuddy
{
    private Dictionary<double, double> _cachedSins
        = new Dictionary<double, double>();
    private const double _cacheStep = 0.01;
    private double _factor = Math.PI / 180.0;

    public SinBuddy()
    {
        for (double angleDegrees = 0; angleDegrees <= 360.0; 
            angleDegrees += _cacheStep)
        {
            double angleRadians = angleDegrees * _factor;
            _cachedSins.Add(angleDegrees, Math.Sin(angleRadians));
        }
    }

    public double CacheStep
    {
        get
        {
            return _cacheStep;
        }
    }

    public double SinLookup(double angleDegrees)
    {
        double value;
        if (_cachedSins.TryGetValue(angleDegrees, out value))
        {
            return value;
        }
        else
        {
            throw new ArgumentException(
                String.Format("No cached Sin value for {0} degrees",
                angleDegrees));
        }
    }

    public double Sin(double angleDegrees)
    {
        double angleRadians = angleDegrees * _factor;
        return Math.Sin(angleRadians);
    }
}

And here's the test/timing 33 code:

SinBuddy buddy = new SinBuddy();

System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
int loops = 200;

// Math.Sin
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.Sin(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

// lookup
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0;
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.SinLookup(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

Using a step value of 0.01 degrees 32 and looping through the full range of values 31 200 times (as in this code) takes about 30 1.4 seconds using Math.Sin, and about 3.2 29 seconds using a Dictionary lookup table. Lowering 28 the step value to 0.001 or 0.0001 makes 27 the lookup perform even worse against Math.Sin. Also, this 26 result is even more in favor of using Math.Sin, since 25 SinBuddy.Sin does a multiplication to turn 24 the angle in degrees into the angle in radians 23 on every call, while SinBuddy.SinLookup 22 just does a straight lookup.

This is on a 21 cheap laptop (no dual cores or anything 20 fancy). Robert, you da man! (But I still 19 think I should get the check, coz I did 18 the work).

Update 2: It turns out stopping and restarting 17 the Stopwatch doesn't reset the elapsed 16 milliseconds, so the lookup only seemed 15 half as fast because it's time was including 14 the time for the Math.Sin calls. Also, I 13 reread the question and realized you were 12 talking about caching the values in a simple 11 array, rather than using a Dictionary. Here 10 is my modified code (I'm leaving the old 9 code up as a warning to future generations):

public class SinBuddy
{
    private Dictionary<double, double> _cachedSins
        = new Dictionary<double, double>();
    private const double _cacheStep = 0.01;
    private double _factor = Math.PI / 180.0;

    private double[] _arrayedSins;

    public SinBuddy()
    {
        // set up dictionary
        for (double angleDegrees = 0; angleDegrees <= 360.0; 
            angleDegrees += _cacheStep)
        {
            double angleRadians = angleDegrees * _factor;
            _cachedSins.Add(angleDegrees, Math.Sin(angleRadians));
        }

        // set up array
        int elements = (int)(360.0 / _cacheStep) + 1;
        _arrayedSins = new double[elements];
        int i = 0;
        for (double angleDegrees = 0; angleDegrees <= 360.0;
            angleDegrees += _cacheStep)
        {
            double angleRadians = angleDegrees * _factor;
            //_cachedSins.Add(angleDegrees, Math.Sin(angleRadians));
            _arrayedSins[i] = Math.Sin(angleRadians);
            i++;
        }
    }

    public double CacheStep
    {
        get
        {
            return _cacheStep;
        }
    }

    public double SinArrayed(double angleDegrees)
    {
        int index = (int)(angleDegrees / _cacheStep);
        return _arrayedSins[index];
    }

    public double SinLookup(double angleDegrees)
    {
        double value;
        if (_cachedSins.TryGetValue(angleDegrees, out value))
        {
            return value;
        }
        else
        {
            throw new ArgumentException(
                String.Format("No cached Sin value for {0} degrees",
                angleDegrees));
        }
    }

    public double Sin(double angleDegrees)
    {
        double angleRadians = angleDegrees * _factor;
        return Math.Sin(angleRadians);
    }
}

And 8 the test/timing code:

SinBuddy buddy = new SinBuddy();

System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
int loops = 200;

// Math.Sin
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.Sin(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

// lookup
timer = new System.Diagnostics.Stopwatch();
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0;
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.SinLookup(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

// arrayed
timer = new System.Diagnostics.Stopwatch();
timer.Start();
for (int i = 0; i < loops; i++)
{
    for (double angleDegrees = 0; angleDegrees <= 360.0;
        angleDegrees += buddy.CacheStep)
    {
        double d = buddy.SinArrayed(angleDegrees);
    }
}
timer.Stop();
MessageBox.Show(timer.ElapsedMilliseconds.ToString());

These results are quite 7 different. Using Math.Sin takes about 850 6 milliseconds, the Dictionary lookup table 5 takes about 1300 milliseconds, and the array-based 4 lookup table takes about 600 milliseconds. So it appears that a (properly-written [gulp]) lookup table is actually a bit faster than using Math.Sin, but 3 not by much.

Please verify these results 2 yourself, since I have already demonstrated 1 my incompetence.

Score: 17

It used to be that an array lookup was a 6 good optimization to perform fast trig calculations.

But 5 with cache hits, built-in math coprocessors 4 (which use table lookups) and other performance 3 improvements, it might be best to time your 2 specific code yourself to determine which 1 will perform better.

Score: 8

For performance questions, the only right 11 answer is the one you reach after testing. But, before 10 you test, you need to determine whether 9 the effort of the test is worth your time 8 - meaning that you've identified a performance 7 issue.

If you're just curious, you can easily 6 write a test to compare the speeds. However, you'll 5 need to remember that using memory for the 4 lookup table can affect paging in larger 3 apps. So, even if paging is faster in your 2 small test, it could slow things down in 1 a larger app that uses more memory.

Score: 2

The answer to this depends entirely on how many values are in your lookup table. You say "the domain is between 0.01 and 360.01", but you don't say how many values in that range might be used, or how accurate you need the answers to be. Forgive me for not expecting to see significant 41 digits used to convey implicit meaning in 40 a non-scientific context.

More information 39 is still needed to answer this question. What 38 is the expected distribution of values between 37 0.01 and 360.01? Are you processing a lot 36 of data other than the simple sin( ) computation?

36000 35 double precision values takes over 256k 34 in memory; the lookup table is too large 33 to fit in L1 cache on most machines; if 32 you're running straight through the table, you'll 31 miss L1 once per sizeof(cacheline)/sizeof(double) accesses, and 30 probably hit L2. If, on the other hand, your 29 table accesses are more or less random, you 28 will be missing L1 almost every time you 27 do a lookup.

It also depends a lot on the 26 math library of the platform that you're 25 on. Common i386 implementations of the 24 sin function, for example, range from ~40 23 cycles up to 400 cycles or even more, depending 22 on your exact microarchitecture and library 21 vendor. I haven't timed the Microsoft library, so 20 I don't know exactly where the C# Math.sin 19 implementation would fall.

Since loads from 18 L2 are generally faster than 40 cycles on 17 a sane platform, one reasonably expects 16 the lookup table to be faster considered 15 in isolation. However, I doubt you're computing 14 sin( ) in isolation; if your arguments to 13 sin( ) jump all over the table, you will 12 be blowing other data needed for other steps 11 of your computation out of the cache; although 10 the sin( ) computation gets faster, the 9 slowdown to other parts of your computation 8 may more than outweigh the speedup. Only 7 careful measurement can really answer this 6 question.

Am I to understand from your other 5 comments that you're doing this as part 4 of a FFT computation? Is there a reason 3 that you need to roll your own FFT instead 2 of using one of the numerous extremely high 1 quality implementations that already exist?

Score: 2

Since you mention Fourier transforms as 11 an application, you might also consider 10 to compute your sines/cosines using the 9 equations

sin(x+y) = sin(x)cos(y) + cos(x)sin(y)

cos(x+y) = cos(x)cos(y) - sin(x)sin(y)

I.e. you 8 can compute sin(n * x), cos(n * x) for n 7 = 0, 1, 2 ... iteratively from sin((n-1) * x), cos((n-1) * x) and 6 the constants sin(x), cos(x) with 4 multiplications. Of 5 course that only works if you have to evaluate 4 sin(x), cos(x) on an arithmetic sequence.

Comparing 3 the approaches without the actual implementation 2 is difficult. It depends a lot on how well 1 your tables fit into the caches.

Score: 1

Math.Sin is faster. The people who wrote 7 are smart and use table lookups when they 6 are accurate and faster and use the math 5 when that is faster. And there's nothing 4 about that domain that makes it particularily 3 faster, the first thing most trig function 2 implementations do is to map down to a favorable 1 domain anyway.

Score: 1

Sorry for grave digging, but there is a 8 good solution for how to make quick indexing 7 of lookup tables: https://jvm-gaming.org/t/fast-math-sin-cos-lookup-tables/36660

It's in Java, but it takes 6 only a few minutes to port it to C#. I did 5 tests and got the following results with 4 100000 iterations:

Math.Sin: 0.043 sec
Mathf.Sin: 0.06 sec (Unity`s Mathf lib)
MathTools.Sin: 0.026 (lookup tables static class).

Probably in Java it will 3 give 50x boost (or it did in 2011 lol, but 2 in C# in 2021 the difference is about 2x 1 only).

Score: 0

As you may have thousands of values in your 7 lookup table, what you may want to do is 6 have a dictionary, and when you calculate 5 a value, put it in the dictionary, so you 4 only calculate each value one time, and 3 use the C# function to do the calculation.

But, there 2 is no reason to recalculate the same value 1 over and over.

More Related questions