Nearest Power of 2 quickly

[dmantione]

Adding uses 1 cycle on any cpu since the Pentium 1. Shifting too, with the exception of the Pentium 4, where it is very slow. Therefore, FPC has been changed to use an add for a multiply by 2. FPC will not avoid a shift for other powers of 2, as this would hurt performance on other cpu's.

[Delfi]

seems i need new trunc implementation, any ideas how to make trunc faster?

[dmantione]

You can use SSE3. But that is not an acceptable solution yet. Trunc performance is a known issue unfortunately...

[Nitrogen]

seems i need new trunc implementation, any ideas how to make trunc faster?

Are you sure it's the trunc()'s causing the problems?
I would have guessed that nasty Log2() would slow it down quite a bit?

Can you benchmark my Pascal solution as well:

Sure, I thought it was just an implementation of the trunc() function, but I'll run it through the test when I get back from work...

[JSoftware]

instead of using integers in cairnswm's N lookup table, couldn't you use bytes and get both a performance and size win?

[Robert Kosek]

This is a rather interesting and entertaining thread.

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...

Oh my! You mean that my new system with 2mb of memory might not be enough? Oh wait... typo, I meant gig, not meg. :lol:

Though it you are programming for an embedded system that 4-8kb of memory does count, our systems (even embedded) have ever increasing capabilities and RAM.

Cairnswm: I like your method of precalculation.

[Lifepower]

I cant think of any situation where a power of 2 calculation is not fast enough...

I've used this in Perlin noise in real-time. If you can't think on some situation, it doesn't mean that such situation doesn't exist.

Now this is how to do it with a lookup table

You'd extend this method up to High(Integer), instead of 2048. You never know.

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

Have you checked CeilPowerOfTwo? Would be interesting to compare the two.

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

This argument is common these days, especially in MSDN documentation, where they explain that we don't need assembler on 64-bit systems anymore. Ironical though, their own JIT doesn't optimize much of the code on the fly "to increase startup speed".

Compiler will do a better optimization job than a human, when it will be able to write code instead of yourself (pro genetic programming? ), but then it won't be a compiler, would it? Until then, humans will still be able to perform the task better.

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...

...then I guess the game will only be able to have 16 different textures on my 256 Mb video card. :cry:

[WILL]

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

Did I not suggest a look-up table? :lol:

Nice job William.

Though I'm sure that the speed increase would only be marginal via assembly, am I right?

btw how costly would greater than or lesser than evaluations be? I'd assume not too much as they are quite common. A straight equals evaluation would be super-cheap I'd figure am I right?

[dmantione]

I'm not sure what you you mean. A table lookup would be about as fast in Pascal as in assembler, but that is because it is a micro-operation where not much freedom exists to do things in different ways, which also means there is too little flexibility to do assembler wizardry.

However, for many calculations there are generally enough things assembler coders can do to obtains superior results.

Any comparison, be it less than, greater than, equal or whatever translates to the cmp instruction, which evaluates in one cycle, so is extemely cheap. Because some instructions already set the flags, the cmp is not always necessary and the comparison is even free (the jump after it might still be expensive depending on correct branch prediction). For example:

if a=2                 {This one requires a cmp register,2}
if a and $f<>0     &#123;This one does not require a cmp, and therefore is free.&#125;

[cairnswm]

So how much of the 6ms on my solution is used to call the function when you could instead just do the return value directly

I use a lot of similar lookups in my code. For example on a 2D map to calculate direction I'll store it in an array and just be using the characters facing I'll access the array to work out how much the x and y values change.

I use this sort of data caching a lot in business apps I write - even to the point of caching complete tables within oracle packages to make access faster.

instead of using integers in cairnswm's N lookup table, couldn't you use bytes and get both a performance and size win?

No because byte only goes to 256 and these numbers are larger - but maybe SmallInt could save space.

I decided a long time ago that memory space was there for programmers to use and not for users to try and save - so a cahe is always cool