10 ms·

Beating the Compiler

140 points by panic 10y ago

mnarayan01 10y ago
Should the second assembler statement use `jle done` rather than `jbe done` to preserve the original semantics? (I know nothing about assembly so could be missing something obvious.)
- kayamon 10y ago
  Yeah, it probably should be. It doesn't affect the performance. The difference would only manifest if you passed in a negative count, which would be an error anyway.
  - mnarayan01 10y ago
    If your version goes UB on a zero length input array, then I think the compiler not only wins, but wins by a lot. Obviously you can easily fix it, but the statement people generally make is "You can't beat the compiler" not "(You, me, whomever else [that was as far as I got], and/or a huge time investment) can't beat the compiler". All that said...people categorically saying "You can't beat the compiler" annoys me too (though in my case they're right; I can't).
    - kayamon 10y ago
      It only fails on a _negative_ count. Zero count works. If your program is passing around negative counts, it's already broken, and the exact specifics of where and when the brokenness manifests aren't particularly important. Technically I should have used a size_t instead of an int for the count anyway, so it's kinda a moot point. I just picked int to make a simpler toy example program.
partycoder 10y ago
Intel and AMD publish programming guides that would help you producing more optimized code. Then there are some aspects that compilers might not optimize a lot for. I like this guide: http://www.farbrausch.com/~fg/seminars/lightspeed_download.pdf http://www.farbrausch.com/~fg/seminars/lightspeed_download.p... It's old, dated, whatever you want, but covers the basics. edit: it seems that link got the "HN hug of death".
sweettea 10y ago
Bestcase seems like a poor metric when the CPU scheduler could certainly cause 7% variation. I would be interested to see, say, 100x the number of runs, and see mean rather than best, since one usually cares about average more than best. I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has.
- flukus 10y ago
  > I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has. From the makefile: GCCFLAGS = -O3 --std=c++11 MSFLAGS = /nologo /Ox /Ob2 /Ot /Oi /GL
  - Too 10y ago
    Would march=native and fstrict-aliasing do any difference? It would be interesting to compare the compiled asm with the hand rolled one. The code has some potential improvements also but maybe the compiler is smart enough to find them, such as reading pivot.key in the loop even though it doesn't change.
    - haldean 10y ago
      -march=native would almost certainly help, but I'm pretty sure -fstrict-aliasing is the default.
- kayamon 10y ago
  The timing _should_ be constant each run, so best case is the best way to remove the scheduler variations. I tried mean also, and the results aren't that different. Optimization is -O3 (see the attached Makefile at the bottom).
- Joky 10y ago
  Because of noise in general, "best case" seems always like the best metric to me. Over a large number of run, you're likely to hit the "perfect" measurement with on a microbenchmark. Otherwise, for an "adaptive" number of runs till enough time is spent to have some "confidence" on the measure, I've been fairly happy with: https://github.com/google/benchmark/ https://github.com/google/benchmark/
Joky 10y ago
This seems quite ridiculous to me, I have seldom seen "modern compilers are always faster than you" but rather "they are good enough that it is not worth it". It provides a very over-confident "conclusion" based on a single dubious test. The main advantage of compilers is that the optimizations scale across a large codebase through inlining for example. Also, just moving from Sandy-Bridge to Haswell for example can have significant performance swing (in both direction). The maintenance cost of the assembly is again a scaling issue. If you have a single function that takes a significant amount of time in your program, and performance is critical, of course you can try to go with lower level. But it is likely that it will be more profitable to start with 1) pre-optimized libraries (i.e. don't write your own "sort") ; 2) follow the optimization guidelines of the CPU vendors regarding memory layout, etc. ; and 3) start with vector C-level intrinsic if possible if you can benefit from vectorization.
- kayamon 10y ago
  On the contrary, I've often seen the "you can't beat the compiler" statement. This[1] recent reddit thread has it in the top comment, which is what prompted me to test it out. And while all those other points are fine points (and I mention all that in the conclusion), it doesn't change the fact that beating the compiler isn't always the rocket science it's made out to be. [1] https://www.reddit.com/r/programming/comments/5f9evm/learning_to_read_x86_assembly_language/ https://www.reddit.com/r/programming/comments/5f9evm/learnin...
  - imauld 10y ago
    Are you the author of the linked post? If so I have a couple of questions: - Why not throw out the best and worst cases for each and then find the mean of run times? Seems like a more "fair" way to compare them. - Did you compare the assembly generated by the compiler to the assembly you wrote?
    - Vendan 10y ago
      You should always be comparing best case for this kind of thing. Slower cases are most likely "your thread got switched out by the OS to let something else run", and that's not really a fair test.
keithnz 10y ago
I'm just curious if there is any overhead in the compiler outputs as the author seemed to be timing the .exe It would be interesting to see the assembly output of all the compilers, and what the compiler settings are
- kayamon 10y ago
  The timing happens directly around the function itself inside the EXE. Compiler settings are in the makefile, full optimization (-O3 or /Ox)
olzhas 10y ago
why the best-case was chosen instead of mean or median?
- kayamon 10y ago
  If the thing you're timing is expected to have a constant running time, the only thing that can slow it down is external factors (e.g. OS background tasks). Best-case over a large number of runs is the correct way to approach the ideal running time of the task in this case, as you can eventually hit a run that didn't get impeded by anything.
- skybrian 10y ago
  When optimizing code, you probably want to work on performance improvements that can actually be fixed by editing the code. Most of the things you can directly affect are things that happen in every test run, so best-case will include them. Slower test runs will include events that don't happen on every test run (the computer is busy doing something else), so editing the code has less effect on them, and possibly none at all if it's completely unrelated. Maybe those other events causing slowdown should be investigated too? But usually you want to look for a way to make them happen every time before working on them.
- emeryberger 10y ago
  You should never do this. Best-case favors outliers and does not represent expected performance, which is what we care about. Just because the stars happen to align one time doesn't mean you report that run. Consider the following runs of two systems: system A: 10s, 10s, 10s, 10s, 10s, 10s, 10s, 5s system B: 6s, 6s, 6s, 6s, 6s, 6s, 6s, 6s Which one is faster? (Hint: don't say system A)
  - to3m 10y ago
    But this ignores the other way of looking at it: if system A is slower, how come it managed to run more quickly?
  - alephnil 10y ago
    You will in practice hardly ever see outliers like you descrivbed in system A, where one run is significantly faster. You will often see cases where one run is significantly slower. The reason could be things like cache misses, swapped out code, some bad code path happening etc (all these on very different timescales). These things tend to happen only occasionally, so the reversed case from your example A (seven five second runs and one ten seconds run) is more pluasible. Because such factors tend to be things you can't easily control, taking the minimum is a good approximation when optimizing a code snippet as opposed to the whole program.
deleted 10y ago
[deleted]
mistercow 10y ago
>where making good use of the SIMD intrinsics can allow assembly to massively beat the compiler. Is this the correct use of this terminology? I thought intrinsics were functions that allow you to tell the compiler to use particular instructions, specifically so you can avoid dropping into assembly. In assembly, wouldn't you just call them "instructions"?
- kayamon 10y ago
  Yeah you're right, I'll fix that.
swolchok 10y ago
I would like to see in the article a discussion of the assembly the compiler produces, how it differs from the assembly the author wrote, and perhaps why the differences are worse.
swolchok 10y ago
It's not mentioned in the article, so I'll note that the code presented is Windows-specific. Windows uses a different calling convention (https://en.wikipedia.org/wiki/X86_calling_conventions#Microsoft_x64_calling_convention https://en.wikipedia.org/wiki/X86_calling_conventions#Micros...) from the one used on Mac and Linux systems (https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI https://en.wikipedia.org/wiki/X86_calling_conventions#System...), so if you want to see the assembly you get from clang on Mac, you'll want to annotate sortRoutine with __attribute__((ms_abi)).
gabrielcsapo 10y ago
"I suppose if there's anything to be learned here, it's that people on the Internet may sometimes be full of shit." most undervalued quote.
dalailambda 10y ago
While this may seem silly to some people, I definitely appreciate the sentiment. "The compiler is smarter than you" is thrown around often here, and on Reddit, and a lot of people consider it "common wisdom", but it's not really correct. Writing code is having a dialogue with the compiler, it can do better than you sometimes, and vice versa, but treating the compiler as a magic box that always spits out faster code than you is pretty silly.
- unscaled 10y ago
  I can see where this received wisdom is coming from: a counter-reaction to the common tendency we had well into the 90s to hand-optimize every procedure considered to be even remotely on the hot path. It didn't even have to be inline assembly: it could just be C code sprinkled with registers, Duff's devices and bit shifts. That used to work well enough for non-portable code targeting a limited range of CPUs, but nowadays the gains are too little , the RoI is negative and these efforts may actually end up backfiring on you. I guess we needed to spread the knowledge that "the compiler is smarter than you" even if it wasn't really accurate, just to stop people from doing crazy stuff out of pure inertia.
  - derrickdirge 10y ago
    Maybe the wisdom should be "the compiler is saner than you."
  - Annatar 10y ago
    I can see where this received wisdom is coming from: a counter-reaction to the common tendency we had well into the 90s to hand-optimize every procedure considered to be even remotely on the hot path. It didn't even have to be inline assembly: it could just be C code sprinkled with registers, Duff's devices and bit shifts. That's not it at all. The original problem was that the compilers generated several orders of magnitude larger and slower code than what we could code in the demo scene, and other than processor or memory, made zero utilization of the hardware or DMA. And in the demo scene, if you're not getting the maximum performance out of the hardware, you might as well be dead -- "demo or die", as Chaos of Sanity (now Farbrausch) so famously put it. Compilers didn't really catch up with us: the fastest and best they can do using hardware instead of just the CPU and RAM is CUDA Fortran (pgi Fortran compilers). I know of no compiler taking advantage of DMA or audio hardware, let alone co-processors like for example the Copper and the Blitter. Even on systems like PS3, the GCC compiler took zero advantage of the RSX chip -- it was just a generic PowerPC compiler. Surely a compiler will sometimes beat a human by generating a perfectly or near perfectly scheduled sequence of instructions for a particular processor, but a human can write a generic piece of assembler code that will get really good performance across a range of different chips in a given processor family, and so still beat a compiler overall.
donovanr 10y ago
Sedgewick's 1978 paper[0] on implementing quicksort has some interesting hand optimizations of the assembly code -- loop rotating, unrolling, etc. I wonder if modern compilers do the same? [0] http://penguin.ewu.edu/cscd300/Topic/AdvSorting/Sedgewick.pdf http://penguin.ewu.edu/cscd300/Topic/AdvSorting/Sedgewick.pd...
- pertymcpert 10y ago
  Yep, loop rotation and unrolling are done very commonly.
deleted 10y ago
[deleted]
bjourne 10y ago
I ported the recursive variant of the quicksort test and ran it on my computer. Changes I made was to replace the Windows specific timing functions with Linux-specific clock_gettime() calls. Then I also changed the rcx and rdx registers to rdi and rsi because those are what the Linux 64bit calling convention uses. Here are my results: sort_asm_recurse.asm 69 ms/loop clang++ 3.8.0/sort_cpp_recurse.cpp 65 ms/loop g++ 5.4.0/sort_cpp_recurse.cpp 70 ms/loop Compiler flags: -O3 --std=c++11 -fomit-frame-pointer -march=native -mtune=native So on my computer, the assembly code (barely) beat g++ but not clang++. From a cursory glance of the assembler code clang++ generates, the difference seem to be that it adds alignment to critical loops. It is also smarter at using 32bit registers when it can get away with it. F.e the handwritten assembler code contains "xor r9, r9". An equivalent but faster variant that the compiler generates is "xor r9d, r9d". There is also a slight error in the assembly code. rsp should be aligned to a 16 byte boundary when a call instruction is executed and the code doesn't ensure that. Likely it loses a whole bunch of performance by calling from unaligned addresses.
- kayamon 10y ago
  It's interesting that your clang and my clang give different results, even though we're using the same version. I suspect it's a result of differing CPU architectures. (i.e. my CPU is a different model to yours perhaps). I originally did put loop alignment in my asm version, but I took it out because it was actually ever so slightly slower on mine. Make of that what you will.
  - kscz 10y ago
    I think a big difference is the flags. At least for g++, if you don't specify -march=native -mtune=native you're going to take a performance hit. How much of a performance hit depends on the features. The sorttest.zip Makefile has only the following flags specified: -O3 --std=c++11 Where bjourne has: -O3 --std=c++11 -fomit-frame-pointer -march=native -mtune=native I might rerun your tests with bjourne's additions!
  - bjourne 10y ago
    That's very likely. Mine is an AMD Phenom(tm) II X6 1090T. Though I changed your code a little so that the intro looks like this: sortRoutine: ; rdi = items ; esi = count push rbp ; <- stack alignment push sortRoutine_start: cmp esi, 2 jb done dec esi The "cmp esi, 2; jb done; dec esi" corresponds to your "sub rdx, 1; jbe done". That improves it on my machine to 63 ms/loop. If you are interested I can put it online somewhere.
DannyBee 10y ago
Yes, you can pretty easily beat the compiler in simple cases when you do this. I would seriously challenge anyone to try to, by hand, do what PLUTO+ does . http://dl.acm.org/citation.cfm?id=2688512 http://dl.acm.org/citation.cfm?id=2688512 It is implemented in at least one real production C++ compiler. The analogue would be graphite in gcc, and polly in llvm, but they don't have the full cost modeling it does. Then try to do it for multiple architectures or even different cache models (IE newer vs older processors). Even simpler things than that, like deciding when it is profitable to add runtime vectorization/alignment checks, etc, is really hard by hand. Hell, in larger functions, i doubt people can even optimally do register allocation (including live range splitting, remat, etc). So yeah, stupid quicksort, sure, you can beat it. I'm not sure what it's supposed to prove? If you restrict yourselves to small cases that are easily optimizable without any thought, and not amenable to any even slightly advanced optimization, yes, you can beat the compiler.
prestonbriggs 10y ago
It's easy to beat a compiler in the small - just takes time & patience. But such an approach doesn't scale. We don't write tiny routines and throw them away; instead, we write big programs made of lots of routines & classes, and we maintain them for years, probably porting them from machine to machine. I encourage everyone to write some assembly; you'll learn a lot. But use a compiler for your work.
titzer 10y ago
Nice job. Here's 900,000 lines of C++ code for you to now translate to assembly. And after you're done with that, I'd like to change a few lines and have you do it over again, preferrably 100 times a day. /sigh /compiler person
- titzer 10y ago
  It'd be nice if people replied instead of just downvoting. You're missing the point of a compiler. It does a huge amount of work to reliably get a very, very good solution to a huge problem in a reasonable amount of time. Depending on the optimization settings, of course it is not going to try its hardest to get the very best code out of every single function. Besides, you can always use the output of the compiler as your starting point for hand optimization. Why don't you try your hand at some Fortran kernels where a compiler might spend a few minutes or hours optimizing the hell out of something extremely important? I doubt you'll beat a Fortran compiler at its main job. No one is claiming that you can't beat the compiler some of the time. But you can't beat the compiler even 0.01% of the time, given how much code there is out there.
  - Gracana 10y ago
    Nobody replied because others made the same argument without being so smug about it.
  - kayamon 10y ago
    I can't beat the compiler even 0.01% of the time? Really? Because that's the point of the article -- I just grabbed the first piece of C I found and managed to beat the compiler.
wictory 10y ago
So I guess that the lesson to take from this post is that you can beat the compiler. We should also appreciate that the people who did similar analyses and did not get a speed up, most probably did not write a blog post about it.
leitasat 10y ago
Is not a tail-recusrion version of the quicksort algorithm needed to really allow compiler to optimize performance?
- kayamon 10y ago
  All of the compilers I tried automatically detected it and did their own tail-recursion.
chriswarbo 10y ago
Compilers are usually at a disadvantage compared to human programmers, as they're under pressure to produce code as quickly as possible; seconds if possible, minutes at worst. A human may spend many hours or days writing, profiling, testing, etc. This biases the kinds of algorithms that compilers use (especially JITs, since they have even stricter requirements). It would be nice to have a compiler/optimiser/analyser/profiler/tester/fuzzer/etc. designed to run for long periods, running all sorts of improvement-finding algorithms, building up a knowledge base about the code on disk (which can be updated incrementally when the code changes), and providing reports and messages to the user. When we're about to embark on a deep dive, for optimisation/debugging/etc. we can fire up this assistant and have it running for the entire time we're devoting to the problem. It can even keep running overnight if we spend several days on the issue.
- adrianb 10y ago
  Maybe like PGO? https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization
  - chriswarbo 10y ago
    Yes, PGO would form part of it. Profiling information could be gathered during testing; we could kill two birds with one stone if we gathered profiling information during property checking, e.g. in the style of QuickCheck/(Lazy)SmallCheck/etc. Maybe with an option to add weights to the test cases, so we can assign a low weight to tests which throw crazy data at the system, like fuzzing, and higher weight to those with realistic data generators, golden tests, etc.
- Franciscouzo 10y ago
  There's this [1], there are also some superoptimizers that will save the optimizations they find for later use, such as [2] [1] https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization [2] https://github.com/google/souper https://github.com/google/souper
  - 10y ago
pkolaczk 10y ago
If he sorts 1 mln items, I guess he runs out of L1 cache and probably out of L2 cache. Therefore memory accesses may pay the biggest role here and that explains why he sees almost no improvement from recursion elimination.
illys 10y ago
About Human vs Compiler, I see a very different issue: most developers (especially at Big Corps) only know objects and do not have a clue about how a processor is processing. As a result, most high level programming has very poor performance - whatever the compiler quality. This is certainly why we keep waiting seconds for simple operations. Questioning compiler output is a very good exercise to become a better developer, whether you can beat the compiler or not.

140 points by panic 10y ago

Should the second assembler statement use `jle done` rather than `jbe done` to preserve the original semantics? (I know nothing about assembly so could be missing something obvious.)

kayamon 10y ago
Yeah, it probably should be. It doesn't affect the performance. The difference would only manifest if you passed in a negative count, which would be an error anyway.
- mnarayan01 10y ago
  If your version goes UB on a zero length input array, then I think the compiler not only wins, but wins by a lot. Obviously you can easily fix it, but the statement people generally make is "You can't beat the compiler" not "(You, me, whomever else [that was as far as I got], and/or a huge time investment) can't beat the compiler". All that said...people categorically saying "You can't beat the compiler" annoys me too (though in my case they're right; I can't).
  - kayamon 10y ago
    It only fails on a _negative_ count. Zero count works. If your program is passing around negative counts, it's already broken, and the exact specifics of where and when the brokenness manifests aren't particularly important. Technically I should have used a size_t instead of an int for the count anyway, so it's kinda a moot point. I just picked int to make a simpler toy example program.

partycoder 10y ago

Intel and AMD publish programming guides that would help you producing more optimized code. Then there are some aspects that compilers might not optimize a lot for. I like this guide: http://www.farbrausch.com/~fg/seminars/lightspeed_download.pdf http://www.farbrausch.com/~fg/seminars/lightspeed_download.p... It's old, dated, whatever you want, but covers the basics. edit: it seems that link got the "HN hug of death".

sweettea 10y ago

Bestcase seems like a poor metric when the CPU scheduler could certainly cause 7% variation. I would be interested to see, say, 100x the number of runs, and see mean rather than best, since one usually cares about average more than best. I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has.

flukus 10y ago
> I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has. From the makefile: GCCFLAGS = -O3 --std=c++11 MSFLAGS = /nologo /Ox /Ob2 /Ot /Oi /GL
- Too 10y ago
  Would march=native and fstrict-aliasing do any difference? It would be interesting to compare the compiled asm with the hand rolled one. The code has some potential improvements also but maybe the compiler is smart enough to find them, such as reading pivot.key in the loop even though it doesn't change.
  - haldean 10y ago
    -march=native would almost certainly help, but I'm pretty sure -fstrict-aliasing is the default.
kayamon 10y ago
The timing _should_ be constant each run, so best case is the best way to remove the scheduler variations. I tried mean also, and the results aren't that different. Optimization is -O3 (see the attached Makefile at the bottom).
Joky 10y ago
Because of noise in general, "best case" seems always like the best metric to me. Over a large number of run, you're likely to hit the "perfect" measurement with on a microbenchmark. Otherwise, for an "adaptive" number of runs till enough time is spent to have some "confidence" on the measure, I've been fairly happy with: https://github.com/google/benchmark/ https://github.com/google/benchmark/

Joky 10y ago

This seems quite ridiculous to me, I have seldom seen "modern compilers are always faster than you" but rather "they are good enough that it is not worth it". It provides a very over-confident "conclusion" based on a single dubious test. The main advantage of compilers is that the optimizations scale across a large codebase through inlining for example. Also, just moving from Sandy-Bridge to Haswell for example can have significant performance swing (in both direction). The maintenance cost of the assembly is again a scaling issue. If you have a single function that takes a significant amount of time in your program, and performance is critical, of course you can try to go with lower level. But it is likely that it will be more profitable to start with 1) pre-optimized libraries (i.e. don't write your own "sort") ; 2) follow the optimization guidelines of the CPU vendors regarding memory layout, etc. ; and 3) start with vector C-level intrinsic if possible if you can benefit from vectorization.

kayamon 10y ago
On the contrary, I've often seen the "you can't beat the compiler" statement. This[1] recent reddit thread has it in the top comment, which is what prompted me to test it out. And while all those other points are fine points (and I mention all that in the conclusion), it doesn't change the fact that beating the compiler isn't always the rocket science it's made out to be. [1] https://www.reddit.com/r/programming/comments/5f9evm/learning_to_read_x86_assembly_language/ https://www.reddit.com/r/programming/comments/5f9evm/learnin...
- imauld 10y ago
  Are you the author of the linked post? If so I have a couple of questions: - Why not throw out the best and worst cases for each and then find the mean of run times? Seems like a more "fair" way to compare them. - Did you compare the assembly generated by the compiler to the assembly you wrote?
  - Vendan 10y ago
    You should always be comparing best case for this kind of thing. Slower cases are most likely "your thread got switched out by the OS to let something else run", and that's not really a fair test.

keithnz 10y ago

I'm just curious if there is any overhead in the compiler outputs as the author seemed to be timing the .exe It would be interesting to see the assembly output of all the compilers, and what the compiler settings are

kayamon 10y ago
The timing happens directly around the function itself inside the EXE. Compiler settings are in the makefile, full optimization (-O3 or /Ox)

olzhas 10y ago

why the best-case was chosen instead of mean or median?

kayamon 10y ago
If the thing you're timing is expected to have a constant running time, the only thing that can slow it down is external factors (e.g. OS background tasks). Best-case over a large number of runs is the correct way to approach the ideal running time of the task in this case, as you can eventually hit a run that didn't get impeded by anything.
skybrian 10y ago
When optimizing code, you probably want to work on performance improvements that can actually be fixed by editing the code. Most of the things you can directly affect are things that happen in every test run, so best-case will include them. Slower test runs will include events that don't happen on every test run (the computer is busy doing something else), so editing the code has less effect on them, and possibly none at all if it's completely unrelated. Maybe those other events causing slowdown should be investigated too? But usually you want to look for a way to make them happen every time before working on them.
emeryberger 10y ago
You should never do this. Best-case favors outliers and does not represent expected performance, which is what we care about. Just because the stars happen to align one time doesn't mean you report that run. Consider the following runs of two systems: system A: 10s, 10s, 10s, 10s, 10s, 10s, 10s, 5s system B: 6s, 6s, 6s, 6s, 6s, 6s, 6s, 6s Which one is faster? (Hint: don't say system A)
- to3m 10y ago
  But this ignores the other way of looking at it: if system A is slower, how come it managed to run more quickly?
- alephnil 10y ago
  You will in practice hardly ever see outliers like you descrivbed in system A, where one run is significantly faster. You will often see cases where one run is significantly slower. The reason could be things like cache misses, swapped out code, some bad code path happening etc (all these on very different timescales). These things tend to happen only occasionally, so the reversed case from your example A (seven five second runs and one ten seconds run) is more pluasible. Because such factors tend to be things you can't easily control, taking the minimum is a good approximation when optimizing a code snippet as opposed to the whole program.

deleted 10y ago

[deleted]

mistercow 10y ago

>where making good use of the SIMD intrinsics can allow assembly to massively beat the compiler. Is this the correct use of this terminology? I thought intrinsics were functions that allow you to tell the compiler to use particular instructions, specifically so you can avoid dropping into assembly. In assembly, wouldn't you just call them "instructions"?

kayamon 10y ago
Yeah you're right, I'll fix that.

swolchok 10y ago

I would like to see in the article a discussion of the assembly the compiler produces, how it differs from the assembly the author wrote, and perhaps why the differences are worse.

swolchok 10y ago

It's not mentioned in the article, so I'll note that the code presented is Windows-specific. Windows uses a different calling convention (https://en.wikipedia.org/wiki/X86_calling_conventions#Microsoft_x64_calling_convention https://en.wikipedia.org/wiki/X86_calling_conventions#Micros...) from the one used on Mac and Linux systems (https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI https://en.wikipedia.org/wiki/X86_calling_conventions#System...), so if you want to see the assembly you get from clang on Mac, you'll want to annotate sortRoutine with __attribute__((ms_abi)).

gabrielcsapo 10y ago

"I suppose if there's anything to be learned here, it's that people on the Internet may sometimes be full of shit." most undervalued quote.

dalailambda 10y ago

While this may seem silly to some people, I definitely appreciate the sentiment. "The compiler is smarter than you" is thrown around often here, and on Reddit, and a lot of people consider it "common wisdom", but it's not really correct. Writing code is having a dialogue with the compiler, it can do better than you sometimes, and vice versa, but treating the compiler as a magic box that always spits out faster code than you is pretty silly.

unscaled 10y ago
I can see where this received wisdom is coming from: a counter-reaction to the common tendency we had well into the 90s to hand-optimize every procedure considered to be even remotely on the hot path. It didn't even have to be inline assembly: it could just be C code sprinkled with registers, Duff's devices and bit shifts. That used to work well enough for non-portable code targeting a limited range of CPUs, but nowadays the gains are too little , the RoI is negative and these efforts may actually end up backfiring on you. I guess we needed to spread the knowledge that "the compiler is smarter than you" even if it wasn't really accurate, just to stop people from doing crazy stuff out of pure inertia.
- derrickdirge 10y ago
  Maybe the wisdom should be "the compiler is saner than you."
- Annatar 10y ago
  I can see where this received wisdom is coming from: a counter-reaction to the common tendency we had well into the 90s to hand-optimize every procedure considered to be even remotely on the hot path. It didn't even have to be inline assembly: it could just be C code sprinkled with registers, Duff's devices and bit shifts. That's not it at all. The original problem was that the compilers generated several orders of magnitude larger and slower code than what we could code in the demo scene, and other than processor or memory, made zero utilization of the hardware or DMA. And in the demo scene, if you're not getting the maximum performance out of the hardware, you might as well be dead -- "demo or die", as Chaos of Sanity (now Farbrausch) so famously put it. Compilers didn't really catch up with us: the fastest and best they can do using hardware instead of just the CPU and RAM is CUDA Fortran (pgi Fortran compilers). I know of no compiler taking advantage of DMA or audio hardware, let alone co-processors like for example the Copper and the Blitter. Even on systems like PS3, the GCC compiler took zero advantage of the RSX chip -- it was just a generic PowerPC compiler. Surely a compiler will sometimes beat a human by generating a perfectly or near perfectly scheduled sequence of instructions for a particular processor, but a human can write a generic piece of assembler code that will get really good performance across a range of different chips in a given processor family, and so still beat a compiler overall.

donovanr 10y ago

Sedgewick's 1978 paper[0] on implementing quicksort has some interesting hand optimizations of the assembly code -- loop rotating, unrolling, etc. I wonder if modern compilers do the same? [0] http://penguin.ewu.edu/cscd300/Topic/AdvSorting/Sedgewick.pdf http://penguin.ewu.edu/cscd300/Topic/AdvSorting/Sedgewick.pd...

pertymcpert 10y ago
Yep, loop rotation and unrolling are done very commonly.

deleted 10y ago

[deleted]

bjourne 10y ago

I ported the recursive variant of the quicksort test and ran it on my computer. Changes I made was to replace the Windows specific timing functions with Linux-specific clock_gettime() calls. Then I also changed the rcx and rdx registers to rdi and rsi because those are what the Linux 64bit calling convention uses. Here are my results: sort_asm_recurse.asm 69 ms/loop clang++ 3.8.0/sort_cpp_recurse.cpp 65 ms/loop g++ 5.4.0/sort_cpp_recurse.cpp 70 ms/loop Compiler flags: -O3 --std=c++11 -fomit-frame-pointer -march=native -mtune=native So on my computer, the assembly code (barely) beat g++ but not clang++. From a cursory glance of the assembler code clang++ generates, the difference seem to be that it adds alignment to critical loops. It is also smarter at using 32bit registers when it can get away with it. F.e the handwritten assembler code contains "xor r9, r9". An equivalent but faster variant that the compiler generates is "xor r9d, r9d". There is also a slight error in the assembly code. rsp should be aligned to a 16 byte boundary when a call instruction is executed and the code doesn't ensure that. Likely it loses a whole bunch of performance by calling from unaligned addresses.

kayamon 10y ago
It's interesting that your clang and my clang give different results, even though we're using the same version. I suspect it's a result of differing CPU architectures. (i.e. my CPU is a different model to yours perhaps). I originally did put loop alignment in my asm version, but I took it out because it was actually ever so slightly slower on mine. Make of that what you will.
- kscz 10y ago
  I think a big difference is the flags. At least for g++, if you don't specify -march=native -mtune=native you're going to take a performance hit. How much of a performance hit depends on the features. The sorttest.zip Makefile has only the following flags specified: -O3 --std=c++11 Where bjourne has: -O3 --std=c++11 -fomit-frame-pointer -march=native -mtune=native I might rerun your tests with bjourne's additions!
- bjourne 10y ago
  That's very likely. Mine is an AMD Phenom(tm) II X6 1090T. Though I changed your code a little so that the intro looks like this: sortRoutine: ; rdi = items ; esi = count push rbp ; <- stack alignment push sortRoutine_start: cmp esi, 2 jb done dec esi The "cmp esi, 2; jb done; dec esi" corresponds to your "sub rdx, 1; jbe done". That improves it on my machine to 63 ms/loop. If you are interested I can put it online somewhere.

DannyBee 10y ago

Yes, you can pretty easily beat the compiler in simple cases when you do this. I would seriously challenge anyone to try to, by hand, do what PLUTO+ does . http://dl.acm.org/citation.cfm?id=2688512 http://dl.acm.org/citation.cfm?id=2688512 It is implemented in at least one real production C++ compiler. The analogue would be graphite in gcc, and polly in llvm, but they don't have the full cost modeling it does. Then try to do it for multiple architectures or even different cache models (IE newer vs older processors). Even simpler things than that, like deciding when it is profitable to add runtime vectorization/alignment checks, etc, is really hard by hand. Hell, in larger functions, i doubt people can even optimally do register allocation (including live range splitting, remat, etc). So yeah, stupid quicksort, sure, you can beat it. I'm not sure what it's supposed to prove? If you restrict yourselves to small cases that are easily optimizable without any thought, and not amenable to any even slightly advanced optimization, yes, you can beat the compiler.

prestonbriggs 10y ago

It's easy to beat a compiler in the small - just takes time & patience. But such an approach doesn't scale. We don't write tiny routines and throw them away; instead, we write big programs made of lots of routines & classes, and we maintain them for years, probably porting them from machine to machine. I encourage everyone to write some assembly; you'll learn a lot. But use a compiler for your work.

titzer 10y ago

Nice job. Here's 900,000 lines of C++ code for you to now translate to assembly. And after you're done with that, I'd like to change a few lines and have you do it over again, preferrably 100 times a day. /sigh /compiler person

titzer 10y ago
It'd be nice if people replied instead of just downvoting. You're missing the point of a compiler. It does a huge amount of work to reliably get a very, very good solution to a huge problem in a reasonable amount of time. Depending on the optimization settings, of course it is not going to try its hardest to get the very best code out of every single function. Besides, you can always use the output of the compiler as your starting point for hand optimization. Why don't you try your hand at some Fortran kernels where a compiler might spend a few minutes or hours optimizing the hell out of something extremely important? I doubt you'll beat a Fortran compiler at its main job. No one is claiming that you can't beat the compiler some of the time. But you can't beat the compiler even 0.01% of the time, given how much code there is out there.
- Gracana 10y ago
  Nobody replied because others made the same argument without being so smug about it.
- kayamon 10y ago
  I can't beat the compiler even 0.01% of the time? Really? Because that's the point of the article -- I just grabbed the first piece of C I found and managed to beat the compiler.

wictory 10y ago

So I guess that the lesson to take from this post is that you can beat the compiler. We should also appreciate that the people who did similar analyses and did not get a speed up, most probably did not write a blog post about it.

leitasat 10y ago

Is not a tail-recusrion version of the quicksort algorithm needed to really allow compiler to optimize performance?

kayamon 10y ago
All of the compilers I tried automatically detected it and did their own tail-recursion.

chriswarbo 10y ago

Compilers are usually at a disadvantage compared to human programmers, as they're under pressure to produce code as quickly as possible; seconds if possible, minutes at worst. A human may spend many hours or days writing, profiling, testing, etc. This biases the kinds of algorithms that compilers use (especially JITs, since they have even stricter requirements). It would be nice to have a compiler/optimiser/analyser/profiler/tester/fuzzer/etc. designed to run for long periods, running all sorts of improvement-finding algorithms, building up a knowledge base about the code on disk (which can be updated incrementally when the code changes), and providing reports and messages to the user. When we're about to embark on a deep dive, for optimisation/debugging/etc. we can fire up this assistant and have it running for the entire time we're devoting to the problem. It can even keep running overnight if we spend several days on the issue.

adrianb 10y ago
Maybe like PGO? https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization
- chriswarbo 10y ago
  Yes, PGO would form part of it. Profiling information could be gathered during testing; we could kill two birds with one stone if we gathered profiling information during property checking, e.g. in the style of QuickCheck/(Lazy)SmallCheck/etc. Maybe with an option to add weights to the test cases, so we can assign a low weight to tests which throw crazy data at the system, like fuzzing, and higher weight to those with realistic data generators, golden tests, etc.
Franciscouzo 10y ago
There's this [1], there are also some superoptimizers that will save the optimizations they find for later use, such as [2] [1] https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization [2] https://github.com/google/souper https://github.com/google/souper
- 10y ago

pkolaczk 10y ago

If he sorts 1 mln items, I guess he runs out of L1 cache and probably out of L2 cache. Therefore memory accesses may pay the biggest role here and that explains why he sees almost no improvement from recursion elimination.

illys 10y ago

About Human vs Compiler, I see a very different issue: most developers (especially at Big Corps) only know objects and do not have a clue about how a processor is processing. As a result, most high level programming has very poor performance - whatever the compiler quality. This is certainly why we keep waiting seconds for simple operations. Questioning compiler output is a very good exercise to become a better developer, whether you can beat the compiler or not.