7 ms·

Writing SSE assembly (not intrinsics) by hand can sometimes give you over a 10x speedup in an inner loop of a computationally expensive problem, like CPU bone a

Writing SSE assembly (not intrinsics) by hand can sometimes give you over a 10x speedup in an inner loop of a computationally expensive problem, like CPU bone animation of vertices. And while it's convenient to use intrinsics to generate SSE (intrinsics look like ordinary C functions and save you from having to write actual assembly), it's impossible for them to always be as efficient as a clever programmer. I'm pretty sure that generating perfectly efficient SSE from SSE intrinsics is an NP-complete problem. So a clever programmer will always be able to boost performance more than a compiler. That said, the two biggest arguments against assembly are: (a) performance matters much less in the modern day, (b) you kill your portability by writing inline assembly. If you expect your code to run on Windows (and gamedevs expect their code to run on Windows, though this may be changing) you'll need to maintain two parallel, #ifdef'd hand written bits of assembly that do exactly the same thing: one for GCC, and one for MSVC. It's a Royal Pain. Those are two damning arguments, and it's why SSE assembly crafting has become something of a lost art. EDIT: I originally led with "It's disappointing that the author makes no mention of SSE assembly," but this was confusing due to the distinction between assembly vs intrinsics. They did briefly mention SSE intrinsics, but not that hand-written SSE assembly is sometimes superior for raw performance. Also, getting a strikethrough modifier on HN for edits would be wonderful.

SixSigma 13y ago
The worst gift #ifdef gives to the world is processor specific code paths. You should really be using conditionals in your make file to select source code files. It is easier to test, easier to debug and you can have a portable fallback. Plan9 uses this method, which is why porting to a new architecture is orders of magnitude simpler than other software platforms. There is no #ifdef hell to work your way through. For instance, plan9's lib C http://plan9.bell-labs.com/sources/plan9/sys/src/libc/ http://plan9.bell-labs.com/sources/plan9/sys/src/libc/ You can choose which functions you would like to hand code and test them against portable C versions with the flick of an environment variable. tl;dr put your logic where it belongs
- dllthomas 13y ago
  There's also the web (literate programming) approach of "change files".
- sillysaurus3 13y ago
  There is no such capability on Windows as a GNU makefile. There is nmake, but it's substantially different. Please don't do this. It will make your code much harder to port. So almost every gamedev will be harmed by this.
  - mschuster91 13y ago
    Actually you can do the following (example is a hypothetical memory allocator implemented at least partially in asm): 1) create a "meta header file" malloc.h, containing the function prototypes. 2) create a "meta source file" malloc.cpp, with #ifdef switches for e.g. x86, x86_64, arm, etc, and inside the ifdefs some #include "malloc_x86.cpp" 3) inside the malloc_x.cpp source files, implement your architecture-specific asm code. 4) if you're after portable code, just do a #else #include "malloc_c.cpp" with a pure-c/cpp implementation. This way everyone can use the malloc and those with matching CPUs can benefit from acceleration.
  - SixSigma 13y ago
    GNU make, that's the last thing I would recommend!
    - sillysaurus3 13y ago
      You should really be using conditionals in your make file to select source code files. If you start moving your programming logic (even compiletime logic) into any kind of makefile, you make life much harder for gamedevs, because it becomes harder to port your code to Windows. If you care about open source, then this is less inclusive a way to write code. You'll be excluding a segment of your programming community (gamedevs) because they're forced by the nature of the industry to compile their code on Windows. That's changing, but it's changing slowly. In the meantime, some people don't care about that, but it would be nice to get some sympathy when it's so easy to write the code in a way that can include more groups of programmers, which is what open source is all about.
jwr 13y ago
> (b) you kill your portability by writing inline assembly. If you expect your code to run on Windows (and gamedevs expect their code to run on Windows, though this may be changing) you'll need to maintain two parallel, #ifdef'd hand written bits of assembly that do exactly the same thing: one for GCC, and one for MSVC. It's a Royal Pain. This is why, when I write assembly, I separate out entire functions, use an external assembler and link them into the final executable. You still have to worry about calling conventions, but in general your code is much easier to maintain than inline assembly. Also, at least for the x86 and gcc, the inline assembly syntax is horrific, and I can't see how anyone can write software in it and still keep their sanity. You really want to use Intel syntax. The disadvantage of writing externally-linked assembly code is that in general, x86 assemblers are crap. You don't even get register allocation, so when I program, I have those pieces of paper around with register allocation tables (1970s-style).
- sillysaurus3 13y ago
  when I program, I have those pieces of paper around with register allocation tables (1970s-style). Would you please make a video or tutorial demonstrating you doing this? Because that's awesome.
  - jwr 13y ago
    Hmm, I'm not quite sure if you're ironic or not? Because it sure feels backwards to be doing that. And the guys next door who program Texas Instruments DSPs roll on the floor laughing -- they write linear assembly for their VLIW chips and the assembler composes the VLIW instructions, takes care of register allocations, and even reorders branch instructions as needed. I feel like using a chisel next to guys with jackhammers.
    - erichocean 13y ago
      Not ironic, I'd love to see it too. I like knowing how things were done originally. :)
- exDM69 13y ago
seertaak 13y ago
He does mention SSE: "Replacing the _mm_andnot_si128 intrinsic with an actual and-not on vectors caused gcc to use other, slower instructions instead of the vmovq to move the result out of the SSE registers for reasons I don't particularly want to track down"
- sillysaurus3 13y ago
  I'm miscommunicating, sorry. Let me try again: The author talks about SSE intrinsics, which masquerade like regular C functions. But this is a post saying "don't use assembly," and writing the actual SSE assembly can give higher performance than using SSE intrinsics. I meant that I was disappointed he didn't talk about SSE assembly directly.
petercooper 13y ago
Writing SSE by hand can sometimes give you over a 10x speedup in an inner loop of a computationally expensive problem [..] a clever programmer will always be able to boost performance more than a compiler. Right now, but I think future proofing is another issue to keep in mind alongside portability. CPUs in, say, 5 years are likely to have alternative and more powerful ways of dealing with certain things, and a good optimizing compiler should (optimistically!) be able to compile older code to run even more quickly on newer CPUs than hand coded assembly might allow. I'm not sure how much impact this issue has in something like the Linux kernel, say, but I could imagine if significant parts of the kernel were written in i386-level x86, it would be a big issue now and demand much rewriting compared to C. (But I could be wrong as I'm not a kernel hacker, and would appreciate expert insight here ;-))
- benjamincburns 13y ago
  I think this is a really good point. It's worth adding that this has been much less of an issue in the past than it will be in the future, as until recently you could always count on increased clock speed. By not being architecture-flexible, your code is basically stuck with today's performance. That said, for some algorithms there's a decent chance that "today's performance" is about what we can expect 20 years from now, so maybe hand-optimization is beneficial.
zwegner 13y ago
> I'm pretty sure that generating perfectly efficient SSE from SSE intrinsics is an NP-complete problem. So a clever programmer will always be able to boost performance more than a compiler. Being NP-complete doesn't really have anything to do with whether humans can solve a given problem better than computers or not. It just means that it (probably) takes exponential time to solve. I believe there is no distinction whatsoever, in principle, between computers and humans (our brains are just big, complicated calculators). As such, it's only a matter of time before computers beat humans in compilation at every point, just like the situation in chess. People claimed for years that humans will always have some edge in chess, because they "understand" the game, or have "ingenuity", or something like that. Nobody claims that anymore, since computers absolutely massacre humans. And similarly to chess, computers have been getting better and better at a very fast rate, while humans have stagnated more-or-less. As an aside, computer chess got quite boring for me, due to the homogeneity of current programs, but it did help to show me the limitations in current programming languages and compilers. So I'd like to do my part to put humans in their place in another field. My still very-much-not-even-close-to-finished contribution, that I haven't found much time to work on in a while, the Mutagen programming language: https://github.com/zwegner/mutagen https://github.com/zwegner/mutagen
- wobbleblob 13y ago
  > I believe there is no distinction whatsoever, in principle, between computers and humans (our brains are just big, complicated calculators). Our brains seem to be primarily an I/O processor attached to a device micro controller.
- joosters 13y ago
  Often, the compiler cannot produce better code than humans because of the failings/features of the language being used. Even c/c++ has many gotchas, for example the assembly code might have to constantly dereference a pointer because the source code (in this case) does not guarantee that the data won't have been changed by others. Meanwhile, a programmer who hand-crafts the same assembly language might know that this won't happen, so they can keep the value in a register. In theory, some of these shortcomings could be solved by a well-written aggressive whole-program optimiser that could deduce data usage & aliasing, but in practice they don't/can't, few people use WPO and it fails when you use library code. In short, compilers probably don't have enough info to beat a skilled assembly programmer.
exDM69 13y ago
> Writing SSE assembly (not intrinsics) by hand can sometimes give you over a 10x speedup in an inner loop of a computationally expensive problem, like CPU bone animation of vertices. My experiences from assembly code vs. intrinsics are just the opposite from yours. What I got out of some intrinsics heavy C code from GCC and Clang was way better than I could ever write. Secondly, using inlineable functions, I could get interprocedural optimization from the compiler. I only needed to write the low level primitives (4x4 matrix multiply, matrix inverse, etc) with intrinsics and the high level code would be inlined and optimized. Adding assembly code to the mix will inhibit compiler optimization. Additionally, the code I wrote could be retargeted for ARM NEON just by switching compilers. I was using mostly the compilers' vector extensions instead of CPU-specific intrinsics (ie. __builtin_shuffle, not __mm_shuffle_ps). > And while it's convenient to use intrinsics to generate SSE (intrinsics look like ordinary C functions and save you from having to write actual assembly), it's impossible for them to always be as efficient as a clever programmer. I'm pretty sure that generating perfectly efficient SSE from SSE intrinsics is an NP-complete problem. So a clever programmer will always be able to boost performance more than a compiler. Looking at the assembly code generated by GCC and Clang, I can see that the compiler does near optimal instruction scheduling and register allocation. On the other hand, the compiler was rather poor in doing instruction selection. I needed to pay a little attention to the code I wrote to avoid GCC spilling registers to the stack, Clang was a bit better. So in my experience, a clever programmer writes poorer assembly code than a clever programmer using a clever compiler and intrinsics. You might need to look at the emitted code from the compiler and do some fine adjustments, so assembly skills are still needed. I bet there are still cases where you can beat the compiler in an isolated problem, but when it comes to maintainability, re-targeting and the amount of effort needed to write the code, writing assembly code isn't worth it most of the time.
- sillysaurus3 13y ago
  Well, of course intrinsics perform just as well as inline assembly when you're doing a single matrix multiply or a single matrix inverse. You won't see any benefit unless you're doing high-throughput computation like thousands of consecutive multiplies. That's when the clever programmer will wipe the floor with your clever compiler. (Well, probably only by a factor of 2x. But still, 2x is better than not-2x in the exceptionally rare case when performance is critical.) I wasn't arguing that people should generally do this. The tradeoffs are rarely worth it. What I was saying is that humans can be more capable than compiler magic, and when it matters, it can really matter. Sometimes by up to 600x, as the other commenter demonstrated.
CJefferson 13y ago
I work on solving NP complete problems by computer. The idea that humans are better at NP-complete problems than computers is laughable. I set as 2nd year 1 week programming tasks writing computer programs that solve NP-complete instances which no person will ever be able to solve by hand.
- jloughry 13y ago
  Sure, in special cases; and it's an important lesson for students to learn: that in small sizes, theoretically impossible problems (in the general case) are perfectly well attackable by brute force enumeration, and it may be the right way to do it under the circumstances.
Groxx 13y ago
>So a clever programmer will always be able to boost performance more than a compiler. I believe the term you're looking for there is "a sufficiently-clever programmer" :) Arguably one is more likely to exist than a sufficiently-clever compiler, but it's exactly the same claim. Even the best humans will have sub-optimal edge cases just like compilers. Given perfect information, sure, I'll agree humans can do better. But it's probably impossible to have (much less make use of) perfect information.

SixSigma 13y ago

The worst gift #ifdef gives to the world is processor specific code paths. You should really be using conditionals in your make file to select source code files. It is easier to test, easier to debug and you can have a portable fallback. Plan9 uses this method, which is why porting to a new architecture is orders of magnitude simpler than other software platforms. There is no #ifdef hell to work your way through. For instance, plan9's lib C http://plan9.bell-labs.com/sources/plan9/sys/src/libc/ http://plan9.bell-labs.com/sources/plan9/sys/src/libc/ You can choose which functions you would like to hand code and test them against portable C versions with the flick of an environment variable. tl;dr put your logic where it belongs

dllthomas 13y ago
There's also the web (literate programming) approach of "change files".
sillysaurus3 13y ago
There is no such capability on Windows as a GNU makefile. There is nmake, but it's substantially different. Please don't do this. It will make your code much harder to port. So almost every gamedev will be harmed by this.
- mschuster91 13y ago
  Actually you can do the following (example is a hypothetical memory allocator implemented at least partially in asm): 1) create a "meta header file" malloc.h, containing the function prototypes. 2) create a "meta source file" malloc.cpp, with #ifdef switches for e.g. x86, x86_64, arm, etc, and inside the ifdefs some #include "malloc_x86.cpp" 3) inside the malloc_x.cpp source files, implement your architecture-specific asm code. 4) if you're after portable code, just do a #else #include "malloc_c.cpp" with a pure-c/cpp implementation. This way everyone can use the malloc and those with matching CPUs can benefit from acceleration.
- SixSigma 13y ago
  GNU make, that's the last thing I would recommend!
  - sillysaurus3 13y ago
    You should really be using conditionals in your make file to select source code files. If you start moving your programming logic (even compiletime logic) into any kind of makefile, you make life much harder for gamedevs, because it becomes harder to port your code to Windows. If you care about open source, then this is less inclusive a way to write code. You'll be excluding a segment of your programming community (gamedevs) because they're forced by the nature of the industry to compile their code on Windows. That's changing, but it's changing slowly. In the meantime, some people don't care about that, but it would be nice to get some sympathy when it's so easy to write the code in a way that can include more groups of programmers, which is what open source is all about.

jwr 13y ago

> (b) you kill your portability by writing inline assembly. If you expect your code to run on Windows (and gamedevs expect their code to run on Windows, though this may be changing) you'll need to maintain two parallel, #ifdef'd hand written bits of assembly that do exactly the same thing: one for GCC, and one for MSVC. It's a Royal Pain. This is why, when I write assembly, I separate out entire functions, use an external assembler and link them into the final executable. You still have to worry about calling conventions, but in general your code is much easier to maintain than inline assembly. Also, at least for the x86 and gcc, the inline assembly syntax is horrific, and I can't see how anyone can write software in it and still keep their sanity. You really want to use Intel syntax. The disadvantage of writing externally-linked assembly code is that in general, x86 assemblers are crap. You don't even get register allocation, so when I program, I have those pieces of paper around with register allocation tables (1970s-style).

sillysaurus3 13y ago
when I program, I have those pieces of paper around with register allocation tables (1970s-style). Would you please make a video or tutorial demonstrating you doing this? Because that's awesome.
- jwr 13y ago
  Hmm, I'm not quite sure if you're ironic or not? Because it sure feels backwards to be doing that. And the guys next door who program Texas Instruments DSPs roll on the floor laughing -- they write linear assembly for their VLIW chips and the assembler composes the VLIW instructions, takes care of register allocations, and even reorders branch instructions as needed. I feel like using a chisel next to guys with jackhammers.
  - erichocean 13y ago
    Not ironic, I'd love to see it too. I like knowing how things were done originally. :)
exDM69 13y ago

seertaak 13y ago

He does mention SSE: "Replacing the _mm_andnot_si128 intrinsic with an actual and-not on vectors caused gcc to use other, slower instructions instead of the vmovq to move the result out of the SSE registers for reasons I don't particularly want to track down"

sillysaurus3 13y ago
I'm miscommunicating, sorry. Let me try again: The author talks about SSE intrinsics, which masquerade like regular C functions. But this is a post saying "don't use assembly," and writing the actual SSE assembly can give higher performance than using SSE intrinsics. I meant that I was disappointed he didn't talk about SSE assembly directly.

petercooper 13y ago

Writing SSE by hand can sometimes give you over a 10x speedup in an inner loop of a computationally expensive problem [..] a clever programmer will always be able to boost performance more than a compiler. Right now, but I think future proofing is another issue to keep in mind alongside portability. CPUs in, say, 5 years are likely to have alternative and more powerful ways of dealing with certain things, and a good optimizing compiler should (optimistically!) be able to compile older code to run even more quickly on newer CPUs than hand coded assembly might allow. I'm not sure how much impact this issue has in something like the Linux kernel, say, but I could imagine if significant parts of the kernel were written in i386-level x86, it would be a big issue now and demand much rewriting compared to C. (But I could be wrong as I'm not a kernel hacker, and would appreciate expert insight here ;-))

benjamincburns 13y ago
I think this is a really good point. It's worth adding that this has been much less of an issue in the past than it will be in the future, as until recently you could always count on increased clock speed. By not being architecture-flexible, your code is basically stuck with today's performance. That said, for some algorithms there's a decent chance that "today's performance" is about what we can expect 20 years from now, so maybe hand-optimization is beneficial.

zwegner 13y ago

> I'm pretty sure that generating perfectly efficient SSE from SSE intrinsics is an NP-complete problem. So a clever programmer will always be able to boost performance more than a compiler. Being NP-complete doesn't really have anything to do with whether humans can solve a given problem better than computers or not. It just means that it (probably) takes exponential time to solve. I believe there is no distinction whatsoever, in principle, between computers and humans (our brains are just big, complicated calculators). As such, it's only a matter of time before computers beat humans in compilation at every point, just like the situation in chess. People claimed for years that humans will always have some edge in chess, because they "understand" the game, or have "ingenuity", or something like that. Nobody claims that anymore, since computers absolutely massacre humans. And similarly to chess, computers have been getting better and better at a very fast rate, while humans have stagnated more-or-less. As an aside, computer chess got quite boring for me, due to the homogeneity of current programs, but it did help to show me the limitations in current programming languages and compilers. So I'd like to do my part to put humans in their place in another field. My still very-much-not-even-close-to-finished contribution, that I haven't found much time to work on in a while, the Mutagen programming language: https://github.com/zwegner/mutagen https://github.com/zwegner/mutagen

wobbleblob 13y ago
> I believe there is no distinction whatsoever, in principle, between computers and humans (our brains are just big, complicated calculators). Our brains seem to be primarily an I/O processor attached to a device micro controller.
joosters 13y ago
Often, the compiler cannot produce better code than humans because of the failings/features of the language being used. Even c/c++ has many gotchas, for example the assembly code might have to constantly dereference a pointer because the source code (in this case) does not guarantee that the data won't have been changed by others. Meanwhile, a programmer who hand-crafts the same assembly language might know that this won't happen, so they can keep the value in a register. In theory, some of these shortcomings could be solved by a well-written aggressive whole-program optimiser that could deduce data usage & aliasing, but in practice they don't/can't, few people use WPO and it fails when you use library code. In short, compilers probably don't have enough info to beat a skilled assembly programmer.

exDM69 13y ago

> Writing SSE assembly (not intrinsics) by hand can sometimes give you over a 10x speedup in an inner loop of a computationally expensive problem, like CPU bone animation of vertices. My experiences from assembly code vs. intrinsics are just the opposite from yours. What I got out of some intrinsics heavy C code from GCC and Clang was way better than I could ever write. Secondly, using inlineable functions, I could get interprocedural optimization from the compiler. I only needed to write the low level primitives (4x4 matrix multiply, matrix inverse, etc) with intrinsics and the high level code would be inlined and optimized. Adding assembly code to the mix will inhibit compiler optimization. Additionally, the code I wrote could be retargeted for ARM NEON just by switching compilers. I was using mostly the compilers' vector extensions instead of CPU-specific intrinsics (ie. __builtin_shuffle, not __mm_shuffle_ps). > And while it's convenient to use intrinsics to generate SSE (intrinsics look like ordinary C functions and save you from having to write actual assembly), it's impossible for them to always be as efficient as a clever programmer. I'm pretty sure that generating perfectly efficient SSE from SSE intrinsics is an NP-complete problem. So a clever programmer will always be able to boost performance more than a compiler. Looking at the assembly code generated by GCC and Clang, I can see that the compiler does near optimal instruction scheduling and register allocation. On the other hand, the compiler was rather poor in doing instruction selection. I needed to pay a little attention to the code I wrote to avoid GCC spilling registers to the stack, Clang was a bit better. So in my experience, a clever programmer writes poorer assembly code than a clever programmer using a clever compiler and intrinsics. You might need to look at the emitted code from the compiler and do some fine adjustments, so assembly skills are still needed. I bet there are still cases where you can beat the compiler in an isolated problem, but when it comes to maintainability, re-targeting and the amount of effort needed to write the code, writing assembly code isn't worth it most of the time.

sillysaurus3 13y ago
Well, of course intrinsics perform just as well as inline assembly when you're doing a single matrix multiply or a single matrix inverse. You won't see any benefit unless you're doing high-throughput computation like thousands of consecutive multiplies. That's when the clever programmer will wipe the floor with your clever compiler. (Well, probably only by a factor of 2x. But still, 2x is better than not-2x in the exceptionally rare case when performance is critical.) I wasn't arguing that people should generally do this. The tradeoffs are rarely worth it. What I was saying is that humans can be more capable than compiler magic, and when it matters, it can really matter. Sometimes by up to 600x, as the other commenter demonstrated.

CJefferson 13y ago

I work on solving NP complete problems by computer. The idea that humans are better at NP-complete problems than computers is laughable. I set as 2nd year 1 week programming tasks writing computer programs that solve NP-complete instances which no person will ever be able to solve by hand.

jloughry 13y ago
Sure, in special cases; and it's an important lesson for students to learn: that in small sizes, theoretically impossible problems (in the general case) are perfectly well attackable by brute force enumeration, and it may be the right way to do it under the circumstances.

Groxx 13y ago

>So a clever programmer will always be able to boost performance more than a compiler. I believe the term you're looking for there is "a sufficiently-clever programmer" :) Arguably one is more likely to exist than a sufficiently-clever compiler, but it's exactly the same claim. Even the best humans will have sub-optimal edge cases just like compilers. Given perfect information, sure, I'll agree humans can do better. But it's probably impossible to have (much less make use of) perfect information.