"The hand-coded x86-64 AVX code is from 1.0× to 2.4× faster than the best C code (which is the AVX model code). This speedup was not as impressive as hoped."
Curious. So assembly optimization does not really help that much with modern CPUs?
Curious. So assembly optimization does not really help that much with modern CPUs?
It's maybe niche, as far as the job market/skills go, but when you think about it, a hell of a lot of the stuff on a modern Linux system you might use every day is powered by hand-optimized assembly. If you're even visiting this webpage -- the cryptographic stack your browser uses to negotiate TLS, with almost 100% certainty, relies on deep assembly optimization. JavaScript engines are relentlessly optimized at these levels. Any time you visit a page and render an image, systems like libjpeg-turbo are, in no small part, a piece of the puzzle. Using disk encryption or ipsec, too? Assembly in your kernel. It's everywhere!
The fft shown here uses a precalced lookup table for sin & cos. For a fft size of 2048 this takes 2 * 8 * 2048 bytes, around 32 kb, which is the already size of the usual L1 cache. The bigger the fft size the bigger the lookup table and the less all the asm will be effective.
The asm benefits more of a pure algorithmic approach, might try some sin cos approximation instead of a lookup table, then the speed gain might be more consistent.
So strictly speaking, assembly optimization can never help you [compared to not using assembly].
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_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 -- 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.
I was talking about hand written C vs hand written ASM. This has no relation to the compiler.
In extreme case of optimization, it's the programmer who does the optimizations with carefully hand written efficient code, not the compiler.
The argument of "the compiler can make faster code than any programmer's assembly code" - which I think is what you are repeating here - is discussing whether writing an entire application in assembly will give great wins. It doesn't do so today because the compilers are much, much better at finding performance wins over a large, sprawling program; it's a poor use of coding time to attempt otherwise. It is inner loop code that is the concern of everyone writing low-level optimizations today, and inner loop code is a special beast. It can be attacked by writing C tuned around the compiler's optimizer, by writing inline assembly, or by writing a specialized compiler that compiles the optimal code path on demand according to some set of parameters.
C written for an general-purpose optimizer understands that a certain assembly-code result is wanted, and it understands that the compiler has a limited ability to analyze the code and produce that result. It's not the same as any other hand-written C, because it deliberately arranges scenarios that the optimizer can pick up on. It uses just-so orderings of statements that are mathematically transitive but will optimize differently in practice. It sets up usages of undefined behavior that are known to be used by the optimizer. It uses extensions specific to the compiler, if they lead to faster generated code. This is a nasty black art and optimizing falls towards this practice because it still ends up being more convenient than writing the assembly, for a variety of reasons - more fluidity in the larger context of the codebase, a safer fallback if the optimization fails, more portable.
Inline assembly is a hard break with the rest of the program, but for the most inner of inner loop code, the additional power over the details of execution continues to make a substantial difference.
Specialized compilation is gradually becoming more practiced for very demanding numeric applications and one can find the occasional paper or tool published about it. It's obviously more work than writing a single optimization once, but it has the benefit of being a potentially reusable abstraction.
WTF. I have never said that.
I wasn't talking about the code generated by the compiler. I even wrote a message to clarify that I talk about handwritten code, not about code generated by a compiler.
Can you elaborate? Are you are talking about nested loops and quadratic run times?