Thread: Optimizing code

But if sqrt with a double is 27 cycles, then even an L2 lookup is gong to be significantly faster? Am I likely to hit L3 using a 250,000 value lookup table?

Come to think of it actually, the data will be weighted toward the low end of the data, so maybe only putting a table for the first 2/3 of the values would work. That means ifs though, which would probably slow it down even more. Blarg.

If you have no other data to read/write, then L2 cache is probably big enough to hold 250000 entries - but you don't JUST read a value from the L2 cache, you need to do a little bit of math on it as well, I think? And that's where it gets hard to beat the sqrt instruction itself.

L3 cache is, I guess, somewhere halfway between RAM and L2 cache in access time - if your system HAS a L3 cache, that is.

--
Mats

All I need to do after I get the value from the table is add 0.5 and cast it to an int - it then becomes the index for an array. But I had to do that to the sqrt as well, so no, the lookup is the only operation that would be replacing the sqrt.

There is lots of other data to though - a 10,000-100,000 by 3 aarray of doubles with x,y,z coorrdinates, and two other arrays that are negligible by comparison.

So, I would expect that there's little you can do about it.

You could, I suppose, make a "2 sqrt at once" using SSE, if you don't mind doing some inline assembler - you probably have to do the rest of the math in SSE inline assembler too, but it doesn't sound like you have a HUGE amount of code.

Seeing as the SQRTPD does it's job in 27 clock-cycles, it's the same amount of time for TWO square roots at once as it is for doing the single square root, and this rule applies to almost all other SSE instructions too, it would probably be possible to do twice as much processing in the same amount of time [subject to running into the memory throughput limit].

--
Mats

Code:

index = (int) (sqrt(y) + 0.5)

take sqrt of y, round to nearest int

I guess I could make the lookup table a table of ints, where

Code:

 table[i] = (int) (sqrt(i) + 0.5)

And that might save time. Thing is, using the nearest integer as an approximation to the square root only gives 1 decimal place accuracy for relatively large numbers. So I would probably have to make the lookup table go by 0.5's or even 0.1's.

Then the code would become

Code:

index = table[(int) y]

Originally Posted by KBriggs

Code:

index = (int) (sqrt(y) + 0.5)

take sqrt of y, round to nearest int

Unless you have some weird sqrt() that returns the negative root, in which case it round the wrong way

Originally Posted by KBriggs

But if sqrt with a double is 27 cycles, then even an L2 lookup is gong to be significantly faster? Am I likely to hit L3 using a 250,000 value lookup table?

Unless you're targetting a specific machine, I don't think you should design your code with a particular cache size or cycle time in mind. This stuff changes all the time.

Even if you could fit your table into L2, that would mean that not much else would fit -- so you might end up hurting other code even though you're gaining here.

I think a simple check like:

Code:

if( x <= TABLE_MAX )
    return table_sqrt( x );
else
    return sqrt( x );

Probably won't hurt things too much. With execution speculation, the hardware sqrt() probably gets pipelined even as the condition is being checked -- if the condition passes, it simply gets cancelled. Of course, now you're filling the pipeline with bubbles, etc etc... Bust out the profiler.

Originally Posted by KBriggs

The table didn't add much, but turning on the -O3 flag for compiling actually made a pretty major difference in run time.

Optimization probably makes the difference between calling an actual function for sqrt() and using an intrinsic inline call to the FSQRT instruction.

You may want to add -ffast-math as well. It's not a guarantee, but it may help a bit.

--
Mats