Page 3 of 4 FirstFirst 1234 LastLast
Results 21 to 30 of 35

Thread: Nearest Power of 2 quickly

  1. #21

    Nearest Power of 2 quickly

    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.

  2. #22

    Nearest Power of 2 quickly

    seems i need new trunc implementation, any ideas how to make trunc faster?
    This is my game project - Top Down City:
    http://www.pascalgamedevelopment.com...y-Topic-Reboot

    My OpenAL audio wrapper with Intelligent Source Manager to use unlimited:
    http://www.pascalgamedevelopment.com...source+manager

  3. #23

    Nearest Power of 2 quickly

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

  4. #24

    Nearest Power of 2 quickly

    Quote Originally Posted by Delfi
    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?

    Quote Originally Posted by dmantione
    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...
    My site: DelphiTuts.com (coming soon)...

    Download Font Studio 4.21 here.

  5. #25

    Nearest Power of 2 quickly

    instead of using integers in cairnswm's N lookup table, couldn't you use bytes and get both a performance and size win?
    Peregrinus, expectavi pedes meos in cymbalis
    Nullus norvegicorum sole urinat

  6. #26

    Nearest Power of 2 quickly

    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.

  7. #27

    Nearest Power of 2 quickly

    Quote Originally Posted by Nitrogen
    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.

    Quote Originally Posted by cairnswm
    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.

    Quote Originally Posted by Nitrogen
    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.

    Quote Originally Posted by 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
    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.

    Quote Originally Posted by Nitrogen
    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:

  8. #28
    Co-Founder / PGD Elder WILL's Avatar
    Join Date
    Apr 2003
    Location
    Canada
    Posts
    6,107
    Blog Entries
    25

    Nearest Power of 2 quickly

    Quote Originally Posted by Nitrogen
    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?
    Jason McMillen
    Pascal Game Development
    Co-Founder





  9. #29

    Nearest Power of 2 quickly

    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:

    Code:
    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;

  10. #30
    Legendary Member cairnswm's Avatar
    Join Date
    Nov 2002
    Location
    Randburg, South Africa
    Posts
    1,537

    Nearest Power of 2 quickly

    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
    William Cairns
    My Games: http://www.cairnsgames.co.za (Currently very inactive)
    MyOnline Games: http://TheGameDeveloper.co.za (Currently very inactive)

Page 3 of 4 FirstFirst 1234 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •