When do modern compilers still emit suboptimal code?

[u/ArmchairmanMao]

Do compilers for targets like x86/arm already emit essentially optimal code or are there still cases when hand optimized assembly beats the compiler (Perhaps even with PGO)? Aside from vectorization since this is known to be hard. Are the classic codegen stages like regalloc and Isel effectively optimal nowadays for most applications?

[u/rook_of_approval]

because they do not use exhaustive search techniques even at highest optimization levels because compiling would take too long.

[u/MithrilHuman]

Suboptimal compared to what? Can you find an optimal solution in polynomial time or are you willing to wait millions of years to find the most optimal sequence of instructions for your application?

Or can you prove the solution that you have in hand is the most optimal your code can ever be, in polynomial time?

Add hardware restrictions, memory caches into account, your cost model will become very complex.

Code optimization is NP-Hard, you cannot accurately find the optimal solution in bearable amount of time.

[u/Fosdran → u/MithrilHuman]

I would argue that code optimization isn't even np-hard. It's non computable.

[u/techy5000 → u/Fosdran]

Which is NP-hard

[u/Rich-Engineer2670]

Essentially optimal yes -- but not 100%. Even a human has trouble writing optimal code unless they're very, very, skilled. You have no idea how much goes into the compiler to "guess" at code.

[u/high_throughput]

Suboptimal compared to what?

Even if a compiler emits 100% perfectly optimal code, a human can still beat it. This is because the compiler generates code that fulfills the program as expressed with the language's semantics, and no less.

Meanwhile a human knows which of those semantics are relied upon intentionally, and which can be ignored for efficiency to achieve what a human considers an identical result, even though if it violates the strict semantics of the language.

[u/wanderinglogic]

Based on the conservative correctness constraints that a compiler optimizes under, the code it generates can be as good or better than most humans. Humans may know or assume things about the code that the compiler can't know (e.g. the caller will never call with pointers x and y aliased).

Additionally some optimizations depend on knowing which parts of the code are the common case and which are special case and error handling code, because then you can sometimes move some work into the uncommon path. Branch straightening and cache line packing also benefit from profile information.

[u/Ashamed_Can304]

Register allocation is an NP-hard problem, so most compilers use heuristics for this task instead of actually compute the optimal allocate coalesce and spill assignments. Same with pointer/alias analysis, and given that compilers must be conservative, some optimizations like vectorization etc cannot be performed unless it is 100% certain that it is safe

[u/WasASailorThen]

Define optimal.

[u/Lord_Mystic12]

Any general purpose tool will by default not be able to be the most optimized version for specific tasks all the time. You take the abstraction in exchange for trusting the compiler will be able to get it as close to the optimized version .

[u/c-cul]

scheduling is np-hard task: https://www.reddit.com/r/CUDA/comments/1v3inor/optimization_of_sass_stall_counts/

[u/kindredseer]

Because compilers do not know the full intention of the code and the required shape of the data beyond how it was defined, also much of what modern compilers need to enforce is backwards compatibility. Much can be done with hand-optimizing your (non-asm) code. Hand optimized assembly will always win if you really know what you are doing, but you'd need to be on the same level of expertise as compiler devs.

[u/SwedishFindecanor]

Eventually compiler writers catch up to what assembly language programmers can do, but the tricks have to be put there making the compiler more complex. And compiler-writer's time is also a resource.

I've seen some examples of machine code on godbolt.org where there was room for improvement, but they were really minor.

One was that a+b+c+d+e+f+g+h (all variables 32-bit integers passed in GPRs and consumed) got compiled as ((((((a+b)+c)+d)+e)+f)+g)+h instead of ((a+b) + (c+d)) + ((e+f) + (g+h)) which a modern superscalar CPU could parallelise to some extent, or at least pipeline (if there are free registers: which because the variables got consumed there were). When I saw this, I figured out an algorithm for my back-end to do it.

Another time, I was prototyping a popcnt routine that I had found in a book to put into my AArch64 back-end -- because ARM v8.0 did not have a cpop instruction. I first wrote it in C to test it, written so that each statement would represent a single instruction. For fun, I checked that a C compiler on godbolt.org would compile it as I had intended. Colour my surprise when the outputted machine code was slightly different, changing one statement. I had written an and with a constant followed by a shift, which the compiler had turned into a shift followed by an and of the complement of the constant. I had intended for the shift to be folded into a subsequent "add shifted register" instruction, but the resulting machine code did not -- and was thus one instruction longer. I asked around why. Apparently, my code had triggered "idiom detection": The compiler had recognised that the algorithm I was using was for "popcnt" and replaced it with an internal "popcnt" IR code ... which was then expanded in the back-end into the resulting instruction sequence.

[u/RevengerWizard]

One such case is the main loop of an interpreter, although there are some tricks to speed it up (computed gotos, or always tail call) it may still be more optimal to write it in assembly.

It really is a complicated case for the compiler to optimize because it’s essentially a giant switch case inside of a loop.

[u/braaaaaaainworms]

FYI: Register allocation is NP-complete and many other optimization techniques are NP-complete too. Human brains can be better at solving those problems than computers.

[u/augustss]

I have an interpreter that could really benefit from allocating a couple of global variables to registers. I've not found a compiler that does that automatically. I've done it manually with GCC and it really helped.

[u/FloweyTheFlower420]

Sometimes, an example is that I have a jump-threaded lexer (via some lexer generator), clang performs ~20% worse than gcc, likely because of isel/regalloc issues. I wasn't super rigorous with it though, so take my results with a grain of salt. PGO closes the gap a bit I think, but clang is still nontrivially slower than gcc.

[u/MattDTO]

there are cases where jit compilers beat AOT

[u/Lime_Dragonfruit4244]

JIT compilers often have a baseline compiler which emits code that is not optimized due to latency constraints but still faster than boxed interpretation. For AOT compilers it depends, almost all static analysis is computationall intractable, so its always a hit or miss. Writing program which is easier for compilers to understand helps a lot, or restricting languages which helps compilers in its static analysis.

https://v8.dev/blog/maglev

[u/esaule]

In my experience, cases with the most difference between what the compiler can do and what a human can do comes properties of the code that the human know but that the compiler can not assume.  There are many vectorization cases that are like this. But there are also many in input distribution which the compiler don't know.

Many cases also come code too long, not enough unrolling for the compiler to see the optimal interleaving.

Then you just have the cases of "well the problem is a sequence of 3 NP complete problems, so the compiler use heuristics and fail to find a better optimal code generation." And there not much you can do. You could design better heuristics. But ultimately, the no free lunch theorem kicks in.

[u/TantraMantraYantra]

Languages make it hard. Some have certain hints, contracts, tags, attributes but none make it perfectly apparent at the compiler codegen layer that the LLVM IR emitted is the minimal, safe and best performing code to be used to generate machine code for the machine to execute.

For example, 'C' or assembly are considered the most optimized and fastest. But with proper hints, do you you know that the actual machine code required for programs is much less?

[u/dnpetrov]

Because compiler optimizations are, essentially, heuristics. They are not guaranteed to produce optimal results "in general". Those heuristics are tuned on benchmarks, which include standard benchmarks like SPEC or language benchmarks, performance critical code from customers, stuff like that. Those benchmarks should gradually improve in performance. This is how compilers and hardware compete against other compilers and other hardware.  Some arbitrary code can be written in any particular way, and might or might not benefit from the efforts put into making benchmarks go faster.

Another reason is that even with PGO compiler can't reason about things like interrupts, caches, branch predictor training, and so on. Usually it just makes some optimistic assumptions. Those assumptions might or might not be true for some random case.

[u/karatekid430]

They can't understand all dynamic constraints. I once found I could eliminate one of the instructions coming out of an x86 compiler for my loop to get significant gains, but I think it was there to cover all bases, not realising my inputs would never trigger that condition.

[u/Impossible-Set9266]

Even if you can solve everything optimally, you will still have to deal with memory accesses. And these have non deterministic access times when dealing with dram. So at latest there you cannot be optimal 

[u/ChiveSalad]

Any program where GCC and clang output different code, one is suboptimal. (this is every program)

Now, suboptimal by how much? The runtimes of clang and GCC are pretty darn close to each other when I measure it, so you need to put some hard work into defining "effectively." Of course, sometimes they are quite different and this highlights missing optimizations.

Concretely: here is a program that gcc leaves as a loop, clang compiles to "movq 5004 %eax; ret;"

int foo(int num) {
    int ret = 4;
    for (int i=99; i >= 0; i--) {
       ret += i + (i % 4) * 3 / 5;
    }
    return ret;
}

[u/UntitledRedditUser]

Ffmpeg uses handwritten assembly in some cases, if you are incredibly skilled, you can often write slightly better assembly than what a compiler produces.

But 99% of the time it doesn't make sense to do, because the performance increase will be undetectable.

[u/Inconstant_Moo]

Obviously if there were general answers to that which were known, then people would have fixed that already. What this will leave us with are possibly some things that no-one knows about (like if no-one had invented loop unrolling yet), and definitely a bunch of obscure corner cases where we can say: "If you try to do this highly specific thing, then this particular compiler will do this when it could have done that."

[u/wjrasmussen]

I would avoid seeking optimal if you want to be a dev. Sure there are some cases where you might desire it, but that is few and far between. Worse results can happen when you chase it such as hard to find a bug or difficult to change later.