6 ms·

Yes! This and only this! The posted "bit hacks" are little more than bit level manipulations exactly as intended. The Stanford hacks are truly excellent. My fav

Yes! This and only this! The posted "bit hacks" are little more than bit level manipulations exactly as intended. The Stanford hacks are truly excellent. My favourite is: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float https://graphics.stanford.edu/~seander/bithacks.html#RoundUp...

cozzyd 8y ago
That's really clever, but extremely inefficient. Something like 1 << (sizeof x - __builtin_clz(x)) should be way faster. Edit: you obviously have to multiply by 8 to convert bytes to bits
- glangdale 8y ago
  By the unwritten conventions of bit hacks folks, 'builtin_clz' is not a primitive (and elsewhere in that same document you will find a brace of different ways of doing clz/ctz). Many of these documents are old and the techniques in them older still (dating back to HAKMEM). You are definitely correct on most modern architectures which have a single operation count leading/trailing zeros that are typically no more expensive than an integer multiply. This has been latency = 3, throughput = 1 for most recent Intel arch. I think a redo assuming modern architectures is long overdue; i.e. let's work off the basis that count leading/trailing zeros, PDEP/PEXT, etc are fast and cheap and start from there. Bonus round: if you had a lot of these operations to do, then you still might be able to go faster on x86 on SSE2 or AVX2 by using this trick, as the penalty to pass a SIMD register full of integers to a floating point op or vice versa is just one cycle. This trick becomes obsolete yet again with AVX512, which introduces parallel count leading zeros.
  - AstralStorm 8y ago
    And neither of the bit twiddling is useful for ARM NEON as bit operations in vector form are very limited... (plus there are pipeline stalls) Also multiply adds can be fused so if you're doing that it cab be faster to just multiply by a different number instead of bit twiddling.
    - glangdale 8y ago
      I'm not sure this is true. Many of the bit twiddling hacks can be used in NEON and they have a few unusual instructions I'm dying to play with. I'm not sure which bit hack you're talking about that's done with a multiply or multiply-add. There's a nice use involving De Bruijin sequences for doing lg2 of a single bit that's very instructive - is that what you meant?
saagarjha 8y ago
Of course, casting that int * to a float * is undefined behavior…
- zyx321 8y ago
  Of course. When you first learn about 'cool hacks' like these, you'll want to use everywhere. Then you'll realize that they don't apply to certain data types in certain environments. Then you'll come to realize that the rules governing which hacks to use are too complex to remember. Then you'll want to write a program that figures it out for you. Then you'll realize that those programs already exist, and they are called compilers. So now you are back where you started. You have made no progress, but you have gained an important insight.
  - TeMPOraL 8y ago
    And from that, at some point you realize that the corollary to your #2 says that such hacks do apply to certain data types in certain environments. And then you've gained a very powerful tool to be used in specific circumstances. There's a reason a lot of these potentially non-portable tricks show up in high-performance computing (particularly in videogames) and in the embedded space.
    - zyx321 8y ago
      That reason being that sometimes spending a 10+ hours on a tweak that gives +0.1% performance improvement is worth it. Otherwise, remember the first rule of code optimization for beginners: "Don't." EDIT: And by "they don't apply", I mean they can crash your program or even silently corrupt your data.
      - kaslai 8y ago
        Sometimes tweaks like these might only save 10-20 cycles, which in a vacuum doesn't sound like much, until you consider that before the tweak, it started at 26 cycles and is now 6 cycles, and it's called 50 million times every second, which is a savings of 100 million cycles per second. For games, this can mean a higher frame rate. For data processing, it can mean the data gets processed significantly faster. It's especially important for things like video encoders, where even a 1% savings in CPU time can translate directly to 1% more potential revenue for the same operating cost at a company that relies heavily on video encoding. Yeah, saving those cycles doesn't really mean anything to a beginner, but they can be a huge savings for high performance computation applications.
vvanders 8y ago
While that is a clever hack if you're looking for performance(which is where I've used these before) the float to int conversion normally hoses your pipeline(depending on platform obviously) and the solution below is much faster on any system I've worked with.

cozzyd 8y ago

That's really clever, but extremely inefficient. Something like 1 << (sizeof x - __builtin_clz(x)) should be way faster. Edit: you obviously have to multiply by 8 to convert bytes to bits

glangdale 8y ago
By the unwritten conventions of bit hacks folks, 'builtin_clz' is not a primitive (and elsewhere in that same document you will find a brace of different ways of doing clz/ctz). Many of these documents are old and the techniques in them older still (dating back to HAKMEM). You are definitely correct on most modern architectures which have a single operation count leading/trailing zeros that are typically no more expensive than an integer multiply. This has been latency = 3, throughput = 1 for most recent Intel arch. I think a redo assuming modern architectures is long overdue; i.e. let's work off the basis that count leading/trailing zeros, PDEP/PEXT, etc are fast and cheap and start from there. Bonus round: if you had a lot of these operations to do, then you still might be able to go faster on x86 on SSE2 or AVX2 by using this trick, as the penalty to pass a SIMD register full of integers to a floating point op or vice versa is just one cycle. This trick becomes obsolete yet again with AVX512, which introduces parallel count leading zeros.
- AstralStorm 8y ago
  And neither of the bit twiddling is useful for ARM NEON as bit operations in vector form are very limited... (plus there are pipeline stalls) Also multiply adds can be fused so if you're doing that it cab be faster to just multiply by a different number instead of bit twiddling.
  - glangdale 8y ago
    I'm not sure this is true. Many of the bit twiddling hacks can be used in NEON and they have a few unusual instructions I'm dying to play with. I'm not sure which bit hack you're talking about that's done with a multiply or multiply-add. There's a nice use involving De Bruijin sequences for doing lg2 of a single bit that's very instructive - is that what you meant?

saagarjha 8y ago

Of course, casting that int * to a float * is undefined behavior…

zyx321 8y ago
Of course. When you first learn about 'cool hacks' like these, you'll want to use everywhere. Then you'll realize that they don't apply to certain data types in certain environments. Then you'll come to realize that the rules governing which hacks to use are too complex to remember. Then you'll want to write a program that figures it out for you. Then you'll realize that those programs already exist, and they are called compilers. So now you are back where you started. You have made no progress, but you have gained an important insight.
- TeMPOraL 8y ago
  And from that, at some point you realize that the corollary to your #2 says that such hacks do apply to certain data types in certain environments. And then you've gained a very powerful tool to be used in specific circumstances. There's a reason a lot of these potentially non-portable tricks show up in high-performance computing (particularly in videogames) and in the embedded space.
  - zyx321 8y ago
    That reason being that sometimes spending a 10+ hours on a tweak that gives +0.1% performance improvement is worth it. Otherwise, remember the first rule of code optimization for beginners: "Don't." EDIT: And by "they don't apply", I mean they can crash your program or even silently corrupt your data.
    - kaslai 8y ago
      Sometimes tweaks like these might only save 10-20 cycles, which in a vacuum doesn't sound like much, until you consider that before the tweak, it started at 26 cycles and is now 6 cycles, and it's called 50 million times every second, which is a savings of 100 million cycles per second. For games, this can mean a higher frame rate. For data processing, it can mean the data gets processed significantly faster. It's especially important for things like video encoders, where even a 1% savings in CPU time can translate directly to 1% more potential revenue for the same operating cost at a company that relies heavily on video encoding. Yeah, saving those cycles doesn't really mean anything to a beginner, but they can be a huge savings for high performance computation applications.

vvanders 8y ago

While that is a clever hack if you're looking for performance(which is where I've used these before) the float to int conversion normally hoses your pipeline(depending on platform obviously) and the solution below is much faster on any system I've worked with.