Hacker News Reader

Comment by payne92 | Hacker News Reader

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.

View on HN

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.

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.

See https://blog.cr.yp.to/20150314-optimizing.html

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.

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.

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

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.

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.

See http://cr.yp.to/qhasm/literature.html

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

Sorry, "hot spot" would be more accurate.

What did you think of first?

Presumably the usual technical meaning: https://en.wikipedia.org/wiki/Critical_section

i.e. the part protected by a lock() / unlock() in multi-threaded code.

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.

But isn't that exactly what OP meant?

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

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.

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

    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.

Your second snippet will just zero rdx - don't confuse the registers (rbx is in the mix in the original :)

Thanks :) Fixed.

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.

Reply on news.ycombinator.com