Fast Lookup Table

[ChaseRLewis]

I Created a Look_up table class but when I test it with sin() and cos() it is actually slower than stdlib math's sin. This surprises me by a lot.

inline double MATH_TABLES::GetSind(double& value)
{
	 return mp_Sind[(static_cast<int>(value/m_SinPrecisiond)];
}

mp_Sind is simply an array of doubles. This is the non-Lerp'd version and it is even slower than by an average of 1.5-2x than sin(x). I am quite surprised by this. Is there something in this code that stands out as a reason for it a table lookup being slower than a sin() function?

Test Code

const unsigned int NUMSINS = 100000;
double Sins[NUMSINS];
boost::timer Timer;
MATH_TABLES Sind;
void TestSinChart()
{
	int counter = 0;
	double time_table = 0;
	double time_reference = 0;
	Timer.restart();
	while( NUMSINS > counter++)
	{
		Sind.GetSind(Sins[counter]);
	}
	time_table = Timer.elapsed();
	counter = 0;
	Timer.restart();
	while(NUMSINS > counter++)
	{
		sin(Sins[counter]);
	}
	time_reference = Timer.elapsed();
	std::cout << "Num Tests: " << counter-1 << "\n";
	std::cout << "Table Time: " << time_table*1000 << " ms \n";
	std::cout << "Reference Time: " << time_reference*1000 << " ms\n";
}

[L7Sqr]

It might have something to do with the way you are determining your index. I'm sure sin implementations vary widely across platforms and depending on the chip support underneath, but if I run a simple test where I do the following:

for( int i = 0; i < 10000; ++i)
   for (int j = 0; j < 100000; ++j)
      double d = get_value (j);

I get wild results just by changing how the index is generated.
For

return table[i];

I get a runtime of ~8 seconds. For

return table[static_cast<int>(i/1.0)];

I get a runtime of ~12 seconds. Seems to correspond to your 1.5x claim, though that is really more likely just a coincidence.

[mrnutty]

Its probably because of the casting and such. Unless your working in a 'tight' environment, generally, forget about lookup tables.

[ChaseRLewis]

Well I'm looking into an embedded system project, that's why I was looking into lookup tables. I was going to write some a generic helper library while I wait on the chip because of Chinese New Years (Like a month from when I ordered it before they ship it).

However, I guess I'll have to do the test on the chip to determine whether it's because of code or hardware acceleration of the sin().

[mike_2000_17]

Converting a double to an integer is not a trivial operation because they are represented completely differently in binary. It is not like conversions between integer types where it's almost just a matter of changing the number of bits. Like L7Sqr has reported, I would expect the conversion from double to integer to be taking a lot of the computing time (we're only talking about a few clock-cycles here, of course). If you can get away with not using floating-point values at all (which is very common in embedded systems since many micro-controllers don't have floating-point modules on their CPU anyways, or very limited capabilities for floating-point operations), then it will be faster. If it is appropriate, consider perhaps using integers with a mapping like 1(integer) -> 0.001(floating-point) (or even a base 2 mapping) and do all your calculation with integers only and your transcendental functions with look-up tables.

And, I would expect that the code you have would be faster than the sin() on a micro-controller (if that sin() function exists).