[ros-dev] Speed Tests (was: ping Alex regarding log2() for scheduler)

[Alex Ionescu]

Ash wrote:

> Hello,
>
> I'd like to provide a small VS.NET project file with 5 different tests.
>
> - 46ffffe9 tells everything is alright with the function calculation
> - times are measured with QueryPerformanceCounter
> - loop run cnt: 0x2ffffff
>
> result orig function            46ffffe9
> it took         1491052
> result orig function inlined    46ffffe9
> it took         1035547
> result second proposal inlined  46ffffe9
> it took         1244434
> result optimized asm            46ffffe9
> it took         1338367
> result debug asm                46ffffe9
> it took         8774815
>
> The second proposal is the original proposal but more shifts - still 
> slower tho.
>
> Interesting is the inlined version generated by MSVC, shaving off 
> almost 1/3 of the overall time.
> Also stared as "optimized asm" - no gurantee on register safety tho ;)
>
> For portability and performance sake it should be considered to create 
> a compiler macro.
> This function is terribly small, any optimisations inside are 
> outweighted by the calling overhead in this case.
> The most impressive one is the original function inlined, althought 
> the ASM would only work on x86.
>
> Please do not think about using 64k tables, thats what, 1/2 of a 
> Sempron L2 cache?
> It would really really trash performance.

Hi Ash,

Thanks a lot for your tests. I don't have much time tonight, but if 
you'd like/can, can you add two more tests?

One using "bsr", the intel opcode. It does all the work for you and 
returns the index.

i think it's as simple as "bsr ecx, eax" where "ecx" is the mask and eax 
is the returned index. Or it might be backwards.

The second test is using a 256-byte log2 table:

const char LogTable256[] = 
{
  0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};


and a lookup code like this:

Addon = 16;
if ((IntMask = Mask >> 16)) {
     Addon = 0;
     IntMask = Mask;
}
if (IntMask && 0xFFFFFF00) {
     Addon += 8;
}
HighBit = LogTable256[(Mask >> Addon)] + Addon;