Nearest Power of 2 quickly

[Paizo]

with recent compilers improvements do you think that assembler is still faster?
I mean that compilers can improve execution speed on differents architectures (ie amd,intel...), assembly can't be optimized by compiler (i think). just for know what you think about

[dmantione]

Oh yes, especially in this cases like this where assembler wizard tricks can be applied.

Generally, compilers do a good job, but still... FPC, Delphi, GCC, Borland C, MSVC are beaten easily by assembler programmers. There exist a few compilers that are hard to beat, for example Pathscale really kicks ass.

[dmantione]

Just for luck, this is how I implemented it.. using the suggested lookup-table.

What is the advantage over the original method? I.e. your algorithm compares with 2,4,8,16,32, which was exactly what the original did, only yours needs more memory.

[cairnswm]

Now this is how to do it with a lookup table

[pascal]
Const
Twos : Array[1..11] of LongInt = (1,2,4,8,16,32,64,128,256,512,1024);

var
N : Array[1..1024] of Integer;

procedure PreparePowerTwos;
Var
I,L : Integer;
begin
L := 1;
For I := 1 to 1024 do
Begin
If Twos[L+1] - I < I - Twos[L] then
L := L+1;
N[I] := L;
End;
end;

Function ClosestTwo(InNum : Integer) : Integer;
begin
Result := Twos[N[InNum]];
end;
[/pascal]

Seems fast

[Nitrogen]

What is the advantage over the original method? I.e. your algorithm compares with 2,4,8,16,32, which was exactly what the original did, only yours needs more memory.

Well, I never claimed it was better, just showing a different method.
But I do think it's better to "waste" a whole 52 bytes of memory rather than doing a multiply operation for every power.

But, it's still a fun exercise to think up ridiculously optimised functions, so keep em coming.

Now this is how to do it with a lookup table

Cheater!

Now that's more of a waste of memory (a whole 4.14kb *shock* *horror*).. But should run very nicely!

I should also point out that most games these days are using up to 2048x2048 textures so you actually need a massive 8.4kb of memory...

[dmantione]

What is the advantage over the original method? I.e. your algorithm compares with 2,4,8,16,32, which was exactly what the original did, only yours needs more memory.

Well, I never claimed it was better, just showing a different method.
But I do think it's better to "waste" a whole 52 bytes of memory rather than doing a multiply operation for every power.

For a real multiply, yes. But a multiply with 2 wil be translated to a "add register,register", which is one of the cheapest operations in the CPU. Luckily a table lookup is in general as fast, unless you have a cache miss, which not something to really bother about in this kind of code. Therefore, in practise both algorithms will perform similar.

[Nitrogen]

I ran a few benchmarks, using the average as reported by GetTickCount over 5 runs of 1,000,000 randomly generated numbers each.

5th place was Delfi's trunc(power(2,trunc(log2(number)))); with a dreadful 146.80 ms average

4th place was my code ops: with a 40.60ms average...

3rd place was jdarling's original code! Well Done! with an average of 25.00ms.

2nd place was Lifepower's NextPowerOfTwo() at 18.80ms
(which returns the next highest power if given a power, so 1024 returns 2048...)

And the winner is... Cairnswm! with an average of just 6.20ms, calling the PreparePowerTwos function once at the start of every run.

For a real multiply, yes. But a multiply with 2 wil be translated to a "add register,register", which is one of the cheapest operations in the CPU

I guess I stand corrected. Lookups are not really faster in this case unless you go all the way!

[dmantione]

Can you benchmark my Pascal solution as well:

dec(v);
v:=v or (v shr 1) or (v shr 2) or (v shr 4) or (v shr 8 ) or (v shr 16);
inc(v);

?

[Paizo]

pretty nice read benchmarks result
like a little competition

[jdarling]

Well, ask and you shall recieve . Seems there are more ways to calculate the nearest power of 2 then I would have thought.

In the end, I realized that the code was (and is) one of the least ran bits, so it didn't make much sense to optimize it just yet. You can see that in the download of the tile splitter in my other post. Though, I might take a look at a different implementation down the road a bit.

Since I am going for cross platform code, I wanted to stay away from assembly code as much as possible.

Thanks everyone, and I'd love to see some compos here on PGD for fastest implementations of different common tasks. In fact, WILL and I were talking over it on IM the other day.

BTW: The fastest way to multiply by 2 is a shift, fastest way to divide by 2 is also a shift . Single clock cycle to execute (considered free). An add takes a minimum 2 clock cycles (also considered free by many people).