News for hackers. Stuff that matters.
Re:Why is this C++ code faster than my hand-written assembly... by payne92 on Tuesday August 22, 2017 @10:11AM (#15072553)
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.

Re:Why is this C++ code faster than my hand-written assembly... by bradford on Tuesday August 22, 2017 @12:09PM (#15073769)
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.

Re:Why is this C++ code faster than my hand-written assembly... by krylon on Tuesday August 22, 2017 @12:17PM (#15073849)
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.

Re:Why is this C++ code faster than my hand-written assembly... by carussell on Tuesday August 22, 2017 @03:05PM (#15075428)
Re:Why is this C++ code faster than my hand-written assembly... by krylon on Tuesday August 22, 2017 @12:12PM (#15073804)
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.

Re:Why is this C++ code faster than my hand-written assembly... by ktRolster on Tuesday August 22, 2017 @10:56AM (#15073007)
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.

Re:Why is this C++ code faster than my hand-written assembly... by bachmeier on Tuesday August 22, 2017 @11:20AM (#15073242)
> 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.

Re:Why is this C++ code faster than my hand-written assembly... by ktRolster on Tuesday August 22, 2017 @03:33PM (#15075648)
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.

Re:Why is this C++ code faster than my hand-written assembly... by mikeash on Tuesday August 22, 2017 @11:46AM (#15073516)
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.

Re:Why is this C++ code faster than my hand-written assembly... by carussell on Tuesday August 22, 2017 @03:06PM (#15075438)
Re:Why is this C++ code faster than my hand-written assembly... by copperred on Tuesday August 22, 2017 @10:32AM (#15072751)
Your use of the phrase "critical section" threw me off for a second. All good now.
Re:Why is this C++ code faster than my hand-written assembly... by payne92 on Tuesday August 22, 2017 @02:33PM (#15075179)
Sorry, "hot spot" would be more accurate.
Re:Why is this C++ code faster than my hand-written assembly... by dingo_bat on Tuesday August 22, 2017 @11:42AM (#15073481)
What did you think of first?
Re:Why is this C++ code faster than my hand-written assembly... by pcordes on Tuesday August 22, 2017 @12:53PM (#15074199)
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.

Re:Why is this C++ code faster than my hand-written assembly... by marcosdumay on Tuesday August 22, 2017 @01:43PM (#15074728)
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.

Re:Why is this C++ code faster than my hand-written assembly... by dingo_bat on Tuesday August 22, 2017 @01:34PM (#15074633)
But isn't that exactly what OP meant?
Re:Why is this C++ code faster than my hand-written assembly... by 2ton_jeff on Tuesday August 22, 2017 @07:46PM (#15077298)
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

Re:Why is this C++ code faster than my hand-written assembly... by heavenlyblue on Tuesday August 22, 2017 @11:25AM (#15073312)
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.

Re:Why is this C++ code faster than my hand-written assembly... by colejohnson66 on Tuesday August 22, 2017 @01:23PM (#15074512)
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
Re:Why is this C++ code faster than my hand-written assembly... by pwdisswordfish on Tuesday August 22, 2017 @05:19PM (#15076497)

    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.
Re:Why is this C++ code faster than my hand-written assembly... by hrydgard on Tuesday August 22, 2017 @01:45PM (#15074740)
Your second snippet will just zero rdx - don't confuse the registers (rbx is in the mix in the original :)
Re:Why is this C++ code faster than my hand-written assembly... by colejohnson66 on Tuesday August 22, 2017 @02:26PM (#15075119)
Thanks :) Fixed.
Re:Why is this C++ code faster than my hand-written assembly... by kutkloon7 on Tuesday August 22, 2017 @11:05AM (#15073097)
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.