5 ms·

I always cringe when developers compare compiler-optimized C to 'hand rolled' assembly. In the dawning age of SAT-based program synthesis and vectorization-awar

I always cringe when developers compare compiler-optimized C to 'hand rolled' assembly. In the dawning age of SAT-based program synthesis and vectorization-aware superoptimizers, it's extremely anachronistic. 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. For example, let's take one critical function here: bit reversal. The C code provided (renamed variables so it's easy to consistently compare) has an impressive speedup just going from -O1 to higher optimization levels. And then, on top of that speedup with a decent optimizer, we can again halve the amount of time spent in this function by providing better intentions to the compiler which allow it to perform automatic vectorization. Note this is all in standard C, and makes the code simpler to understand (and maintain) by humans as well. uint64_t reverse_slow(uint64_t n, uint64_t k) { uint64_t r, i; for (r = 0, i = 0; i < k; ++i, n >>= 1) r = (r << 1) | (n & 1); return r; } uint64_t reverse_fast(const uint64_t n, const uint64_t k) { uint64_t r, i; for (r = 0, i = 0; i < k; ++i) r |= ((n >> i) & 1) << (k - i - 1); return r; } Lesson: do your job as a human and provide guidance, let the machines do their job at taking your advice and running wild with creativity. It helps you both become more effective.

conistonwater 10y ago
While what you write has a point, I think it's not quite right. I remember stumbling on this HN conversation recently: https://news.ycombinator.com/item?id=9202858 https://news.ycombinator.com/item?id=9202858 — the two realistic examples mentioned there are video codecs and language interpreters. > In the dawning age of SAT-based program synthesis and vectorization-aware superoptimizers, it's extremely anachronistic. I find this particular argument unconvincing, because those aren't real yet. (Consider also that if it was easy and feasible, they probably would have been real already.) In particular, with respect to automatic vectorization (not even superoptimizers!), there is one curious thing that should be noted: clang, with its automatic vectorizer, gives you special options to check if the vectorizer is working for your code (http://llvm.org/docs/Vectorizers.html#diagnostics http://llvm.org/docs/Vectorizers.html#diagnostics). This is necessary: from the point of view of the programmer, performance-sensitive code that is not auto-vectorized is miscompiled because vectorizing it and the consequent performance gain is part of its correctness. One group of examples of this is all the linear algebra libraries. > do your job as a human and provide guidance This advice is only good in the general setting, where it is indeed good advice. The people whose job it is to write all that performance-sensitive code absolutely must get it right, and saying "a compiler will eventually do it for you" is simply not good enough. FWIW, I think you're not addressing your argument at the right crowd.
- throwaway_26758 10y ago
  > I find this particular argument unconvincing, because those aren't real yet. While the 'ideal' of writing any half-attempted but correct specification, then superoptimizing to the absolute minimal instruction count is unfeasible today, I counter that the attitude that these basic technologies are fantasy is the AI effect in play here. Compilers routinely employ techniques that were considered the holy-grail of program synthesis and superoptimization several years ago, but due to the moving target mindset, we've discounted how capable these suites are becoming. One of the major issues is actually a PEBCAK: programmers don't realize what the standard actually affords. What is truly undefined behavior in your code that will give the go-ahead to a compiler to fully work around what you wrote? Or how about the way you wrote that loop creates a chain of memory dependencies that artificially constrains how the compiler is able to rearrange memory accesses and vectorize. And especially important here is optimization coupled with testing. You wrote your algorithm with while loops and no explicit stopping condition, so even though you could transform the code into a properly bounded for loop and profit, now the optimizer and bounded model checker can't unroll your loop in certainty for checking if a different implementation is actually perfectly functionally identical. Now the compiler can't actually make the optimizing transforms it wishes it could because you failed at your job. And on top of that, you can't refactor while having the machine verify that nothing functionally changed -- a potential regression nightmare. I'm not advocating we forget about how to optimize our code, in fact it's quite the opposite. Human programmers need to fully understand what assumptions and guarantees are built into a language in order to be proficient at giving a specification where optimization automation is possible. Sticking to standard C presents a rather unchanging simple 'virtual machine' model (terminology abused there), rather than deal with the constant flux of small hardware architecture changes that chaotically renders your past wisdom obsolete.
- TheOtherHobbes 10y ago
  The problem is you need to know exactly which optimisations are in the compiler, and whether or not your code will trigger those optimisations. This is very much not a trivial requirement. If you're not desperate to optimise performance you can ignore it. But if you are, you really need to know in detail what your compiler will and won't do for you. A blanket assumption that it's smarter than you will be wrong a significant proportion of the time.
gajjanag 10y ago
> I always cringe when developers compare compiler-optimized C to 'hand rolled' assembly. In the dawning age of SAT-based program synthesis and vectorization-aware superoptimizers, it's extremely anachronistic. 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. I agree with your general point, but note that there are some unfortunate reasons why this can't be done in many cases. A compiler can only make use of appropriate SIMD instructions if it knows that the target has the appropriate SIMD. Most packages/shipped binaries are "universal" x86-64 binaries, i.e at compilation time, these instructions can't really be used effectively in many cases. Of course, in certain cases, one can get around this issue. For example, if one compiles from source, one can pass -march=native or similar such flags. Another example is in game development, where one can freely assume that the target processor has AVX (or whatever it is based on the "min reqs" listed on the game). But in the general case, the common solution is to compile in different pieces of code corresponding to the different target CPU levels and do runtime CPU detection. Video coding (e.g FFmpeg) is one illustration of this approach, and to which I don't know of any reasonable portable alternatives.
- wtallis 10y ago
  GCC has the target_clones function attribute that lets you specify a list of different architecture variants, and GCC will emit a version of the function compiled for each, and automatically generate the code to pick the right one at runtime. This does hinder portability outside of the GNU binutils/glibc world, but is otherwise a pretty clean solution.
  - gajjanag 10y ago
    Thanks a lot for this pointer. I noticed just now that there is another hn discussion on recent developments on this front in GCC: https://news.ycombinator.com/item?id=13153320 https://news.ycombinator.com/item?id=13153320. I do wish there was a portable solution though (at least across *nix platforms with clang or gcc).
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 ago
  I 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 ago
    I'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.

conistonwater 10y ago

While what you write has a point, I think it's not quite right. I remember stumbling on this HN conversation recently: https://news.ycombinator.com/item?id=9202858 https://news.ycombinator.com/item?id=9202858 — the two realistic examples mentioned there are video codecs and language interpreters. > In the dawning age of SAT-based program synthesis and vectorization-aware superoptimizers, it's extremely anachronistic. I find this particular argument unconvincing, because those aren't real yet. (Consider also that if it was easy and feasible, they probably would have been real already.) In particular, with respect to automatic vectorization (not even superoptimizers!), there is one curious thing that should be noted: clang, with its automatic vectorizer, gives you special options to check if the vectorizer is working for your code (http://llvm.org/docs/Vectorizers.html#diagnostics http://llvm.org/docs/Vectorizers.html#diagnostics). This is necessary: from the point of view of the programmer, performance-sensitive code that is not auto-vectorized is miscompiled because vectorizing it and the consequent performance gain is part of its correctness. One group of examples of this is all the linear algebra libraries. > do your job as a human and provide guidance This advice is only good in the general setting, where it is indeed good advice. The people whose job it is to write all that performance-sensitive code absolutely must get it right, and saying "a compiler will eventually do it for you" is simply not good enough. FWIW, I think you're not addressing your argument at the right crowd.

throwaway_26758 10y ago
> I find this particular argument unconvincing, because those aren't real yet. While the 'ideal' of writing any half-attempted but correct specification, then superoptimizing to the absolute minimal instruction count is unfeasible today, I counter that the attitude that these basic technologies are fantasy is the AI effect in play here. Compilers routinely employ techniques that were considered the holy-grail of program synthesis and superoptimization several years ago, but due to the moving target mindset, we've discounted how capable these suites are becoming. One of the major issues is actually a PEBCAK: programmers don't realize what the standard actually affords. What is truly undefined behavior in your code that will give the go-ahead to a compiler to fully work around what you wrote? Or how about the way you wrote that loop creates a chain of memory dependencies that artificially constrains how the compiler is able to rearrange memory accesses and vectorize. And especially important here is optimization coupled with testing. You wrote your algorithm with while loops and no explicit stopping condition, so even though you could transform the code into a properly bounded for loop and profit, now the optimizer and bounded model checker can't unroll your loop in certainty for checking if a different implementation is actually perfectly functionally identical. Now the compiler can't actually make the optimizing transforms it wishes it could because you failed at your job. And on top of that, you can't refactor while having the machine verify that nothing functionally changed -- a potential regression nightmare. I'm not advocating we forget about how to optimize our code, in fact it's quite the opposite. Human programmers need to fully understand what assumptions and guarantees are built into a language in order to be proficient at giving a specification where optimization automation is possible. Sticking to standard C presents a rather unchanging simple 'virtual machine' model (terminology abused there), rather than deal with the constant flux of small hardware architecture changes that chaotically renders your past wisdom obsolete.
TheOtherHobbes 10y ago
The problem is you need to know exactly which optimisations are in the compiler, and whether or not your code will trigger those optimisations. This is very much not a trivial requirement. If you're not desperate to optimise performance you can ignore it. But if you are, you really need to know in detail what your compiler will and won't do for you. A blanket assumption that it's smarter than you will be wrong a significant proportion of the time.

gajjanag 10y ago

> I always cringe when developers compare compiler-optimized C to 'hand rolled' assembly. In the dawning age of SAT-based program synthesis and vectorization-aware superoptimizers, it's extremely anachronistic. 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. I agree with your general point, but note that there are some unfortunate reasons why this can't be done in many cases. A compiler can only make use of appropriate SIMD instructions if it knows that the target has the appropriate SIMD. Most packages/shipped binaries are "universal" x86-64 binaries, i.e at compilation time, these instructions can't really be used effectively in many cases. Of course, in certain cases, one can get around this issue. For example, if one compiles from source, one can pass -march=native or similar such flags. Another example is in game development, where one can freely assume that the target processor has AVX (or whatever it is based on the "min reqs" listed on the game). But in the general case, the common solution is to compile in different pieces of code corresponding to the different target CPU levels and do runtime CPU detection. Video coding (e.g FFmpeg) is one illustration of this approach, and to which I don't know of any reasonable portable alternatives.

wtallis 10y ago
GCC has the target_clones function attribute that lets you specify a list of different architecture variants, and GCC will emit a version of the function compiled for each, and automatically generate the code to pick the right one at runtime. This does hinder portability outside of the GNU binutils/glibc world, but is otherwise a pretty clean solution.
- gajjanag 10y ago
  Thanks a lot for this pointer. I noticed just now that there is another hn discussion on recent developments on this front in GCC: https://news.ycombinator.com/item?id=13153320 https://news.ycombinator.com/item?id=13153320. I do wish there was a portable solution though (at least across *nix platforms with clang or gcc).

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 ago
I 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 ago
  I'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.