5 ms·

tl;dr -- the asm author used DIV to divide by a constant 2 More fundamentally: it's theoretically possible to at least match compiled code performance with as

tl;dr -- the asm author used DIV to divide by a constant 2 More fundamentally: it's theoretically possible to at least match compiled code performance with assembly, because you could just write the code the compiler generates. BUT, it requires a LOT of experience. Modern compilers "know" a lot of optimizations (e.g. integer mult by fixed constant --> shifts, adds, and subtracts). Avoiding pipeline stalls requires a lot of tedious register bookkeeping, and modern processors have very complicated execution models. It's almost always better to start with a compiler-generated critical section and see if there are possible hand optimizations.

copperred 9y ago
Your use of the phrase "critical section" threw me off for a second. All good now.
- dingo_bat 9y ago
  What did you think of first?
  - pcordes 9y ago
    Presumably the usual technical meaning: https://en.wikipedia.org/wiki/Critical_section https://en.wikipedia.org/wiki/Critical_section i.e. the part protected by a lock() / unlock() in multi-threaded code.
    - dingo_bat 9y ago
      But isn't that exactly what OP meant?
    - marcosdumay 9y ago
      That deserves a place on the CS bad names gallery, just right of "strong type system". There isn't anything even critical about it, just exclusive. The usage on the context of optimization is much more deserved, although I never heard anybody calling it "section" before, just critical code, critical loop, or stuff like that.
- payne92 9y ago
  Sorry, "hot spot" would be more accurate.
ktRolster 9y ago
It's almost always better to start with a compiler-generated critical section and see if there are possible hand optimizations. Yeap. But once you do, it's almost always easy to get some efficiency gains, because you understand what the code intends, and the compiler does not. Surprisingly it doesn't take much experience to do this: just a profiler, and a willingness to try different things until you find something that works.
- bachmeier 9y ago
  > you understand what the code intends, and the compiler does not It seems to me that the best approach to this would be to feed more information to the compiler rather than writing assembly yourself. Otherwise you give up portability.
  - mikeash 9y ago
    That's generally better when it's possible, but it's not always possible. If you do start writing assembly, you usually want to have it exist next to a higher-level version of the code that you can toggle on and off. This lets you maintain portability (just compile the higher-level version on platforms where you don't yet have assembly) and makes it easy to try out new optimizations that wouldn't require assembly.
  - carussell 9y ago
    See http://cr.yp.to/qhasm/literature.html http://cr.yp.to/qhasm/literature.html
  - ktRolster 9y ago
    You are right. A lot of times you can rearrange the code in various ways, and the compiler will happily generate more efficient code. When that's not possible, the way to keep it portable is by writing a generic C function, then writing an optimized version of the same function that will be compiled when that architecture is available. At work it's rare to need to compile the same code for various architectures, but sometimes it happens.
kutkloon7 9y ago
Nice post. It really surprises me that someone who writes assembly for fun doesn't know that dividing by constants can be done faster, nor that dividing/multiplying by powers of two can be done even faster. On the topic of hand-optimizing or not: There always seem to be two camps. The first say: "Never bother with assembly. Let the compiler do optimizing. If anything, try to write code that the compiler can optimize.". The second camp always states something like "It is not that hard to outperform the compiler.". I guess the complicated pipeline models are mostly the reason for the complexity. I'm not sure how much compilers do to avoid pipeline stalls though. For example, how detailed the execution model that they use is. It shouldn't be too complicated, since most compilers (as far as I know) don't differentiate between different processors, while different processors have a different execution model.
heavenlyblue 9y ago
The issue is that division by a constant of 2, when it's highly optimisable - must already be embodied in the algorithm on a higher level. Essentially you must have a piece of code where that constant is just a parameter to the algorithm that suddenly when set to a value of 2 makes it that much more efficient. Now here's the bummer: if you had already planned for it, then writing custom assembly for it is not going to make the algorithm that much faster. But when you didn't - you're rewriting the whole of the algorithm anyway.
- colejohnson66 9y ago
  But on x86, division by 2 on an unsigned integer is the same as shifting to the right by 1. So instead of even: mov rbx, 2 xor rdx, rdx div rbx the OP should've done something like even: xor rdx, rdx % possible to remove? shr rbx, 1
  - hrydgard 9y ago
    Your second snippet will just zero rdx - don't confuse the registers (rbx is in the mix in the original :)
    - colejohnson66 9y ago
      Thanks :) Fixed.
  - pwdisswordfish 9y ago
    shr rax, 1 div rbx will divide the 128-bit value in (rdx, rax) by rbx, then store the quotient in rax and the remainder in rdx.
bradford 9y ago
In University computer architecture courses, we were challenged to write a quicksort routine in assembly. We were also asked to compare the assembly that we authored with assembly that was compiled from C++ (after we authored our own solutions, of course). It was an amazing crash-course on just how good compilers have become at optimizing. Not a single student could hand craft assembly that was faster than the compiler output. The teacher of the course was able to generate assembly that was slightly faster, and he stated that in order to do so, he had to greatly exploit his in-depth knowledge of the processor's pipeline system. That was roughly year 2000, and I'm sure compilers have only become better at their job since then. All in all, excellent learning experience. I've since encountered several instances where developers assert superior assembly skills, and by default I'm silently skeptical of their claims.
- krylon 9y ago
  Gathering and exploiting in-depth knowledge of a CPU's internals has become more difficult over time, too, I think. At least for x86/amd64 - with out-of-order-exection, branch prediction and whatnot one not only has to know the architecture, but one has to know the specific implementation the code will run on. And knowledge on the deep internals of CPUs made by Intel or AMD (or Via? are they still around?) is not easy to come by.
- carussell 9y ago
  See https://blog.cr.yp.to/20150314-optimizing.html https://blog.cr.yp.to/20150314-optimizing.html
krylon 9y ago
In a prior job I worked as a C programmer, and once I tried to rewrite a few heavily used utility function in assembly. I measured, but it did not run any faster. Damnit, this is assembly, I said, it has to be faster. So I looked at the assembly code generated by the compiler: Turned out it was pretty much identical to the code I had written. At that point, I felt brief surge of pride (because I was as clever as the compiler) and then disappointment (because I was not more clever than the compiler), and I figured trying to be smarter than the compiler was a waste of my time.
2ton_jeff 9y ago
Compelled to chime in here and say that you can just as easily write bad HLL that the compiler can't do much with in the first place. Also back in 2016, I participated in a pseudo-challenge on the fasm board [1] and it is trivial to optimise both the C/C++ as well as hand-written assembly. IMO comparing how good a compiler is at optimising is akin to how good it is at figuring out your intentions (and they all suck at that). 1: https://board.flatassembler.net/topic.php?t=19103 https://board.flatassembler.net/topic.php?t=19103

copperred 9y ago

Your use of the phrase "critical section" threw me off for a second. All good now.

dingo_bat 9y ago
What did you think of first?
- pcordes 9y ago
  Presumably the usual technical meaning: https://en.wikipedia.org/wiki/Critical_section https://en.wikipedia.org/wiki/Critical_section i.e. the part protected by a lock() / unlock() in multi-threaded code.
  - dingo_bat 9y ago
    But isn't that exactly what OP meant?
  - marcosdumay 9y ago
    That deserves a place on the CS bad names gallery, just right of "strong type system". There isn't anything even critical about it, just exclusive. The usage on the context of optimization is much more deserved, although I never heard anybody calling it "section" before, just critical code, critical loop, or stuff like that.
payne92 9y ago
Sorry, "hot spot" would be more accurate.

ktRolster 9y ago

It's almost always better to start with a compiler-generated critical section and see if there are possible hand optimizations. Yeap. But once you do, it's almost always easy to get some efficiency gains, because you understand what the code intends, and the compiler does not. Surprisingly it doesn't take much experience to do this: just a profiler, and a willingness to try different things until you find something that works.

bachmeier 9y ago
> you understand what the code intends, and the compiler does not It seems to me that the best approach to this would be to feed more information to the compiler rather than writing assembly yourself. Otherwise you give up portability.
- mikeash 9y ago
  That's generally better when it's possible, but it's not always possible. If you do start writing assembly, you usually want to have it exist next to a higher-level version of the code that you can toggle on and off. This lets you maintain portability (just compile the higher-level version on platforms where you don't yet have assembly) and makes it easy to try out new optimizations that wouldn't require assembly.
- carussell 9y ago
  See http://cr.yp.to/qhasm/literature.html http://cr.yp.to/qhasm/literature.html
- ktRolster 9y ago
  You are right. A lot of times you can rearrange the code in various ways, and the compiler will happily generate more efficient code. When that's not possible, the way to keep it portable is by writing a generic C function, then writing an optimized version of the same function that will be compiled when that architecture is available. At work it's rare to need to compile the same code for various architectures, but sometimes it happens.

kutkloon7 9y ago

Nice post. It really surprises me that someone who writes assembly for fun doesn't know that dividing by constants can be done faster, nor that dividing/multiplying by powers of two can be done even faster. On the topic of hand-optimizing or not: There always seem to be two camps. The first say: "Never bother with assembly. Let the compiler do optimizing. If anything, try to write code that the compiler can optimize.". The second camp always states something like "It is not that hard to outperform the compiler.". I guess the complicated pipeline models are mostly the reason for the complexity. I'm not sure how much compilers do to avoid pipeline stalls though. For example, how detailed the execution model that they use is. It shouldn't be too complicated, since most compilers (as far as I know) don't differentiate between different processors, while different processors have a different execution model.

heavenlyblue 9y ago

The issue is that division by a constant of 2, when it's highly optimisable - must already be embodied in the algorithm on a higher level. Essentially you must have a piece of code where that constant is just a parameter to the algorithm that suddenly when set to a value of 2 makes it that much more efficient. Now here's the bummer: if you had already planned for it, then writing custom assembly for it is not going to make the algorithm that much faster. But when you didn't - you're rewriting the whole of the algorithm anyway.

colejohnson66 9y ago
But on x86, division by 2 on an unsigned integer is the same as shifting to the right by 1. So instead of even: mov rbx, 2 xor rdx, rdx div rbx the OP should've done something like even: xor rdx, rdx % possible to remove? shr rbx, 1
- hrydgard 9y ago
  Your second snippet will just zero rdx - don't confuse the registers (rbx is in the mix in the original :)
  - colejohnson66 9y ago
    Thanks :) Fixed.
- pwdisswordfish 9y ago
  shr rax, 1 div rbx will divide the 128-bit value in (rdx, rax) by rbx, then store the quotient in rax and the remainder in rdx.

bradford 9y ago

In University computer architecture courses, we were challenged to write a quicksort routine in assembly. We were also asked to compare the assembly that we authored with assembly that was compiled from C++ (after we authored our own solutions, of course). It was an amazing crash-course on just how good compilers have become at optimizing. Not a single student could hand craft assembly that was faster than the compiler output. The teacher of the course was able to generate assembly that was slightly faster, and he stated that in order to do so, he had to greatly exploit his in-depth knowledge of the processor's pipeline system. That was roughly year 2000, and I'm sure compilers have only become better at their job since then. All in all, excellent learning experience. I've since encountered several instances where developers assert superior assembly skills, and by default I'm silently skeptical of their claims.

krylon 9y ago
Gathering and exploiting in-depth knowledge of a CPU's internals has become more difficult over time, too, I think. At least for x86/amd64 - with out-of-order-exection, branch prediction and whatnot one not only has to know the architecture, but one has to know the specific implementation the code will run on. And knowledge on the deep internals of CPUs made by Intel or AMD (or Via? are they still around?) is not easy to come by.
carussell 9y ago
See https://blog.cr.yp.to/20150314-optimizing.html https://blog.cr.yp.to/20150314-optimizing.html

krylon 9y ago

In a prior job I worked as a C programmer, and once I tried to rewrite a few heavily used utility function in assembly. I measured, but it did not run any faster. Damnit, this is assembly, I said, it has to be faster. So I looked at the assembly code generated by the compiler: Turned out it was pretty much identical to the code I had written. At that point, I felt brief surge of pride (because I was as clever as the compiler) and then disappointment (because I was not more clever than the compiler), and I figured trying to be smarter than the compiler was a waste of my time.

2ton_jeff 9y ago

Compelled to chime in here and say that you can just as easily write bad HLL that the compiler can't do much with in the first place. Also back in 2016, I participated in a pseudo-challenge on the fasm board [1] and it is trivial to optimise both the C/C++ as well as hand-written assembly. IMO comparing how good a compiler is at optimising is akin to how good it is at figuring out your intentions (and they all suck at that). 1: https://board.flatassembler.net/topic.php?t=19103 https://board.flatassembler.net/topic.php?t=19103