3 ms·
> It only shows a lack of awareness that in reality your job as a programmer is not to give instructions to a machine, but to provide enough help that a machine
by Veedrac 10y ago
> It only shows a lack of awareness that in reality your job as a programmer is not to give instructions to a machine, but to provide enough help that a machine can create its own instructions better than you can.
If you are in the position where you need to care about fast code, this is extremely naïve advice. Even in your example, it's plainly obvious that something simple but specialized like
uint64_t reverse_actually_fast(uint64_t n, const uint64_t k) {
n = bswap_64(n);
n = (n & 0xF0F0F0F0F0F0F0F0) >> 4 | (n & 0x0F0F0F0F0F0F0F0F) << 4;
n = (n & 0xCCCCCCCCCCCCCCCC) >> 2 | (n & 0x3333333333333333) << 2;
n = (n & 0xAAAAAAAAAAAAAAAA) >> 1 | (n & 0x5555555555555555) << 1;
return n >> (64 - k);
}
is going to knock the socks off a "plain C" version.
- throwaway_26758 10y agoI was going for a low-hanging fruit example without resorting to bit-twiddling which might confuse many readers, but since you insist I'll repeat my point that going for plain C is great. And that compilers, if properly guided, can optimize better than humans. Following code generates essentially the same code as the GCC builtin intrinsic. uint64_t reverse_actually_fast_c(const uint64_t n, const uint64_t k) { uint64_t r = 0; r = ((n & 0xFF00000000000000) >> 56) | ((n & 0x00FF000000000000) >> 40) | ((n & 0x0000FF0000000000) >> 24) | ((n & 0x000000FF00000000) >> 8) | ((n & 0x00000000FF000000) << 8) | ((n & 0x0000000000FF0000) << 24) | ((n & 0x000000000000FF00) << 40) | ((n & 0x00000000000000FF) << 56); r = (r & 0xF0F0F0F0F0F0F0F0) >> 4 | (r & 0x0F0F0F0F0F0F0F0F) << 4; r = (r & 0xCCCCCCCCCCCCCCCC) >> 2 | (r & 0x3333333333333333) << 2; r = (r & 0xAAAAAAAAAAAAAAAA) >> 1 | (r & 0x5555555555555555) << 1; return r >> (64 - k); }
- Veedrac 10y agoI'm not arguing against plain C - for example I'll always write blsi as `n & -n` because I trust the compiler to recognize that pattern. The problem I have is the claim that the compiler knows better than me, or any programmer with even fairly basic knowledge of the underlying hardware. The only reason to write `reverse_actually_fast_c` like that is because you know of the bswap instruction. If there was no bswap instruction on the target you support, this would hardly be the ideal implementation! Even if you write it indirectly and verbosely, you're still picking out specific assembly instructions. You're giving instructions to a machine.