News for hackers. Stuff that matters.
Re:Bubble sort slower with -O3 than -O2 with GCC by rkagerer on Sunday October 17, 2021 @05:24PM (#28899919)
this is pretty clearly an anti-optimization you should report on https://gcc.gnu.org/bugzilla/

Was it ever reported?

I did a quick search on 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?)

Re:Bubble sort slower with -O3 than -O2 with GCC by mhh__ on Sunday October 17, 2021 @01:05PM (#28897902)
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 ^^

Re:Bubble sort slower with -O3 than -O2 with GCC by unwind on Sunday October 17, 2021 @01:59PM (#28898341)
Just to clarify, in this context PGO = Profile-Guided Optimization [1].

[1]: https://en.m.wikipedia.org/wiki/Profile-guided_optimization

Re:Bubble sort slower with -O3 than -O2 with GCC by jhgb on Sunday October 17, 2021 @04:14PM (#28899391)
...as opposed to? Off the top of my head I can't seem to remember a single acronym I could possibly confuse it with, and now you got me wondering which common acronym I completely failed to learn.
Re:Bubble sort slower with -O3 than -O2 with GCC by toxik on Sunday October 17, 2021 @04:46PM (#28899652)
Pose graph optimization
Re:Bubble sort slower with -O3 than -O2 with GCC by mhh__ on Sunday October 17, 2021 @05:15PM (#28899865)
That seems like a bit of a reach given that the thread is obviously about GCC.
Re:Bubble sort slower with -O3 than -O2 with GCC by gnufx on Sunday October 17, 2021 @02:04PM (#28898374)
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.
Re:Bubble sort slower with -O3 than -O2 with GCC by MauranKilom on Sunday October 17, 2021 @02:00PM (#28898350)
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.
Re:Bubble sort slower with -O3 than -O2 with GCC by mhh__ on Sunday October 17, 2021 @08:06PM (#28900862)
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)
Re:Bubble sort slower with -O3 than -O2 with GCC by bick_nyers on Monday October 18, 2021 @08:10AM (#28904587)
Do you know of any tools for generating this, possibly with runtime data? Been wanting to do this ever since I learned about the feature but I don't want to do this by hand for dependencies.

Edit: It is possible that I just don't understand how to actually implement PGO

Re:Bubble sort slower with -O3 than -O2 with GCC by gnufx on Monday October 18, 2021 @05:08PM (#28911779)
I don't know what exactly is required, but the basic business is

  gcc -fprofile-generate ...
  ./a.out ...
  gcc -fprofile-use ...
I don't know the current state of https://gcc.gnu.org/wiki/AutoFDO
Re:Bubble sort slower with -O3 than -O2 with GCC by gnufx on Sunday October 17, 2021 @02:29PM (#28898583)
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 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
Re:Bubble sort slower with -O3 than -O2 with GCC by Ballas on Tuesday October 19, 2021 @02:21AM (#28915355)
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

Re:Bubble sort slower with -O3 than -O2 with GCC by mgraczyk on Sunday October 17, 2021 @01:57PM (#28898314)
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

Re:Bubble sort slower with -O3 than -O2 with GCC by MauranKilom on Sunday October 17, 2021 @01:41PM (#28898218)
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. :)
Re:Bubble sort slower with -O3 than -O2 with GCC by jeffbee on Sunday October 17, 2021 @12:23PM (#28897567)
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.
Re:Bubble sort slower with -O3 than -O2 with GCC by flatiron on Sunday October 17, 2021 @11:26AM (#28897136)
Dude spent more time on the explanation than I spend on my “good” projects at work!
Re:Bubble sort slower with -O3 than -O2 with GCC by mcraiha on Sunday October 17, 2021 @11:59AM (#28897387)
Mandatory xkcd https://xkcd.com/664/
Re:Bubble sort slower with -O3 than -O2 with GCC by codr7 on Sunday October 17, 2021 @11:47AM (#28897280)
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.

Re:Bubble sort slower with -O3 than -O2 with GCC by DannyBee on Sunday October 17, 2021 @11:55AM (#28897350)
For interpreters, that's highly likely to be true, especially if they are mainly spending time in switch tables or executing basic opcodes.
Re:Bubble sort slower with -O3 than -O2 with GCC by infberg on Sunday October 17, 2021 @12:31PM (#28897636)
Care to explain? -O3 generates larger code than -O2?
Re:Bubble sort slower with -O3 than -O2 with GCC by pclmulqdq on Sunday October 17, 2021 @12:57PM (#28897836)
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.

Re:Bubble sort slower with -O3 than -O2 with GCC by gnufx on Sunday October 17, 2021 @02:14PM (#28898458)
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.)
Re:Bubble sort slower with -O3 than -O2 with GCC by boibombeiro on Sunday October 17, 2021 @11:21PM (#28901938)
Modern x86 CPUs have micro instr caches to store small loops (about 50 instr) and medium loops (~2k instr). Also, the bottleneck is usually the instruction decoding (Alder Lake made huge changes on that, so this might change).

In other words, loop unrolling is, more often than not, harmful.

Re:Bubble sort slower with -O3 than -O2 with GCC by jleahy on Sunday October 17, 2021 @02:52PM (#28898770)
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.
Re:Bubble sort slower with -O3 than -O2 with GCC by userbinator on Sunday October 17, 2021 @04:46PM (#28899649)
You asked for minimum size, and that's what you got. I'd say that's working as it should.

A more granular control over optimisation would be good, however.

Re:Bubble sort slower with -O3 than -O2 with GCC by jleahy on Monday October 18, 2021 @08:07AM (#28904566)
Probably just some tweaks to O2 would be enough, after all people are selecting Os over O2 because they see better performance, and that should not be happening.
Re:Bubble sort slower with -O3 than -O2 with GCC by kevin_thibedeau on Sunday October 17, 2021 @07:31PM (#28900683)
You can enable/disable individual optimizations. How much more granular do you need?
Re:Bubble sort slower with -O3 than -O2 with GCC by jhgb on Sunday October 17, 2021 @04:15PM (#28899409)
Surely a profile-guided build should be able to only apply -Os to those functions where it doesn't cause a lot of problems.
Re:Bubble sort slower with -O3 than -O2 with GCC by pclmulqdq on Sunday October 17, 2021 @07:07PM (#28900578)
In the application I referred to, PGO was also used. However, that only applies -Os to cold code, and if what you're doing is very branchy, it can help even in the hot path.
Re:Bubble sort slower with -O3 than -O2 with GCC by gnufx on Sunday October 17, 2021 @02:07PM (#28898400)
Python, specifically, is supposed to get most benefit from -fno-semantic-interposition
Re:Bubble sort slower with -O3 than -O2 with GCC by nly on Sunday October 17, 2021 @12:32PM (#28897641)
What about when you factor in PGO? (-fprofile-generate & -fprofile-use)
Re:Bubble sort slower with -O3 than -O2 with GCC by mhh__ on Sunday October 17, 2021 @01:03PM (#28897881)
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.

Re:Bubble sort slower with -O3 than -O2 with GCC by codr7 on Sunday October 17, 2021 @01:20PM (#28898019)
Haven't really been down that rabbit hole yet, thanks for reminding me.
Re:Bubble sort slower with -O3 than -O2 with GCC by digitallyfree on Sunday October 17, 2021 @12:44PM (#28897726)
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.
Re:Bubble sort slower with -O3 than -O2 with GCC by phkahler on Sunday October 17, 2021 @01:46PM (#28898242)
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

Notice that v3 is no better and may even be a hair slower.

Re:Bubble sort slower with -O3 than -O2 with GCC by jleahy on Sunday October 17, 2021 @02:10PM (#28898428)
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.

Re:Bubble sort slower with -O3 than -O2 with GCC by phkahler on Sunday October 17, 2021 @04:45PM (#28899641)
The fact that they are changing to include some vectorization options by default for -O2 suggests otherwise. In particular SLP vectorization should have been there all along. Every graphics library 2d and 3d defines vector classes that will easily go faster with the simplest vectorization.

Arguments around code size have been largely irrelevant for quite some time, so long as performance increases.

If I put on a tinfoil hat, I'd suspect Intel was at least an influence. They're the ones adding AVX, AVX2, 512 and providing their own compiler to take advantage of them, while crippling AMD parts. That is until they switched to LLVM.

Re:Bubble sort slower with -O3 than -O2 with GCC by sroussey on Sunday October 17, 2021 @07:15PM (#28900606)
Code size always matters. The code cache in the cpu is far from infinite and long jumps will stall. Sometimes vectorization can shrink code, so yay. And, like you said, if performance increases, then yay again regardless of size.
Re:Bubble sort slower with -O3 than -O2 with GCC by ncmncm on Sunday October 17, 2021 @08:29PM (#28900983)
Code size always matters, except for all the times when it doesn't. Or when something else matters more.

Code size matters less than it once did, now that we have bigger and smarter caches. But bigger, while sometimes big enough, is never big.

Re:Bubble sort slower with -O3 than -O2 with GCC by kzrdude on Sunday October 17, 2021 @02:36PM (#28898648)
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.
Re:Bubble sort slower with -O3 than -O2 with GCC by userbinator on Sunday October 17, 2021 @04:42PM (#28899615)
Did you mean the P4? An extremely long pipeline meant loop unrolling helps it far more than it does x86 processors before or after. PIII is more similar to Core/2/i in performance characteristics.

...and then there's Atom, which is also an odd one - I believe it's more like a classic Pentium (P54).

Re:Bubble sort slower with -O3 than -O2 with GCC by jleahy on Sunday October 17, 2021 @06:08PM (#28900249)
Well I did want to say the P4, but I never actually had one so didn’t want to say something that turned out to be wrong.

Certainly on earlier microarchitectures it did help a lot more than it does now, and there were some nice wins on the PIII for it

Re:Bubble sort slower with -O3 than -O2 with GCC by gnufx on Sunday October 17, 2021 @02:00PM (#28898349)
See https://gcc.gnu.org/gcc-12/changes.html It's still not necessarily a guaranteed win, I think.
Re:Bubble sort slower with -O3 than -O2 with GCC by amelius on Sunday October 17, 2021 @04:22PM (#28899455)
Can you turn on optimizations on a per-function basis?
Re:Bubble sort slower with -O3 than -O2 with GCC by gnufx on Sunday October 17, 2021 @04:41PM (#28899604)
Yes, and that's sometimes a good idea. GCC has a pragma and function attribute (unfortunately not for Fortran, at least).
Re:Bubble sort slower with -O3 than -O2 with GCC by torginus on Sunday October 17, 2021 @05:39PM (#28900030)
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.
Re:Bubble sort slower with -O3 than -O2 with GCC by glandium on Sunday October 17, 2021 @05:22PM (#28899911)
Relevant talk by Emery Berger: Performance matters https://www.youtube.com/watch?v=r-TLSBdHe1A I'd recommend everyone interested in the subject to watch it.
Re:Bubble sort slower with -O3 than -O2 with GCC by c21h30o2 on Sunday October 17, 2021 @09:48PM (#28901466)
Now do -Os

my results:

time ./size-optimized 30000 real 0m1,164s

time ./optimized2 30000 real 0m1,207s

time ./optimized3 30000 real 0m1,216s

Re:Bubble sort slower with -O3 than -O2 with GCC by sroussey on Sunday October 17, 2021 @07:19PM (#28900630)
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.
Re:Bubble sort slower with -O3 than -O2 with GCC by ncmncm on Sunday October 17, 2021 @08:20PM (#28900937)
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.

Re:Bubble sort slower with -O3 than -O2 with GCC by userbinator on Sunday October 17, 2021 @03:45PM (#28899183)
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).
Re:Bubble sort slower with -O3 than -O2 with GCC by StephanTLavavej on Sunday October 17, 2021 @05:15PM (#28899866)
MSVC has /O1 and /O2 (and /Os), but not /O3. See https://docs.microsoft.com/en-us/cpp/build/reference/compile... . (I work on MSVC's STL.)
Re:Bubble sort slower with -O3 than -O2 with GCC by kiryin on Sunday October 17, 2021 @02:50PM (#28898759)
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.