7 ms·

Bubble sort slower with -O3 than -O2 with GCC

163 points by asicsp 5y ago

kiryin 5y ago
I've always been under the impression that -03, -0fast and related "performance" tweaks are not recommended, and shouldn't be used unless the software in question is specifically written with them in mind.
ncmncm 5y ago
I quite frequently find -O3 to produce slower code than -O2. This is not actually surprising: the reliable operations are placed in 2, and the dodgy ones in 3. It is possible, even common, for 3 to be faster, but you can't rely on it. You have to measure.
flatiron 5y ago
Dude spent more time on the explanation than I spend on my “good” projects at work!
- mcraiha 5y ago
  Mandatory xkcd https://xkcd.com/664/ https://xkcd.com/664/
codr7 5y ago
I've written a lot of interpreters in C/++ lately, and spent a lot of time profiling and optimizing them. I can't remember -O3 ever being faster than -O2, it's usually slightly slower for me.
- nly 5y ago
  What about when you factor in PGO? (-fprofile-generate & -fprofile-use)
  - mhh__ 5y ago
    This is the rub. the compiler is flying completely blind without PGO. I turned on PGO for the D compiler recently and it compiled it's tests 15% faster. Boom.
  - codr7 5y ago
    Haven't really been down that rabbit hole yet, thanks for reminding me.
- DannyBee 5y ago
  For interpreters, that's highly likely to be true, especially if they are mainly spending time in switch tables or executing basic opcodes.
  - infberg 5y ago
    Care to explain? -O3 generates larger code than -O2?
    - pclmulqdq 5y ago
      Yes, -O3 tends to include a lot of features that increase code size, like aggressive loop unrolling. If you are jumping around a large amount of code, -O3 generally performs more poorly than -O2, but if you are running a tight loop (like HPC code), -O3 is better. In the past, at a time when I worked on a very performance sensitive codebase that was also limited in scope, we compiled with -Osize and did all the loop optimizations we wanted manually (and with pragmas). That produced faster code than -O2 or -O3.
      - gnufx 5y ago
        Regarding unrolling, -O3 contains -funroll-and-jam but not -funroll-loops. You may want one or the other, maybe both, depending on circumstances. I don't see much benefit from the available pragmas on HPC-type code unless for OpenMP, and "omp simd" isn't necessary to get vectorization in the places I've seen people say it is. Mileage always varies somewhat, of course. (Before second-guessing anything, use -fopt-info.)
      - jleahy 5y ago
        It’s a shame that Osize can sometimes produce truly awful code. There are a few optimisations in there that trade a byte for a massive slowdown.
        jhgb 5y ago
        Surely a profile-guided build should be able to only apply -Os to those functions where it doesn't cause a lot of problems.
jeffbee 5y ago
Lots of things are slower at higher -O levels, many things get slower if you compile them for your native instruction extensions, and there are other surprises lurking all over the compiler. The only way to be sure is to sweep out the parameter space of your compiler, using benchmark results as your objective function.
digitallyfree 5y ago
From my experience, -O2 includes optimizations that improve performance in the majority of cases. Whereas -O3 contains additional optimizations that may improve performance but the results are less clear-cut - hence why they're included in -O3 as opposed to -O2. I've seen cases where -O3 is faster than -O2, and vice versa.
- phkahler 5y ago
  That's why its infuriating that vectorization was not enabled at -O2. Since x86-64 supports SSE2 as a baseline, every program has been under performing at -O2 for over 15 years. Without knowing this it turns out the recent introduction of -march=x86-64-v2 and v3 dont benefit either when both have AVX2 which goes largely unused. See pathetic test results here: https://github.com/solvespace/solvespace/issues/972 https://github.com/solvespace/solvespace/issues/972 Notice that v3 is no better and may even be a hair slower.
  - gnufx 5y ago
    See https://gcc.gnu.org/gcc-12/changes.html https://gcc.gnu.org/gcc-12/changes.html It's still not necessarily a guaranteed win, I think.
  - jleahy 5y ago
    Vectorisation is not a clear win, and so doesn’t belong in O2. Certainly it can deliver massive improvements in some cases (as loop unrolling could in Pentium III days), yet can cause significant binary size increases (think icache costs) and makes loops with small iteration counts potentially much slower. If for some reason you want O2 but with vectorisation you can enable it, and if you want O3 without inlining or loop unrolling (the same thing), you’re welcome to specify that.
    - kzrdude 5y ago
      Maybe it could use a different heuristic in O2? Depending on the function it's vital to have autovectorization for performance. Neither -O3 nor -O2 are perfect as a blanket option for all the functions in a big program.
mhh__ 5y ago
How to keep the O3 goodness without pessimizations: Use likely/unlikely liberally, unreachable(), and PGO. If the code slows down, it's usually because the compiler has generated a bunch of code because it doesn't know what hot path to schedule for. They will generate hundreds to thousands of instructions for factorial if you let them because it turns it into a loop, then vectorizes the loop. Undefined Behaviour pub quiz question in there ^^
- MauranKilom 5y ago
  Not sure if that would have an impact here. GCC is just unaware of the latency implications of store forwarding. I mean, it's definitely worth a shot, but you'd just be more or less hoping that your mentioned techniques disable the right optimization pass.
  - mhh__ 5y ago
    That's true, although I'm curious if any compiler really understands the microarchitecture at that level without being coerced by a compiler dev writing a pass (i.e. won't happen straight from a pipeline description)
- gnufx 5y ago
  Yes to -fprofile-use. That brought gfortran to essentially the same geometric mean as ifort with reasonable "good" flags for me, running a benchmark set which I think is supposed to show off proprietary compilers. ifort got little benefit from its equivalent.
- deleted 5y ago
  [deleted]
- unwind 5y ago
  Just to clarify, in this context PGO = Profile-Guided Optimization [1]. [1]: https://en.m.wikipedia.org/wiki/Profile-guided_optimization https://en.m.wikipedia.org/wiki/Profile-guided_optimization
  - 5y ago
MauranKilom 5y ago
If you've spent any amount of time on StackOverflow around C/C++/assembly, you could probably tell within the first three paragraphs of the answer who authored it. :)
mgraczyk 5y ago
To me the more interesting meta-point here is that some algorithms are less microarchitecture friendly than others. Algorithms with larger distances between data dependencies are less likely to stall. For example I compared an insertion sort and see the same performance between O2 and O3: void insertionsort(int *buf) { for (int i = 1; i < n; ++i) { const int x = buf[i]; int j = i - 1; for (; j >= 0 && buf[j] > x; --j) buf[j + 1] = buf[j]; buf[j + 1] = x; } } bubble O2: 1.208s bubble O3: 1.469s insertion O2: 0.126s insertion O3: 0.126s
gnufx 5y ago
I see something rather different with that example, using GCC 10 on SKX with that code and program argument, bound to a core, +/- ~2%: -O2 -g: 1.07s -O3 -g: 1.17s -O3 -g -fprofile-generate/use: 0.84s (maqao cqa from https://maqao.org https://maqao.org would give comprehensive info on the generated code.) -- /* Tom, don't let me ever catch you using bubblesort again! -- Don */ — Knuth in dvips/afm2tfm.c
- Ballas 5y ago
  Are you also on Ryzen? I get: clang -O3 -march=native: 0.769s clang -O3 : 0.830s clang -O2 -march=native : 0.904s gcc -O2 -march=native :1.007s gcc -Os -march=native : 1.148s gcc -O3 -march=native : 1.928s gcc (GCC) 11.1.0 clang version 12.0.1 On Ryzen 3700x
userbinator 5y ago
My experience with MSVC and ICC is similar - O3 is often worse than O2, and a lot of the time Os is actually the fastest (and smallest).
- StephanTLavavej 5y ago
  MSVC has /O1 and /O2 (and /Os), but not /O3. See https://docs.microsoft.com/en-us/cpp/build/reference/compiler-options-listed-by-category?view=msvc-160 https://docs.microsoft.com/en-us/cpp/build/reference/compile... . (I work on MSVC's STL.)
glandium 5y ago
Relevant talk by Emery Berger: Performance matters https://www.youtube.com/watch?v=r-TLSBdHe1A https://www.youtube.com/watch?v=r-TLSBdHe1A I'd recommend everyone interested in the subject to watch it.
rkagerer 5y ago
this is pretty clearly an anti-optimization you should report on https://gcc.gnu.org/bugzilla/ https://gcc.gnu.org/bugzilla/ Was it ever reported? I did a quick search on https://gcc.gnu.org/bugzilla https://gcc.gnu.org/bugzilla for any issues, of any status, tagged with missed-optimization and containing the term "store-forwarding" or "bubble sort" and didn't see it (maybe I'm not searching right?)
torginus 5y ago
I think bubble sort is kind of an optimization nightmare - a loop where subsequent iterations depend on each other - and the dependency is through memory. I'm pretty sure the compiler tries to extract some level of parallelism from the loop and fails miserably.
sroussey 5y ago
For a decade I used to compile MySQL myself, and always -O2 and never -O3. And a few other flags. Really made a difference in speed to do yourself, but a product like that can show compiler issues and the first two years were less than stable until the right mix was discovered.
- redis_mlc 5y ago
  Back in the day, everybody compiled their own MySQL servers. But it was a mistake. Half of MySQL AB's support calls were related to custom builds, mainly issues with old versions of glibc and multi-threading. Try to use a QA'ed and packaged build of whatever multi-threaded software you need. Source: DBA.
iphorde 5y ago
I just ran this test, I came up with different results. gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 This could be running on a Spectre/Meltdown patched CPU.
c21h30o2 5y ago
Now do -Os my results: time ./size-optimized 30000 real 0m1,164s time ./optimized2 30000 real 0m1,207s time ./optimized3 30000 real 0m1,216s

163 points by asicsp 5y ago

I've always been under the impression that -03, -0fast and related "performance" tweaks are not recommended, and shouldn't be used unless the software in question is specifically written with them in mind.

ncmncm 5y ago

I quite frequently find -O3 to produce slower code than -O2. This is not actually surprising: the reliable operations are placed in 2, and the dodgy ones in 3. It is possible, even common, for 3 to be faster, but you can't rely on it. You have to measure.

flatiron 5y ago

Dude spent more time on the explanation than I spend on my “good” projects at work!

mcraiha 5y ago
Mandatory xkcd https://xkcd.com/664/ https://xkcd.com/664/

codr7 5y ago

I've written a lot of interpreters in C/++ lately, and spent a lot of time profiling and optimizing them. I can't remember -O3 ever being faster than -O2, it's usually slightly slower for me.

nly 5y ago
What about when you factor in PGO? (-fprofile-generate & -fprofile-use)
- mhh__ 5y ago
  This is the rub. the compiler is flying completely blind without PGO. I turned on PGO for the D compiler recently and it compiled it's tests 15% faster. Boom.
- codr7 5y ago
  Haven't really been down that rabbit hole yet, thanks for reminding me.
DannyBee 5y ago
For interpreters, that's highly likely to be true, especially if they are mainly spending time in switch tables or executing basic opcodes.
- infberg 5y ago
  Care to explain? -O3 generates larger code than -O2?
  - pclmulqdq 5y ago
    Yes, -O3 tends to include a lot of features that increase code size, like aggressive loop unrolling. If you are jumping around a large amount of code, -O3 generally performs more poorly than -O2, but if you are running a tight loop (like HPC code), -O3 is better. In the past, at a time when I worked on a very performance sensitive codebase that was also limited in scope, we compiled with -Osize and did all the loop optimizations we wanted manually (and with pragmas). That produced faster code than -O2 or -O3.
    - gnufx 5y ago
      Regarding unrolling, -O3 contains -funroll-and-jam but not -funroll-loops. You may want one or the other, maybe both, depending on circumstances. I don't see much benefit from the available pragmas on HPC-type code unless for OpenMP, and "omp simd" isn't necessary to get vectorization in the places I've seen people say it is. Mileage always varies somewhat, of course. (Before second-guessing anything, use -fopt-info.)
    - jleahy 5y ago
      It’s a shame that Osize can sometimes produce truly awful code. There are a few optimisations in there that trade a byte for a massive slowdown.
      - jhgb 5y ago
        Surely a profile-guided build should be able to only apply -Os to those functions where it doesn't cause a lot of problems.

jeffbee 5y ago

Lots of things are slower at higher -O levels, many things get slower if you compile them for your native instruction extensions, and there are other surprises lurking all over the compiler. The only way to be sure is to sweep out the parameter space of your compiler, using benchmark results as your objective function.

digitallyfree 5y ago

From my experience, -O2 includes optimizations that improve performance in the majority of cases. Whereas -O3 contains additional optimizations that may improve performance but the results are less clear-cut - hence why they're included in -O3 as opposed to -O2. I've seen cases where -O3 is faster than -O2, and vice versa.

phkahler 5y ago
That's why its infuriating that vectorization was not enabled at -O2. Since x86-64 supports SSE2 as a baseline, every program has been under performing at -O2 for over 15 years. Without knowing this it turns out the recent introduction of -march=x86-64-v2 and v3 dont benefit either when both have AVX2 which goes largely unused. See pathetic test results here: https://github.com/solvespace/solvespace/issues/972 https://github.com/solvespace/solvespace/issues/972 Notice that v3 is no better and may even be a hair slower.
- gnufx 5y ago
  See https://gcc.gnu.org/gcc-12/changes.html https://gcc.gnu.org/gcc-12/changes.html It's still not necessarily a guaranteed win, I think.
- jleahy 5y ago
  Vectorisation is not a clear win, and so doesn’t belong in O2. Certainly it can deliver massive improvements in some cases (as loop unrolling could in Pentium III days), yet can cause significant binary size increases (think icache costs) and makes loops with small iteration counts potentially much slower. If for some reason you want O2 but with vectorisation you can enable it, and if you want O3 without inlining or loop unrolling (the same thing), you’re welcome to specify that.
  - kzrdude 5y ago
    Maybe it could use a different heuristic in O2? Depending on the function it's vital to have autovectorization for performance. Neither -O3 nor -O2 are perfect as a blanket option for all the functions in a big program.

mhh__ 5y ago

How to keep the O3 goodness without pessimizations: Use likely/unlikely liberally, unreachable(), and PGO. If the code slows down, it's usually because the compiler has generated a bunch of code because it doesn't know what hot path to schedule for. They will generate hundreds to thousands of instructions for factorial if you let them because it turns it into a loop, then vectorizes the loop. Undefined Behaviour pub quiz question in there ^^

MauranKilom 5y ago
Not sure if that would have an impact here. GCC is just unaware of the latency implications of store forwarding. I mean, it's definitely worth a shot, but you'd just be more or less hoping that your mentioned techniques disable the right optimization pass.
- mhh__ 5y ago
  That's true, although I'm curious if any compiler really understands the microarchitecture at that level without being coerced by a compiler dev writing a pass (i.e. won't happen straight from a pipeline description)
gnufx 5y ago
Yes to -fprofile-use. That brought gfortran to essentially the same geometric mean as ifort with reasonable "good" flags for me, running a benchmark set which I think is supposed to show off proprietary compilers. ifort got little benefit from its equivalent.
deleted 5y ago
[deleted]
unwind 5y ago
Just to clarify, in this context PGO = Profile-Guided Optimization [1]. [1]: https://en.m.wikipedia.org/wiki/Profile-guided_optimization https://en.m.wikipedia.org/wiki/Profile-guided_optimization
- 5y ago

MauranKilom 5y ago

If you've spent any amount of time on StackOverflow around C/C++/assembly, you could probably tell within the first three paragraphs of the answer who authored it. :)

mgraczyk 5y ago

To me the more interesting meta-point here is that some algorithms are less microarchitecture friendly than others. Algorithms with larger distances between data dependencies are less likely to stall. For example I compared an insertion sort and see the same performance between O2 and O3: void insertionsort(int *buf) { for (int i = 1; i < n; ++i) { const int x = buf[i]; int j = i - 1; for (; j >= 0 && buf[j] > x; --j) buf[j + 1] = buf[j]; buf[j + 1] = x; } } bubble O2: 1.208s bubble O3: 1.469s insertion O2: 0.126s insertion O3: 0.126s

gnufx 5y ago

I see something rather different with that example, using GCC 10 on SKX with that code and program argument, bound to a core, +/- ~2%: -O2 -g: 1.07s -O3 -g: 1.17s -O3 -g -fprofile-generate/use: 0.84s (maqao cqa from https://maqao.org https://maqao.org would give comprehensive info on the generated code.) -- /* Tom, don't let me ever catch you using bubblesort again! -- Don */ — Knuth in dvips/afm2tfm.c

Ballas 5y ago
Are you also on Ryzen? I get: clang -O3 -march=native: 0.769s clang -O3 : 0.830s clang -O2 -march=native : 0.904s gcc -O2 -march=native :1.007s gcc -Os -march=native : 1.148s gcc -O3 -march=native : 1.928s gcc (GCC) 11.1.0 clang version 12.0.1 On Ryzen 3700x

userbinator 5y ago

My experience with MSVC and ICC is similar - O3 is often worse than O2, and a lot of the time Os is actually the fastest (and smallest).

StephanTLavavej 5y ago
MSVC has /O1 and /O2 (and /Os), but not /O3. See https://docs.microsoft.com/en-us/cpp/build/reference/compiler-options-listed-by-category?view=msvc-160 https://docs.microsoft.com/en-us/cpp/build/reference/compile... . (I work on MSVC's STL.)

glandium 5y ago

Relevant talk by Emery Berger: Performance matters https://www.youtube.com/watch?v=r-TLSBdHe1A https://www.youtube.com/watch?v=r-TLSBdHe1A I'd recommend everyone interested in the subject to watch it.

rkagerer 5y ago

this is pretty clearly an anti-optimization you should report on https://gcc.gnu.org/bugzilla/ https://gcc.gnu.org/bugzilla/ Was it ever reported? I did a quick search on https://gcc.gnu.org/bugzilla https://gcc.gnu.org/bugzilla for any issues, of any status, tagged with missed-optimization and containing the term "store-forwarding" or "bubble sort" and didn't see it (maybe I'm not searching right?)

torginus 5y ago

I think bubble sort is kind of an optimization nightmare - a loop where subsequent iterations depend on each other - and the dependency is through memory. I'm pretty sure the compiler tries to extract some level of parallelism from the loop and fails miserably.

sroussey 5y ago

For a decade I used to compile MySQL myself, and always -O2 and never -O3. And a few other flags. Really made a difference in speed to do yourself, but a product like that can show compiler issues and the first two years were less than stable until the right mix was discovered.

redis_mlc 5y ago
Back in the day, everybody compiled their own MySQL servers. But it was a mistake. Half of MySQL AB's support calls were related to custom builds, mainly issues with old versions of glibc and multi-threading. Try to use a QA'ed and packaged build of whatever multi-threaded software you need. Source: DBA.

iphorde 5y ago

I just ran this test, I came up with different results. gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 This could be running on a Spectre/Meltdown patched CPU.

c21h30o2 5y ago

Now do -Os my results: time ./size-optimized 30000 real 0m1,164s time ./optimized2 30000 real 0m1,207s time ./optimized3 30000 real 0m1,216s