5 ms·

"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." C

by kken 10y ago

"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?

iammyIP 10y ago
the usual speedup with sse/avx is in about that 2.5 range from what i've observed. If it's lower, then there are likely other effects that stall the execution, like cache misses and other data logistic ineffieciency. 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.
user5994461 10y ago
Whatever can be done with assembly can be done the same with C (or C++). So strictly speaking, assembly optimization can never help you [compared to not using assembly].
- benchaney 10y ago
  This isn't true at all, in fact, the opposite is true. Compilers are often better than naive micro optimizations, but they do not always have every optimization programmed for every architecture. An expert can absolutely beat the compiler in some cases.
  - Veedrac 10y ago
    Although I agree the compiler rarely produces great code automatically, it's normally possible to handhold the compiler into producing code roughly equivalent to hand-written ASM. Doing so is rarely easier, but it is at least more portable!
    - benchaney 10y ago
      Compilers don't use all instructions. For example crypto code often require assembly in order to take advantage of AES instructions.
      - Veedrac 10y ago
        That's what intrinsics are for.
        user5994461 10y ago
        Given the comments, I would assume that the other commenters don't know about intrinsics, or embedding ASM code into C, or "handholding the compiler into producing great code".
- 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.
- user5994461 10y ago
  Wow. You all misunderstood my message judging by the comments and the downvotes. I was talking about hand written C vs hand written ASM. This has no relation to the compiler.
  - benchaney 10y ago
    This makes no sense at all. How can you talk about c vs assembly performance without considering the compiler?
    - user5994461 10y ago
      I guess this is the source of all the misunderstanding. What makes you think that the compiler is relevant to performances? In extreme case of optimization, it's the programmer who does the optimizations with carefully hand written efficient code, not the compiler.
  - buzzybee 10y ago
    That indicates that you swallowed a piece of dogma at some point and didn't think it through. 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.
kitsuac 10y ago
I program assembly as a large part of my daily job, and we generally target between 500% and 1500% speedup for our assembly routines. That number being compared to C code with all compiler optimisations enabled. 1.0x - 2.4x is indeed pretty awful, but it does sometimes happen. For example, many algorithms are fundamentally serial in nature (e.g. entropy decoding).
- gregschlom 10y ago
  I'm curious: what kind of job requires assembly programming nowadays? high frequency trading? game dev? neural networks?
  - kitsuac 10y ago
    I work with video codecs now, but anything computationally intensive and/or close to the hardware will benefit from some assembly code. The three that you mentioned are good examples. The web browser you're using to view and respond to this thread is another example. Among other things, the JavaScript engine most likely does dynamic recompilation and it may use sandboxed webviews.
    - bogomipz 10y ago
      Could you elaborate on how assembly is used in sandboxed webviews?
      - kitsuac 10y ago
        I'm not sure to what extent exactly, but iirc they instrument APIs and pass them through IPC. It may not really be the best example, for some reason it popped into my head but maybe it was an incorrect assumption.
  - aseipp 10y ago
    Cryptography, image/video processing, scientific computation (analysis/physics etc), game dev/graphics, microcontrollers/embedded devices, hardware interfaces, compiler/language development. There are probably at least a dozen more major areas I'm forgetting. I've at least used assembly for 3 of those myself (crypto/hw interfacing/compiler dev). 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!

by kken 10y ago

iammyIP 10y ago

the usual speedup with sse/avx is in about that 2.5 range from what i've observed. If it's lower, then there are likely other effects that stall the execution, like cache misses and other data logistic ineffieciency. 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.

user5994461 10y ago

Whatever can be done with assembly can be done the same with C (or C++). So strictly speaking, assembly optimization can never help you [compared to not using assembly].

benchaney 10y ago
This isn't true at all, in fact, the opposite is true. Compilers are often better than naive micro optimizations, but they do not always have every optimization programmed for every architecture. An expert can absolutely beat the compiler in some cases.
- Veedrac 10y ago
  Although I agree the compiler rarely produces great code automatically, it's normally possible to handhold the compiler into producing code roughly equivalent to hand-written ASM. Doing so is rarely easier, but it is at least more portable!
  - benchaney 10y ago
    Compilers don't use all instructions. For example crypto code often require assembly in order to take advantage of AES instructions.
    - Veedrac 10y ago
      That's what intrinsics are for.
      - user5994461 10y ago
        Given the comments, I would assume that the other commenters don't know about intrinsics, or embedding ASM code into C, or "handholding the compiler into producing great code".
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.
user5994461 10y ago
Wow. You all misunderstood my message judging by the comments and the downvotes. I was talking about hand written C vs hand written ASM. This has no relation to the compiler.
- benchaney 10y ago
  This makes no sense at all. How can you talk about c vs assembly performance without considering the compiler?
  - user5994461 10y ago
    I guess this is the source of all the misunderstanding. What makes you think that the compiler is relevant to performances? In extreme case of optimization, it's the programmer who does the optimizations with carefully hand written efficient code, not the compiler.
- buzzybee 10y ago
  That indicates that you swallowed a piece of dogma at some point and didn't think it through. 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.

kitsuac 10y ago

I program assembly as a large part of my daily job, and we generally target between 500% and 1500% speedup for our assembly routines. That number being compared to C code with all compiler optimisations enabled. 1.0x - 2.4x is indeed pretty awful, but it does sometimes happen. For example, many algorithms are fundamentally serial in nature (e.g. entropy decoding).

gregschlom 10y ago
I'm curious: what kind of job requires assembly programming nowadays? high frequency trading? game dev? neural networks?
- kitsuac 10y ago
  I work with video codecs now, but anything computationally intensive and/or close to the hardware will benefit from some assembly code. The three that you mentioned are good examples. The web browser you're using to view and respond to this thread is another example. Among other things, the JavaScript engine most likely does dynamic recompilation and it may use sandboxed webviews.
  - bogomipz 10y ago
    Could you elaborate on how assembly is used in sandboxed webviews?
    - kitsuac 10y ago
      I'm not sure to what extent exactly, but iirc they instrument APIs and pass them through IPC. It may not really be the best example, for some reason it popped into my head but maybe it was an incorrect assumption.
- aseipp 10y ago
  Cryptography, image/video processing, scientific computation (analysis/physics etc), game dev/graphics, microcontrollers/embedded devices, hardware interfaces, compiler/language development. There are probably at least a dozen more major areas I'm forgetting. I've at least used assembly for 3 of those myself (crypto/hw interfacing/compiler dev). 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!