NOTE: Accidentally put this here instead of under "Programming Questions"... might want to move it...

After some experimenting I've deduced that the following is the fastest way to implement sine/cosine tables through a function that is interchangeable with the built-in sin() and cos() functions included in MATH.H.

// NOTE: Code to build sine table not included in this excerpt.

#define SIN_TABLE_SIZE    4096
#define SIN_TABLE_BITMASK  4095

double _sin_t[SIN_TABLE_SIZE];

double Get_SinT (double d)
{
  return _sin_t[(int)(d * 651.8986469f) & SIN_TABLE_BITMASK];
}

My tests showed this routine to be almost twice as fast as the normal sin() function with no compiler optimizations enabled.

Does anyone have any ideas how to make this even faster, or is that about as fast as it's going to get while still being compatible with radians?

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Didn't most newer CPU's have special instruction that returned sin/cos value from HW table? I think I saw something about it in the Intel architecture manuals.

orz: I tired implementing your code in place of the integer type-casting. There was a calculable drop in speed. My benchmark (100,000,000 sin-table operations with no compiler optimizations) went from about 4.5 seconds to complete its calculations to 6 seconds. Though that's still better than the 7.8 seconds the regular sin() and cos() routines take.

In case it makes a difference (since your code was assembler after all) I am using MSVC 6.0 under Windows 98SE. My processor is an AMD Sempron 2.0 GHz.

And I'm only using doubles because the sin() and cos() routines do. I plan to switch to regular floats when I add this to my game engine.

tobing: I always prefer to do things myself. A testament to that is the random number generator I made which I use in my games.

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Uh-oh. Good luck with that. I would go nowhere, if I had to do all for myself, without relying on powerful libraries, allegro being just one of many. I would also not be keen to write my own compiler, os etc...

HoHo:

1. MSVC vs. GCC is one of those arguments I am not going to be dragged into. It's like comparing MS Word to Wordperfect.

2. sinf() benchmarks at about 11 seconds using my program... worse than sin().

3. All my benchmark program is is a for-loop and the command who's speed I wish to test, being assigned to a variable. My program doesn't actually do the timing part, I time it myself using a stopwatch a few times then figure out the average. It was faster to program that way and at the time, I wanted it programmed in a few minutes using the console instead of a half hour using Allegro's timer functions.

tobing:

Well, obviously I use Allegro, but the only thing stopping me from learning to write my own library of functions is the fact that I don't have access to enough variations of computers to test such an implementation, whereas Allegro has been through its paces on so many computers I've never heard of my games crashing horribly on anyone's system due to Allegro's fault. (Let alone my own actually.)

orz:

MSVC is optimizing the area of my benchmark that is just a fixed command over and over to only process once, thus no matter how many times I loop for, it's only taking a split second to execute with either the built-in commands or the table commands, thus it's making it impossible for me to figure out how my functions will work when optimized.

--- Kris Asick (Gemini)
--- http://www.pixelships.com

The problem is that your code is written in such way that discarding your calls is legal for the compiler, because your calls don't actually do anything except set a variable which is never looked at. The trick is to do something such that the code cannot behave correctly without calling your function the correct number of times. Trying adding up all return values and printing the sum. This is a sample of the code I benchmarked with:

  sum = 3.1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 1000; j++) {
      sum += sinf(sum);
      sum += sinf(sum);
      sum += sinf(sum);
      sum += sinf(sum);
    }
  }
  double time4 = get_time2();
  double dt3 = (time4 - time3) / (n * 4000.0) * 1000000;
  printf("algorithm3: %.3f ns / sin; (check:%.9f)\n", dt3, sum);

It's not just MSVC vs GCC. MSVC 6.0 is old, and extremely buggy if you use C++ templates beyond STL. If you don't use C++ templates, it's probably adequate. MSVC 7.1 is much less buggy in that regard, as are most recent and semi-recent versions of GCC. edit: more recent MSVCs and GCCs are also faster than MSVC 6.0

edit: just for fun, this is the output of my current code:

                                Get_SinT 27.525 ns / call; (check:2.510948387)
                      get_sin_via_table2 18.895 ns / call; (check:1.646245552)
   get_sin_via_table2_with_interpolation 34.012 ns / call; (check:2.000266046)
                                   _sinf 74.413 ns / call; (check:2.000186454)
                                     sin 84.446 ns / call; (check:2.000186454)
                                _fsincos 95.225 ns / call; (check:2.000186454)

I've modified it to make imprecisions in the results more obvious in the "check" value, and to simplify the code and make the output more readable. Notice how the top two (your original code and a modification of it to use inline assembly float->int conversion) produce large deviations, while the interpolating version (which also uses asm float->int) produces small deviations, and the remaining three produce identical results? Also notice that _fsincos is only slightly slower than sin despite calculating both sin and cos.

Not trying to derail your thread Kris, but...

I recently attempted to switch from MSVC6 to the latest mingw32 package. My current game which uses a lot of sin/cos and software polygon rendering experienced a noticeable drop in framerate, in the neighbourhood of 10FPS, with mingw32.

Otherwise, the switch went well, using MinGW Visual Studio which is a lot like MVC6.

Unless I can see some metrics on the supposed superiority of mingw32 over MSVC6, and an explanation on how to access this superior performance, I'll be sticking with MSVC6.

STL and C++ I avoid like the plague anyway, so MSVC6 works perfectly fine.

Kris Asick:
With tables size 16384 instead of 4096:

                                Get_SinT 26.865 ns / call; (check:2.141740928)
                      get_sin_via_table2 18.751 ns / call; (check:1.982911766)
   get_sin_via_table2_with_interpolation 33.851 ns / call; (check:2.000186454)
                                   _sinf 72.959 ns / call; (check:2.000186454)
                                     sin 85.588 ns / call; (check:2.000186454)
                                _fsincos 96.583 ns / call; (check:2.000186454)

The deviations by this measure got noticably smaller. In fact, for the interpolating version, the deviation disappeared. But, I am not a believe in large table sizes, at least for general purpose things; they may do fine on benchmarks until they start overflowing the cache, but in real world circumstances there's other stuff that wants a share of the cache too.

ppridham: edit: why does this showing up on the wrong line if I don't add a spurious space?
I only see bugs in MSVC 6 when using C++; for C it seems to produce correct code. I do find GCC 3.3.x faster than MSVC 6 in most, though not all, cases. I haven't tried GCC 4.* yet. In a complete program the comparison may be more difficult than in a simpler benchmark due to libraries complicating the picture.

Bob:

edit: corrected these results, and the description; a bug initially had the table based stuff performing better
It's comparable to the normal sin()/cos() in that regard. Except the interpolating version I wrote, which barfs after a bit; but perhaps that's fixable. A version modified to show check values with various biases applied:
zero bias:

                                Get_SinT   29.411 ns / call; check:1.015412770
                      get_sin_via_table2   22.424 ns / call; check:0.738985208
   get_sin_via_table2_with_interpolation   36.800 ns / call; check:0.778233193
                                     sin   89.889 ns / call; check:0.778233193

bias: PI * 256

                                Get_SinT   31.876 ns / call; check:1.015412770
                      get_sin_via_table2   23.182 ns / call; check:0.738985208
   get_sin_via_table2_with_interpolation   39.232 ns / call; check:0.778233193
                                     sin   92.577 ns / call; check:0.778233193

bias: PI * 65536

                                Get_SinT   29.303 ns / call; check:1.015412770
                      get_sin_via_table2   22.898 ns / call; check:0.738985208
   get_sin_via_table2_with_interpolation   36.886 ns / call; check:0.778233179
                                     sin   93.601 ns / call; check:0.778233353

bias: PI * 4294967296

                                Get_SinT   29.197 ns / call; check:0.962381428
                      get_sin_via_table2   22.253 ns / call; check:4.964428596
   get_sin_via_table2_with_interpolation   36.993 ns / call; check:-1.#IND00000
                                     sin   98.563 ns / call; check:0.789689926

bias: PI * 1099511627776

                                Get_SinT   29.090 ns / call; check:0.956744473
                      get_sin_via_table2   22.055 ns / call; check:4.964428596
   get_sin_via_table2_with_interpolation   37.330 ns / call; check:-1.#IND00000
                                     sin  100.243 ns / call; check:3.776719549

bias: PI * 281474976710656

                                Get_SinT   29.282 ns / call; check:2.899386226
                      get_sin_via_table2   22.070 ns / call; check:4.964428596
   get_sin_via_table2_with_interpolation   37.951 ns / call; check:-1.#IND00000
                                     sin  103.442 ns / call; check:-4.451114322

I don't have the code here on this computer, but you can multiply the number by some magic value and grab the int off the mantissa and mask off the fp exponent & sign bits. If this doesn't allow enough range, you can cast to a double to get more accuracy. (store to double is still faster than fistp)

Using a particular compiler can be like using a particular language, you have to know your way around to get best performance. Did you try -ffast-math, -fomit-frame-pointer, -O3, -march=pentium4, -fpumath=sse,387, and countless others? I haven't been able to outrun (within 2%) Mingw 3.42 with the free VC++ download thing if I spent a half hour on a particular program.

Even the fpu sin/cos functions have limits, huge to be sure, but there nonetheless.

Indeed. And I forgot to make sure my memory accesses were unpredictable. My performance numbers were based upon the assumption that memory access mostly went to the L1 (though, on an Athlon-based system, L1 is big enough to fit decent tables; on an intel system IIRC L1 is generally smaller but the speed hit for dropping to L2 is a lot better). Unfortunately, it's hard to make sure it can't prefetch my memory without sticking in frequent random number generator calls, which slows things down a bit independantly of the trig speed.

I don't really like that method, as the behavior is kinda stupid when the input goes outside of the intended range. But, it does seem to improve speed a little more.

#elif defined USE_BINARY_FLOAT_CONVERSION
#  define BIGDOUBLE 6755399441055744.0
  int iround(double a) {
    int i;
    a = a + (BIGDOUBLE + 0);
    i = *((int*)&a);
    return i;
  }

Done. Be warned though, this is kinda a mess that was quickly assembled from pieces of several different projects. There's a ton of code you'll just want to skip over to get to the relevant stuff.

edit: The output on my computer from the code as posted:

                                   dummy    5.672 ns / call; check:2.1907804172
                                Get_SinT   33.177 ns / call; check:1.7299634784
                      get_sin_via_table2   23.802 ns / call; check:1.7279857059
        get_sin_via_table2_binary_iround   18.555 ns / call; check:1.7279857059
   get_sin_via_table2_with_interpolation   36.615 ns / call; check:1.7273836151
                                   _sinf   61.737 ns / call; check:1.7273835937
                                     sin   71.317 ns / call; check:1.7273835937
                                _fsincos   82.553 ns / call; check:1.7273835937

Dummy does nothing except the overhead - it calls the random number generator, adds things up, but no sin/cos stuff.
The table sizes are set to 65536.
Get_SinT is the original code (except for the table size).
get_sin_via_table2 is that modified to use asm float->int conversion
get_sin_via_table2_binary_iround is that modified to use binary float->int conversion (reinterpret the floating point memory as integers w/ silly tricks)
get_sin_via_table2_with_interpolation uses the asm float->int, and interpolates between two entries in the table for high accuracy
_sinf calls sinf
sin is just plain sin() from the standard library
_fsincos uses inline asm to call the fsincos opcode

The timing numbers in the last set include plenty of L1 misses. It doesn't include many L2 misses though, as even the 256 kilobyte table fits into the L2 cache footprint. The L1 miss rate is worse than real world in most cases, since it's largely based upon randomly generated angles. The L2 miss rate is better than real world in most cases, since no major other program data is used simultaneously. If you want a graph of log(table size) vs performance ala linpack you could simply adjust the table size and run again a few times.