4 ms·
Uhhhhhhhhhh, assembly optimizations are absolutely vital in many niches these days, and using it can absolutely help you substantially, over trying to magically
by aseipp 10y ago
Uhhhhhhhhhh, assembly optimizations are absolutely vital in many niches these days, and using it can absolutely help you substantially, over trying to magically contort and "over-fit" the compiler and its optimizations into doing what you want. If you want reasonable speed for some of these domains in C, you have to basically force the compiler to do it, by manually forcing these "assembler optimizations" anyway. Compilers are heuristic and "good enough" for the wide majority of code, they aren't perfect at everything.
You cannot beat the compiler globally, but you can absolutely, with almost 100% certainty, beat it locally. It's a matter of if that "local" component is important enough. You can absolutely beat the compiler at its own game in several domains -- for example, cryptographic code. In this realm, efficiency matters a hell-of-a-lot.
Having implemented things like ChaCha20 before in C -- it's very hard to get the C compiler to get anywhere close, by itself, to what a hand-optimized implementation can do. Just look at Ted Krovetz ChaCha20 written in C: it's fast, in the 1-cycle-per-byte range (my own implementation being in the ~5cpb range), but the code is absolutely ridiculous, because it has to "work with" the C compiler so much and hold its hand, it has to manually use SIMD intrinsics (which still rely on you knowing about the underlying architecture anyway), manually unroll loops etc, careful exit fast paths, etc. By comparison, doing things like vectorized, multi-byte loads or carefully controlled unrolling is relatively "simple" in native assembly and does not require working against any optimizer. These are the kinds of optimizations that are sometimes far simpler to do at the assembly level. https://github.com/floodyberry/supercop/blob/master/crypto_stream/chacha20/krovetz/vec128/stream.c https://github.com/floodyberry/supercop/blob/master/crypto_s...
Ted's implementation is 5x faster than mine, but it's also substantially more complicated due, in no small part, having to force the compiler to get there (I'd say it's ~2x the code but probably on the order or ~10x more complex, all things considered, when you get down to design details). It's not clear to me, honestly, if it wouldn't be better to just write the core loop in assembly and call that. It may very well be less complex by some standards. Also, just to head off this suggestion: no, simply converting my naive code to use GCC vectorized types (not SIMD intrinsics, but vector types) didn't make up for this difference at all, despite the fact it's a fairly perfect case for vectorized code. It made maybe a 10% difference at the end. I need a 500% difference to be in the same ballpark. I'm not going to get it by crossing my fingers, unfortunately.
That said, Ted's implementation has redeeming qualities, including the fact it can be portable, and it does remove some complexity by e.g. not having to register allocate manually. The compiler can take care of instruction scheduling, too. But it only achieves its speed at the cost of a lot of incidental complexity when dealing with the compiler. A lot of the things it's doing are things you have to carefully consider in an assembly optimization, too. You're not gaining anything by "Using C because I can express anything", the main thing you're gaining is a slight ease-of-development, because some of the code is portable. You still have to do all the actual hard work yourself.
At that point, when you're doing that much work -- for a lot of cases, you might as well just say "Screw the compiler" and write it manually, and also yield even more gains, such as a library like this: https://github.com/floodyberry/chacha-opt https://github.com/floodyberry/chacha-opt -- the efficiency gains may absolutely trump development time, when you realize these efficiency gains compound on each other (2x work for 5% benefit is a lot more reasonable when you realize that 5% benefit is going to be realized 100, 10,000, or even 10,000,000 times over, consistently, with every single use).
And in any case, if we want to be pedantic, your assertion is just factually 100% wrong anyway. Here's an example: IEEE-compliant floating point division can easily expressed in assembly, on IEEE-compliant platforms. IEEE-compliant floating point division is, in a real sense, impossible to implement in C/C++ by the rules of the language standard. Why? Because division by zero is defined in IEEE and not C/C++, even if 'float' and 'double' in your system are IEEE-compliant. Another example is overshifting a register, which is undefined in C/C++ and perfectly defined for several architectures. There are absolutely cases where you can write completely legitimate assembly that is impossible to write in standards-compliant C, if you want to be language-lawyer-y about it.