9 ms·

You can't fool the optimizer

267 points by HeliumHydride 10mo ago

jagged-chisel 10mo ago
I always code with the mindset “the compiler is smarter than me.” No need to twist my logic around attempting to squeeze performance out of the processor - write something understandable to humans, let the computer do what computers do.
- qsort 10mo ago
  > I always code with the mindset “the compiler is smarter than me.” Like with people in general, it depends on what compiler/interpreter we're talking about, I'll freely grant that clang is smarter than me, but CPython for sure isn't. :) More generally, canonicalization goes very far, but no farther than language semantics allows. Not even the notorious "sufficiently smart compiler" with infinite time can figure out what you don't tell it.
  - manbitesdog 10mo ago
    To add to this, the low-level constraints also make this assumption noisy, no matter how smart the compiler is. On the CPython case, if you do `dis.dis('DAY = 24 * 60 * 60)` you will see that constant folding nicely converts it to `LOAD_CONST 86400`. However, if you try `dis.dis('ATOMS_IN_THE_WORLD = 10*50')` you will get LOAD_CONST 10, LOAD_CONST 50, BINARY_OP **.
    - zbentley 10mo ago
      > However, if you try `dis.dis('ATOMS_IN_THE_WORLD = 10*50')` you will get LOAD_CONST 10, LOAD_CONST 50... I do not get that, I get LOAD_CONST 500. Tested on: Python 3.9.3 MacOS (Apple provided), 3.13.3 (uv provided) MacOS and Linux, and 3.14.0 (uv provided) MacOS and Linux.
      - manbitesdog 10mo ago
        Sorry, I meant 10**50; HN formatting removed one asterisk
        zbentley 10mo ago
        Ah, gotcha. Yep! Not constant-calculated at all!
- adrianN 10mo ago
  This is decent advice in general, but it pays off to try and express your logic in a way that is machine friendly. That mostly means thinking carefully about how you organize the data you work with. Optimizers generally don't change data structures or memory layout but that can make orders of magnitude difference in the performance of your program. It is also often difficult to refactor later.
  - lou1306 10mo ago
    To make a more specific example, if you malloc()/free() within a loop, it's unlikely that the compiler will fix that for you. However, moving those calls outside of the loop (plus maybe add some realloc()s within, only if needed) is probably going to perform better.
    - adrianN 10mo ago
      That is something that can be easily found and usually fixed with trivial profiling. I'm more talking about data locality instead of pointer chasing. Once you set up a pointer-chasing data infrastructure changing that means rewriting most of your application.
  - amiga386 10mo ago
    I find the same too. I find gcc and clang can inline functions, but can't decide to break apart a struct used only among those inlined functions and make every struct member a local variable, and then decide that one or more of those local variables should be allocated as a register for the full lifetime of the function, rather than spill onto the local stack. So if you use a messy solution where something that should be a struct and operated on with functions, is actually just a pile of local variables within a single function, and you use macros operating on local variables instead of inlineable functions operating on structs, you get massively better performance. e.g. /* slower */ struct foo { uint32_t a,b,c,d,e,f,g,h; } uint32_t do_thing(struct foo *foo) { return foo->a ^ foo->b ^ foo->c ^ foo->d; } void blah() { struct foo x; for (...) { x.e = do_thing(&x) ^ x.f; ... } } /* faster */ #define DO_THING (a^b^c^d) void blah() { uint32_t a,b,c,d,e,f,g,h; for (...) { e = DO_THING ^ f; ... } }
- tonyhart7 10mo ago
  also not all software need optimization to the bone pareto principle like always, dont need the best but good enough not every company is google level anyway
- ErroneousBosh 10mo ago
  You say that, but I was able to reduce the code size of some avr8 stuff I was working on by removing a whole bunch of instructions that zero out registers and then shift a value around. I don't it to literally shift the top byte 24 bits to the right and zero out the upper 24 bits, I just need it to pass the value in the top 8 bits direct to the next operation. I agree that most people are not writing hand-tuned avr8 assembly. Most people aren't attempting to do DSP on 8-bit AVRs either.
- IshKebab 10mo ago
  The fact that compilers are smart isn't an excuse to not think about performance at all. They can't change your program architecture, algorithms, memory access patterns, etc. You can mostly not think about super low level integer manipulation stuff though.
- jaccola 10mo ago
  I would take it one step further, often trying to eke out performance gains with clever tricks can hurt performance by causing you to "miss the forest for the trees". I work with Cuda kernels a lot for computer vision. I am able to consistently and significantly improve on the performance of research code without any fancy tricks, just with good software engineering practices. By organising variables into structs, improving naming, using helper functions, etc... the previously impenetrable code becomes so much clearer and the obvious optimisations reveal themselves. Not to say there aren't certain tricks / patterns / gotchas / low level hardware realities to keep in mind, of course.
- flohofwoe 10mo ago
  > I always code with the mindset “the compiler is smarter than me.” ...I don't know... for instance the MSVC compiler creates this output for the last two 'non-trivial' functions with '/Ox': add w8,w1,w0 cmp w0,#0 cseleq w0,w1,w8 Even beginner assembly coders on their first day wouldn't write such bullshit :) A better mindset is "don't trust the compiler for code that's actually performance sensitive". You shouldn't validate each line of compiler output, but at least for the 'hot areas' in the code base that definitely pays off, because sometimes compilers do really weird shit for no good reason (often because of 'interference' between unrelated optimizer passes) - and often you don't need to dig deep to stumble over weird output like in the example above.
  - sumtechguy 10mo ago
    I see the msvc arm compiler has not improved much in 20 years. The msvc arm was pretty odd when we used it in ~2003. We did not trust it at all. Think we had to get 4 or so compiler fixes out of MS for that project plus 3 or 4 library fixes. The x86 one was pretty solid. We were targeting 4 different CPU platforms at the same time so we could find things like that decently quickly. Most of the the time it was something we did that was weird. But even then we would find them. That one looks like maybe the optimizer back filled a nop slot?
- wavemode 10mo ago
  This is very often true when your data is sitting right there on the stack. Though when your data is behind pointers, it's very easy to write code that the compiler can no longer figure out how to optimize.
- wat10000 10mo ago
  I would modify this a bit. Someone with decent computer architecture knowledge, tools, and time can generally do better than the compiler. But you generally won't, because you have a lot of other things to think about. So I'd state this as, "the compiler is more diligent and consistent than me." It's not so much that it can spot a for loop that's equivalent to a single add, but that it will spot it just about every time, so you don't have to worry about it.
- stonemetal12 10mo ago
  I go with "You are responsible for the algorithms, it is responsible for the code micro optimizations". The compiler can't optimize you out of an SQL N+1 situation, that is on me to avoid, but it is better than me at loop unrolling.
- mamcx 10mo ago
  > “the compiler is smarter than me.” This is true, but it also means "the compiler IS made for someone median smart, that now knows the machine". It works great for basic, simple, common code, and for code that is made with care for data structures. A total mess of code is another story. P.D: is similar to the query optimizers, that neither can outrun a terrible made schema and queries
- moregrist 10mo ago
  There are optimizations that a compiler can perform; usually these are code transformations. Modern optimizing compilers usually get these right. The optimizations that tend to have the most impact involve changes to the algorithm or data layout. Most compilers won’t do things like add a hash table to make a lookup O(1) or rearrange an array of structures to be a structure of arrays for better data locality. Coding with an eye for these optimizations is still a very good use of your time.
- kragen 10mo ago
  > I always code with the mindset “the compiler is smarter than me.” That mindset will last until the first or second time you walk through the compiler's assembly-language output. GCC and LLVM can find some amazing optimizations, but they also consistently miss very obvious optimization opportunities, often even on utterly trivial code. That isn't to say that it's worthwhile to hand-optimize all your code. But the compiler is very much not smarter than you, and if you do need to squeeze performance out of the processor, you can do a lot better than the compiler does. A good first step is to look at the stupid shit the compiler has spat out and massage your source code until the shit stinks less.
barishnamazov 10mo ago
Sometimes you can fool the compiler :-) See "Example 2: Tricking the compiler" in my blog post about O3 sometimes being slower than O2: https://barish.me/blog/cpp-o3-slower/ https://barish.me/blog/cpp-o3-slower/
317070 10mo ago
"The compiler" and "The optimizer" are doing a lot of the heavy lifting here in the argument. I definitely know compilers and optimizers which are not that great. Then again, they are not turning C++ code into ARM instructions. You absolutely can fool a lot of compilers out there! And I am not only looking at you, NVCC.
- Almondsetat 10mo ago
  But the point should be to follow the optimization cycle: develop, benchmark, evaluate, profile, analyze, optimize. Writing performant code is no joke and very often destroys readability and introduces subtle bugs, so before trying to oursmart the compiler, evaluate if what it produces is good enough already
amelius 10mo ago
One undesirable property of optimizers is that in theory one day they produce good code and the next day they don't.
- titzer 10mo ago
  These situations are known as "performance cliffs" and they are particularly pernicious in optimizing dynamic languages like JavaScript, where runtime optimization happens that depends not just on the program's shape, but its past behavior.
sureglymop 10mo ago
With this one I instead wondered: If there are 4 functions doing exactly the same thing, couldn't the compiler also only generate the code for one of them? E.g. if in `main` you called two different add functions, couldn't it optimize one of them away completely? It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? Why doesn't it do that?
- cyco130 10mo ago
  It would but it's harder to trigger. Here, it's not safe because they're public functions and the standard would require `add_v1 != add_v2` (I think). If you declare them as static, it eliminates the functions and the calls completely: https://aoco.compiler-explorer.com/z/soPqe7eYx https://aoco.compiler-explorer.com/z/soPqe7eYx I'm sure it could also perform definition merging like you suggest but I can't think of a way of triggering it at the moment without also triggering their complete elision.
- moefh 10mo ago
  > It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? It can't do that because the program might load a dynamic library that depends on the function (it's perfectly OK for a `.so` to depend on a function from the main executable, for example). That's one of the reasons why a very cheap optimization is to always use `static` for functions when you can. You're telling the compiler that the function doesn't need to be visible outside the current compilation unit, so the compiler is free to even inline it completely and never produce an actual callable function, if appropriate.
  - bruce343434 10mo ago
    Sadly most C++ projects are organized in a way that hampers static functions. To achieve incremental builds, stuff is split into separate source files that are compiled and optimized separately, and only at the final step linked, which requires symbols of course. I get it though, because carefully structuring your #includes to get a single translation unit is messy, and compile times get too long.
daft_pink 10mo ago
Is this an argument for compiled code?
- 0xTJ 10mo ago
  It's not really an argument for anything, it's just showing off how cool compilers are!
mkornaukhov 10mo ago
Better tell me how to make the compiler not fool me!
Scene_Cast2 10mo ago
This post assumes C/C++ style business logic code. Anything HPC will benefit from thinking about how things map onto hardware (or, in case of SQL, onto data structures). I think way too few people use profilers. If your code is slow, profiling is the first tool you should reach for. Unfortunately, the state of profiling tools outside of NSight and Visual Studio (non-Code) is pretty disappointing.
- layer8 10mo ago
  I don’t disagree, but profiling also won’t help you with death by a thousand indirections.
  - lmm 10mo ago
    Sure, but that's mostly a myth.
    - 1718627440 10mo ago
      So how do you see in a profiler, that everything is 1.2x slower than it could be?
      - lmm 10mo ago
        No-one's getting out of bed for 1.2x.
        1718627440 10mo ago
        Depends. If you have a real-time system, that might very well will be what you chase after. Also why not make your program a bit faster when it is no work, by starting it the right way upfront. I mean I wouldn't rewrite a program for this, but when I program some new part and I can avoid an indirection, why not do it? Less complexity, less (failure) state, better performance.
        10mo ago
asah 10mo ago
I want an AI optimization helper that recognizes patterns that could-almost be optimized if I gave it a little help, e.g. hints about usage, type, etc.
- Jaxan 10mo ago
  Why does it have to be AI?
stabbles 10mo ago
For people who enjoy these blogs, you would definitely like the Julia REPL as well. I used to play with this a lot to discover compiler things. For example: $ julia julia> function f(n) total = 0 for x in 1:n total += x end return total end julia> @code_native f(10) ... sub x9, x0, #2 mul x10, x8, x9 umulh x8, x8, x9 extr x8, x8, x10, #1 add x8, x8, x0, lsl #1 sub x0, x8, #1 ret ... it shows this with nice colors right in the REPL. In the example above, you see that LLVM figured out the arithmetic series and replaced the loop with a simple multiplication.
- lifthrasiir 10mo ago
  This and add_v3 in the OP fall into the general class of Scalar Evolution optimizations (SCEV). LLVM for example is able to handle almost all Brainfuck loops in practice---add_v3 indeed corresponds to a Brainfuck loop `[->+<]`---, and its SCEV implementation is truly massive: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/ScalarEvolution.cpp https://github.com/llvm/llvm-project/blob/main/llvm/lib/Anal...
- Someone 10mo ago
  LLVM can do more complex sums, too. See https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo...
- eigenspace 10mo ago
  Another nice thing in julia is that if you dont want the optimizer to delete something, you can just ask it nicely :) julia> function f(n) total = 0 for x in 1:n total += Base.donotdelete(x) end return total end will keep the loop
matja 10mo ago
You can fool the optimizer, but you have to work harder to do so: unsigned add(unsigned x, unsigned y) { unsigned a, b; do { a = x & y; b = x ^ y; x = a << 1; y = b; } while (a); return b; } becomes (with armv8-a clang 21.1.0 -O3) : add(unsigned int, unsigned int): .LBB0_1: ands w8, w0, w1 eor w1, w0, w1 lsl w0, w8, #1 b.ne .LBB0_1 mov w0, w1 ret
- thaumasiotes 10mo ago
  Since I had to think about it: unsigned add(unsigned x, unsigned y) { unsigned a, b; do { a = x & y; /* every position where addition will generate a carry */ b = x ^ y; /* the addition, with no carries */ x = a << 1; /* the carries */ y = b; /* if there were any carries, repeat the loop */ } while (a); return b; } It's easy to show that this algorithm is correct in the sense that, when b is returned, it must be equal to x+y. x+y summing to a constant is a loop invariant, and at termination x is 0 and y is b. It's a little more difficult to see that the loop will necessarily terminate. New a values come from a bitwise & of x and y. New x values come from a left shift of a. This means that, if x ends in some number of zeroes, the next value of a will also end in at least that many zeroes, and the next value of x will end in an additional zero (because of the left shift). Eventually a will end in as many zeroes as there are bits in a, and the loop will terminate.
  - gfaster 10mo ago
    In C, I'm pretty confident the loop is defined by the standard to terminate. Also I did take the excuse to plug it (the optimized llvm ir) into Alive: https://alive2.llvm.org/ce/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:14,j:1,lang:llvm,selection:(endColumn:8,endLineNumber:1,positionColumn:8,positionLineNumber:1,selectionStartColumn:8,selectionStartLineNumber:1,startColumn:8,startLineNumber:1),source:'define+i32+@src(i32+noundef+%25x,+i32+noundef+%25y)+%7B%0Aentry:%0A++br+label+%25do.body%0A%0Ado.body:%0A++%25y.addr.0+%3D+phi+i32+%5B+%25y,+%25entry+%5D,+%5B+%25xor,+%25do.body+%5D%0A++%25x.addr.0+%3D+phi+i32+%5B+%25x,+%25entry+%5D,+%5B+%25shl,+%25do.body+%5D%0A++%25and+%3D+and+i32+%25x.addr.0,+%25y.addr.0%0A++%25xor+%3D+xor+i32+%25x.addr.0,+%25y.addr.0%0A++%25shl+%3D+shl+i32+%25and,+1%0A++%25tobool.not+%3D+icmp+eq+i32+%25and,+0%0A++br+i1+%25tobool.not,+label+%25do.end,+label+%25do.body%0A%0Ado.end:%0A++ret+i32+%25xor%0A%7D%0A%0Adefine+i32+@tgt(i32+noundef+%25x,+i32+noundef+%25y)+%7B%0A++++%25add+%3D+add+i32+%25x,+%25y%0A++++ret+i32+%25add%0A%7D'),l:'5',n:'0',o:'LLVM+IR+source+%231',t:'0')),k:49.32378679395386,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:alive,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'1',trim:'1'),fontScale:14,j:1,lang:llvm,libs:!(),options:'',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'alive-tv+(Editor+%231,+Compiler+%231)+LLVM+IR',t:'0')),k:50.67621320604614,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://alive2.llvm.org/ce/#g:!((g:!((g:!((h:codeEditor,i:(f...
raverbashing 10mo ago
I'm curious what is the theoreme-proving magic behind add_v4 and if this is prior LLVM ir
Joker_vD 10mo ago
Wait, why does GAS use Intel syntax for ARM instead of AT&T? Or something that looks very much like it: the destination is the first operand, not the last, and there is no "%" prefix for the register names?
- Karliss 10mo ago
  That's not Intel syntax that's more or less ARM assembly syntax as used by ARM documentation. Intel vs AT&T discussion is primarily relevant only for x86 and x86_64 assembly. If you look at GAS manual https://ftp.gnu.org/old-gnu/Manuals/gas-2.9.1/html_chapter/as_toc.html https://ftp.gnu.org/old-gnu/Manuals/gas-2.9.1/html_chapter/a... almost every other architecture has architecture specific syntax notes, in many cases for something as trivial comments. If they couldn't even decide on single symbols for comments, there is no hope for everything else. ARM isn't the only architecture where GAS uses similar syntax as developers of corresponding CPU arch. They are not doing the same for X86 due to historical choices inherited from Unix software ecosystem and thus AT&T. If you play around on Godbolt with compilers for different architectures it seems like x86 and use AT&T syntax is the exception, there are a few other which use similar syntax but it's a minority. Why not use same syntax for all architectures? I don't really know all the historical reasoning but I have a few guesses and each arch probably has it's own historic baggage. Being consistent with manufacturer docs and rest of ecosystem has the obvious benefits for the ones who need to read it. Assembly is architecture specific by definition so being consistent across different architectures has little value. GAS is consistent with GCC output. Did GCC added support for some architectures early with the with help of manufacturers assembler and only later in GAS? A lot of custom syntax quirks which don't easily fit into Intel/AT&T model and are related to various addressing modes used by different architectures. For example ARM has register postincrement/preincrement and the 0 cost shifts, arm doesn't have the subregister acess like x86 (RAX/EAX/AX/AH/AL) and non word access is more or less limited to load/store instructions unlike x86 where it can show up in more places. You would need to invent quite a few extensions for AT&T syntax for it to be used by all the non x86 architectures, or you could just use the syntax made by developer of architecture.
  - Joker_vD 10mo ago
torginus 10mo ago
Awesome blog post - thanks to this I found out that you can view what the LLVM optimizer pipeline does, and which pass is actually responsible for doing which instruction. It's super cool to see this in practice, and for me it helps putting more trust in the compiler that it does the right thing, rather than me trying to micro-optimize my code and peppering inline qualifiers everywhere.
dlenski 10mo ago
Today I learned that Matt Godbolt is British!
jmcomets 10mo ago
Obvious caveat: pushing this a bit further it can quickly fallback to the default case. The optimizer is a superpower but you still need to try to write efficient code. unsigned add_v5(unsigned x, unsigned y) { if (x == y) return 2 * x; return x + y; } Results in: add_v5(unsigned int, unsigned int): lsl w8, w0, #1 add w9, w1, w0 cmp w0, w1 csel w0, w8, w9, eq ret (armv8-a clang 21.1.0 with O3) If compiler folks can chime in, I'm curious why incrementing in a loop can be unrolled and inspected to optimize to an addition, but doubling the number when both operands are equal can't?
- Someone 10mo ago
  > I'm curious why incrementing in a loop can be unrolled and inspected to optimize to an addition, but doubling the number when both operands are equal can’t? I expect because the former helps more in optimising real-world code than the latter. It’s not worth the LLVM developer's time to make the compiler better for programs that it won’t see in practice. It’s not as if the compiler did nothing with that code, though. It replaced the multiplication by a left shift and removed the branch.
- DullPointer 10mo ago
  I’m not a compiler expert, an assembly expert or an ARM expert, so this may be wildly wrong, but this looks optimized to me. The trick is that it’s doing both the add and the left shift in parallel then selecting which to use based on a compare of the two values with csel. (To see this, rather than reading the code sequentially, think of every instruction as being issued at the same time until you hit an instruction that needs a destination register from an earlier instruction) The add is stored in W9 but only read if the two arguments are unequal. If the compare succeeds and the lsl retires before the add, the add is never read, so nothing stalls waiting for it and the answer can be returned while the add is still in flight. The result of the add would then be quietly discarded assuming it ever started (maybe there’s some magic where it doesn’t even happen at all?). It’s not clear to me that this is power efficient, or that on many real cpus there’s a latency difference to exploit between add and lsl, so it may not be faster than just unconditionally doing the addition. That said, it is definitely faster than the code as it was written which if translated to asm verbatim stalls on the compare before executing either the add or the left shift.
anon-3988 10mo ago
What I am curious about is, is the compiler smart enough to be lazy with computation and or variables? For example consider: let a = expr let b = expr2 if (a || b) { return true; } is the compiler allowed to lazily compute this if it is indeed faster to do that way? Or declaring a bunch of variables that may or may not be used in all of the branches. Is the compiler smart enough to only compute them whenever it is necessary? AFAIK this is now allowed in C-like languages. Things have to materialize. Another one is, I like to do memcpy every single time eventhough it might not even be used or overwritten by other memcpys. Is the compiler smart enough to not perform those and reorder my program so that only the last relevant memcpy is performed? A lot of times, my code becomes ugly because I don't trust that it does any of this. I would like t write code in consistent and simple ways but I need compilers to be much smarter than it is today. A bad example recently is something like const S * s =; let a = constant; let b = constant; let c = constant; let d = constant; let e = constant; let f = constant; let g = constant; let h = constant; let i = constant; let j = constant; let k = constant; let l = constant; if (s->a == a && s->b == b /* etc */ ) { return true; } It did not turn all of this into a SIMD mask or something like that.
- jcranmer 10mo ago
  > Is the compiler smart enough to only compute them whenever it is necessary? This is known as "code sinking," and most optimizers are capable of doing this. Except keep in mind that a) the profitability of doing so is not always clear [1] and b) the compiler is a lot more fastidious about corner-case behavior than you are, so it might conclude that it's not in fact safe to sink the operation when you think it is safe to do so. [1] If the operation to sink is x = y + z, you now may need to keep the values of y and z around longer to compute the addition, increasing register pressure and potentially hurting performance as a result.
- Denvercoder9 10mo ago
  > It did not turn all of this into a SIMD mask or something like that. Did you try using bitwise and (&), or a local for the struct? The short-circuiting behaviour of the logical means that if `s->a != a`, `s->b` must not be dereferenced, so the compiler cannot turn this into a SIMD mask operation, because it behaves differently. Generally compilers are pretty smart these days, and I find that more often than not if they miss an "obvious" optimization it's because there's a cornercase where it behaves differently from the code I wrote.
Scubabear68 10mo ago
I liked the idea behind this post, but really the author fairly widely missed the mark in my opinion. The extent to which you can "fool the optimizer" is highly dependent on the language and the code you're talking about. Python is a great example of a language that is devilishly hard to optimize for precisely because of the language semantics. C and C++ are entirely different examples with entirely different optimization issues, usually which have to do with pointers and references and what the compiler is allowed to infer. The point? Don't just assume your compiler will magically make all your performance issues go away and produce optimal code. Maybe it will, maybe it won't. As always, the main performance lessons should always be "1) Don't prematurely optimize", and "2) If you see perf issues, run profilers to try to definitively nail where the perf issue is".
- gpderetta 10mo ago
  I think the author is strictly talking about C and C++. Python is famously pessimal in all possible ways.
  - Scubabear68 10mo ago
    Digging around, OK that makes sense. But even in the context of C and C++, there are often more ways the compiler can't help you than ways it can. The most common are on function calls involving array operations and pointers, but a lot of it has to do with the C/C++ header and linker setup as well. C and C++ authors should not blithely assume the compiler is doing an awesome job, and in my experience, they don't.
    - gpderetta 10mo ago
      > C and C++ authors should not blithely assume the compiler is doing an awesome job Agree. And I'm sure the author agrees as well. That's why compiler-explorer exists in the first place.
gpderetta 10mo ago
Interesting, even this can't fool the optimizer (tried with a recent gcc and clang): unsigned add(unsigned x, unsigned y) { std::vector vx {x}; std::vector vy {y}; auto res = vx[0]+vy[0]; return res; }
senfiaj 10mo ago
I wonder if compilers do multiple passes on the intermediate code in order to optimize / simplify it. For example, during each pass the optimizer searches some known harcoded patterns and replaces them with something else and repeats until no possible improvement is found. Also optimizers have a limit, they can't reason as abstractly as humans, for example: bool is_divisible_by_6(int x) { return x % 2 == 0 && x % 3 == 0; } bool is_divisible_by_6_optimal(int x) { return x % 6 == 0; } I tried with both gcc and clang, the asm code for is_divisible_by_6 is still less optimal. So no, there are plenty of easy ways to fool the optimizer by obfuscation. The morale is that you still have to optimize algorithms (O notation) and math operations / expressions.
- jakobnissen 10mo ago
  They do, and the order of the passes matter. Sometimes, optimizations are missed because they require a certain order of passes that is different from the one your compiler uses. On higher optimization levels, many passes occur multiple times. However, as far as I know, compilers don't repeatedly run passes until they've reached an optimum. Instead, they run a fixed series of passes. I don't know why, maybe someone can chime in.
  - titzer 10mo ago
    It's a long-standing problem in compilers, often referred to as the "phase ordering problem". In general, forward dataflow optimizations can be combined if they are monotonic (meaning, never make the code worse, or at least, never undo a previous step. It's possible to run forward dataflow problems together repeatedly to a fixpoint. In TurboFan a general graph reduction algorithm is [1] instantiated with a number of reducers, and then a fixpoint is run. The technique of trying to combine multiple passes has been tried a number of times. What doesn't seem so obvious is how to run optimizations that are not traditional forward dataflow problems or are indeed backward dataflow problems (like DCE) together with other transformations. Generally compilers get tuned by running them on lots of different kinds of code, often benchmarks, and then tinkering with the order of passes and other heuristics like loop unroll factors, thresholds for inlining, etc, and seeing what works best. [1]was? TurboFan seems to have splintered into a number of pieces being reused in different ways these days
derefr 10mo ago
Even better / potentially more surprising: unsigned mult(unsigned x, unsigned y) { unsigned y0 = y; while (x--) y = add_v1(y, y0); return y; } optimizes to: mult(unsigned int, unsigned int): madd w0, w1, w0, w1 ret (and this produces the same result when substituting any of the `add_vN`s from TFA)
deleted 10mo ago
[deleted]
Findecanor 10mo ago
I'm wondering how the compiler optimised add_v3() and add_v4() though. Was it through "idiom detection", i.e. by recognising those specific patterns, or did the compiler deduce the answers them through some more involved analysis?
- fooyc 10mo ago
  add_v3() is the result of induction variable simplification: https://llvm.org/doxygen/IndVarSimplify_8cpp_source.html https://llvm.org/doxygen/IndVarSimplify_8cpp_source.html
- j2kun 10mo ago
  Scalar Evolution is one way loops can be simplified
abainbridge 10mo ago
The examples are fun, but rather than yet another article saying how amazing optimizing compilers are (they are, I already know), I'd probably benefit more from an article explaining when obvious optimizations are missed and what to do about it. Some boring examples I've just thought of... eg 1: int bar(int num) { return num / 2; } Doesn't get optimized to a single shift right, because the that won't work if num is negative. In this case we can change the ints to unsigneds to tell the compiler we know the number isn't negative. But it isn't always easy to express to the compiler everything you know about your data and use case. There is an art in knowing what kinds of things you need to tell the compiler in order to unlock optimizations. eg 2: int foo(void) { return strlen("hello"); } We all know that strlen will return 5, but some compilers don't: https://godbolt.org/z/M7x5qraE6 https://godbolt.org/z/M7x5qraE6 eg 3: int foo(char const *s) { if (strlen(s) < 3) return 0; if (strcmp(s, "hello") == 0) return 1; return 0; } This function returns 1 if s is "hello". 0 otherwise. I've added a pointless strlen(). It seems like no compiler is clever enough to remove it. https://godbolt.org/z/Koj65eo5K https://godbolt.org/z/Koj65eo5K. I can think of many reasons the compiler isn't able to spot this.
- commandlinefan 10mo ago
  > won't work if num is negative I remember reading (although I can't find it now) a great analysis of all the optimizations that Javascript compilers _can't_ do because of the existence of the "eval" instruction.
  - astrange 10mo ago
    A JIT can do any optimization it wants, as long as it can deoptimize if it turns out it was wrong.
    - adrianN 10mo ago
      You also want to prove that the „optimization“ doesn’t make things slower.
      - 10mo ago
CodeArtisan 10mo ago
Recursive Popcount: unsigned int popcount(unsigned int n) { return (n &= n - 1u) ? (1u + popcount(n)) : 0u; } Clang 21.1 x64: popcount: mov eax, -1 .LBB0_1: lea ecx, [rdi - 1] inc eax and ecx, edi mov edi, ecx jne .LBB0_1 ret GCC 15.2: popcount: blsr edi, edi popcnt eax, edi ret Both compiled with -O3 -march=znver5
- pbsd 10mo ago
  Because the function is not quite correct. It should be return n ? (1u + popcount(n & n - 1u)) : 0u; which both Clang and GCC promptly optimize to a single popcnt.
  - 1718627440 10mo ago
    There should be testsuites, which are based on testing which compilation passes the compiler chose.
norir 10mo ago
For me, compiler optimization is a mixed bag. On the one hand, they can facilitate the generation of higher performance runtime artifacts, but it comes at significant cost, often I believe exceeding the value they provide. They push programs in the direction of complexity and inscrutability. They make it harder to know what a function _actually_ does, and some even have the ability to break your code. In the OP examples, instead of optimization, what I would prefer is a separate analysis tool that reports what optimizations are possible and a compiler that makes it easy to write both high level and machine code as necessary. Now instead of the compiler opaquely rewriting your code for you, it helps guide you into writing optimal code at the source level. This, for me, leads to a better equilibrium where you are able to express your intent at a high level and then, as needed, you can perform lower level optimizations in a transparent and deterministic way. For me, the big value of existing optimizing compilers is that I can use them to figure out what instructions might be optimal for my use case and then I can directly write those instructions where the highest performance is needed. But I do not need to subject myself to the slow compilation times (which compounds as the compiler repeatedly reoptimizes the same function thousands of times during development -- a cost that is repeated with every single compilation of the file) nor the possibility that the optimizer breaks my code in an opaque way that I won't notice until something bad and inscrutable happens at runtime.
msarnoff 10mo ago
I was very surprised that GCC could optimize NEON SIMD intrinsics. After spending hours trying to optimize my vector code, trying to get the spacing between register dependencies right to reduce stalls, breaking long reduction operations into intermediate results, messing with LLVM-MCA, etc., I realized that I just couldn’t beat the compiler. It was doing its best to allocate registers and reorder instructions to keep the pipeline filled. I don’t think it always did the best job and saw a bunch of register spills I thought were unnecessary, but I couldn’t justify the time and effort to do it in assembly…
WalterBright 10mo ago
There are general optimizations, based on DFA (Data Flow Analysis). These recognize things like loops, loop invariants, dead code, copy propagation, constant propagation, common subexpressions, etc. Then, there are is a (very long) list of checks for specific patterns and replacing them with shorter sequences of code, things like recognizing the pattern of bswap and replacing it with a bswap instruction. There's no end to adding patterns to check for.
- DannyBee 10mo ago
  This is true but there is actually an end ;) There are limits on provable equivalence in the first place. things like equality saturation also try and do a better job of formalizing equivalence based rewrites.
bgbntty2 10mo ago
I'm not well-versed in compilers, so it was a bit surprising to see how it optimizes all the add_vX functions. What I most enjoyed, though, was how the guy in the video (linked at the bottom of the article) was typing - a mistake on every few characters. Backspace was likely his most-used key. I found it encouraging, somehow. I know typing speed or correctness isn't really important for coders, but I always felt like I'm behind others with regards to typing, even though when I really concentrate, I do good on those online typing tests. Even when writing this comment, I made like 30 mistakes. Probably an useless comment, but it may give some people hope or validation if they feel like they not great typists.
anonymousiam 10mo ago
Sometimes you can fool the (C) optimizer by using the 'volatile' keyword in front of a variable in code that would otherwise be optimized out. https://www.embeddedrelated.com/thread/4749/when-and-how-to-use-the-volatile-keyword-embedded-c-programming https://www.embeddedrelated.com/thread/4749/when-and-how-to-...
- mattnewport 10mo ago
  That's not really "fooling" the optimizer, that's kind of the point of volatile. The optimizer not making optimizations is the intended behaviour.
  - anonymousiam 10mo ago
    You're right, but the article failed to mention that there was a way around the optimizations.
- 1718627440 10mo ago
  Fooling for you is making someone not do X by telling them not to do X?
Panzerschrek 10mo ago
I can: https://godbolt.org/z/Kc8cTddd5 https://godbolt.org/z/Kc8cTddd5 Compilers still struggle to optimize non-trivial recursive functions, where obvious non-recursive approach is possible.
raluk 10mo ago
Years ago I wrote c++ library for stream compostion. Something like C++20 ranges. It turns out that as long as you compose everything with lambdas, compiled code is same as it would be with naive loops. Everything gets optimised. For example, you can write sum of numbers less than n as: count(uint64_t(0)) | take(n) | sum<uint64_t>(); Clang converted this into n*(n-1)/2.
amai 10mo ago
> This process of converting different code patterns into a standard, canonical form is what lets the compiler treat them all identically. Wouldn‘t it be nice if we could transform back from the canonical form into the most readable code? In the example that would convert all functions into x + y.

267 points by HeliumHydride 10mo ago

I always code with the mindset “the compiler is smarter than me.” No need to twist my logic around attempting to squeeze performance out of the processor - write something understandable to humans, let the computer do what computers do.

qsort 10mo ago
> I always code with the mindset “the compiler is smarter than me.” Like with people in general, it depends on what compiler/interpreter we're talking about, I'll freely grant that clang is smarter than me, but CPython for sure isn't. :) More generally, canonicalization goes very far, but no farther than language semantics allows. Not even the notorious "sufficiently smart compiler" with infinite time can figure out what you don't tell it.
- manbitesdog 10mo ago
  To add to this, the low-level constraints also make this assumption noisy, no matter how smart the compiler is. On the CPython case, if you do `dis.dis('DAY = 24 * 60 * 60)` you will see that constant folding nicely converts it to `LOAD_CONST 86400`. However, if you try `dis.dis('ATOMS_IN_THE_WORLD = 10*50')` you will get LOAD_CONST 10, LOAD_CONST 50, BINARY_OP **.
  - zbentley 10mo ago
    > However, if you try `dis.dis('ATOMS_IN_THE_WORLD = 10*50')` you will get LOAD_CONST 10, LOAD_CONST 50... I do not get that, I get LOAD_CONST 500. Tested on: Python 3.9.3 MacOS (Apple provided), 3.13.3 (uv provided) MacOS and Linux, and 3.14.0 (uv provided) MacOS and Linux.
    - manbitesdog 10mo ago
      Sorry, I meant 10**50; HN formatting removed one asterisk
      - zbentley 10mo ago
        Ah, gotcha. Yep! Not constant-calculated at all!
adrianN 10mo ago
This is decent advice in general, but it pays off to try and express your logic in a way that is machine friendly. That mostly means thinking carefully about how you organize the data you work with. Optimizers generally don't change data structures or memory layout but that can make orders of magnitude difference in the performance of your program. It is also often difficult to refactor later.
- lou1306 10mo ago
  To make a more specific example, if you malloc()/free() within a loop, it's unlikely that the compiler will fix that for you. However, moving those calls outside of the loop (plus maybe add some realloc()s within, only if needed) is probably going to perform better.
  - adrianN 10mo ago
    That is something that can be easily found and usually fixed with trivial profiling. I'm more talking about data locality instead of pointer chasing. Once you set up a pointer-chasing data infrastructure changing that means rewriting most of your application.
- amiga386 10mo ago
  I find the same too. I find gcc and clang can inline functions, but can't decide to break apart a struct used only among those inlined functions and make every struct member a local variable, and then decide that one or more of those local variables should be allocated as a register for the full lifetime of the function, rather than spill onto the local stack. So if you use a messy solution where something that should be a struct and operated on with functions, is actually just a pile of local variables within a single function, and you use macros operating on local variables instead of inlineable functions operating on structs, you get massively better performance. e.g. /* slower */ struct foo { uint32_t a,b,c,d,e,f,g,h; } uint32_t do_thing(struct foo *foo) { return foo->a ^ foo->b ^ foo->c ^ foo->d; } void blah() { struct foo x; for (...) { x.e = do_thing(&x) ^ x.f; ... } } /* faster */ #define DO_THING (a^b^c^d) void blah() { uint32_t a,b,c,d,e,f,g,h; for (...) { e = DO_THING ^ f; ... } }
tonyhart7 10mo ago
also not all software need optimization to the bone pareto principle like always, dont need the best but good enough not every company is google level anyway
ErroneousBosh 10mo ago
You say that, but I was able to reduce the code size of some avr8 stuff I was working on by removing a whole bunch of instructions that zero out registers and then shift a value around. I don't it to literally shift the top byte 24 bits to the right and zero out the upper 24 bits, I just need it to pass the value in the top 8 bits direct to the next operation. I agree that most people are not writing hand-tuned avr8 assembly. Most people aren't attempting to do DSP on 8-bit AVRs either.
IshKebab 10mo ago
The fact that compilers are smart isn't an excuse to not think about performance at all. They can't change your program architecture, algorithms, memory access patterns, etc. You can mostly not think about super low level integer manipulation stuff though.
jaccola 10mo ago
I would take it one step further, often trying to eke out performance gains with clever tricks can hurt performance by causing you to "miss the forest for the trees". I work with Cuda kernels a lot for computer vision. I am able to consistently and significantly improve on the performance of research code without any fancy tricks, just with good software engineering practices. By organising variables into structs, improving naming, using helper functions, etc... the previously impenetrable code becomes so much clearer and the obvious optimisations reveal themselves. Not to say there aren't certain tricks / patterns / gotchas / low level hardware realities to keep in mind, of course.
flohofwoe 10mo ago
> I always code with the mindset “the compiler is smarter than me.” ...I don't know... for instance the MSVC compiler creates this output for the last two 'non-trivial' functions with '/Ox': add w8,w1,w0 cmp w0,#0 cseleq w0,w1,w8 Even beginner assembly coders on their first day wouldn't write such bullshit :) A better mindset is "don't trust the compiler for code that's actually performance sensitive". You shouldn't validate each line of compiler output, but at least for the 'hot areas' in the code base that definitely pays off, because sometimes compilers do really weird shit for no good reason (often because of 'interference' between unrelated optimizer passes) - and often you don't need to dig deep to stumble over weird output like in the example above.
- sumtechguy 10mo ago
  I see the msvc arm compiler has not improved much in 20 years. The msvc arm was pretty odd when we used it in ~2003. We did not trust it at all. Think we had to get 4 or so compiler fixes out of MS for that project plus 3 or 4 library fixes. The x86 one was pretty solid. We were targeting 4 different CPU platforms at the same time so we could find things like that decently quickly. Most of the the time it was something we did that was weird. But even then we would find them. That one looks like maybe the optimizer back filled a nop slot?
wavemode 10mo ago
This is very often true when your data is sitting right there on the stack. Though when your data is behind pointers, it's very easy to write code that the compiler can no longer figure out how to optimize.
wat10000 10mo ago
I would modify this a bit. Someone with decent computer architecture knowledge, tools, and time can generally do better than the compiler. But you generally won't, because you have a lot of other things to think about. So I'd state this as, "the compiler is more diligent and consistent than me." It's not so much that it can spot a for loop that's equivalent to a single add, but that it will spot it just about every time, so you don't have to worry about it.
stonemetal12 10mo ago
I go with "You are responsible for the algorithms, it is responsible for the code micro optimizations". The compiler can't optimize you out of an SQL N+1 situation, that is on me to avoid, but it is better than me at loop unrolling.
mamcx 10mo ago
> “the compiler is smarter than me.” This is true, but it also means "the compiler IS made for someone median smart, that now knows the machine". It works great for basic, simple, common code, and for code that is made with care for data structures. A total mess of code is another story. P.D: is similar to the query optimizers, that neither can outrun a terrible made schema and queries
moregrist 10mo ago
There are optimizations that a compiler can perform; usually these are code transformations. Modern optimizing compilers usually get these right. The optimizations that tend to have the most impact involve changes to the algorithm or data layout. Most compilers won’t do things like add a hash table to make a lookup O(1) or rearrange an array of structures to be a structure of arrays for better data locality. Coding with an eye for these optimizations is still a very good use of your time.
kragen 10mo ago
> I always code with the mindset “the compiler is smarter than me.” That mindset will last until the first or second time you walk through the compiler's assembly-language output. GCC and LLVM can find some amazing optimizations, but they also consistently miss very obvious optimization opportunities, often even on utterly trivial code. That isn't to say that it's worthwhile to hand-optimize all your code. But the compiler is very much not smarter than you, and if you do need to squeeze performance out of the processor, you can do a lot better than the compiler does. A good first step is to look at the stupid shit the compiler has spat out and massage your source code until the shit stinks less.

barishnamazov 10mo ago

Sometimes you can fool the compiler :-) See "Example 2: Tricking the compiler" in my blog post about O3 sometimes being slower than O2: https://barish.me/blog/cpp-o3-slower/ https://barish.me/blog/cpp-o3-slower/

317070 10mo ago

"The compiler" and "The optimizer" are doing a lot of the heavy lifting here in the argument. I definitely know compilers and optimizers which are not that great. Then again, they are not turning C++ code into ARM instructions. You absolutely can fool a lot of compilers out there! And I am not only looking at you, NVCC.

Almondsetat 10mo ago
But the point should be to follow the optimization cycle: develop, benchmark, evaluate, profile, analyze, optimize. Writing performant code is no joke and very often destroys readability and introduces subtle bugs, so before trying to oursmart the compiler, evaluate if what it produces is good enough already

amelius 10mo ago

One undesirable property of optimizers is that in theory one day they produce good code and the next day they don't.

titzer 10mo ago
These situations are known as "performance cliffs" and they are particularly pernicious in optimizing dynamic languages like JavaScript, where runtime optimization happens that depends not just on the program's shape, but its past behavior.

sureglymop 10mo ago

With this one I instead wondered: If there are 4 functions doing exactly the same thing, couldn't the compiler also only generate the code for one of them? E.g. if in `main` you called two different add functions, couldn't it optimize one of them away completely? It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? Why doesn't it do that?

cyco130 10mo ago
It would but it's harder to trigger. Here, it's not safe because they're public functions and the standard would require `add_v1 != add_v2` (I think). If you declare them as static, it eliminates the functions and the calls completely: https://aoco.compiler-explorer.com/z/soPqe7eYx https://aoco.compiler-explorer.com/z/soPqe7eYx I'm sure it could also perform definition merging like you suggest but I can't think of a way of triggering it at the moment without also triggering their complete elision.
moefh 10mo ago
> It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? It can't do that because the program might load a dynamic library that depends on the function (it's perfectly OK for a `.so` to depend on a function from the main executable, for example). That's one of the reasons why a very cheap optimization is to always use `static` for functions when you can. You're telling the compiler that the function doesn't need to be visible outside the current compilation unit, so the compiler is free to even inline it completely and never produce an actual callable function, if appropriate.
- bruce343434 10mo ago
  Sadly most C++ projects are organized in a way that hampers static functions. To achieve incremental builds, stuff is split into separate source files that are compiled and optimized separately, and only at the final step linked, which requires symbols of course. I get it though, because carefully structuring your #includes to get a single translation unit is messy, and compile times get too long.

daft_pink 10mo ago

Is this an argument for compiled code?

0xTJ 10mo ago
It's not really an argument for anything, it's just showing off how cool compilers are!

mkornaukhov 10mo ago

Better tell me how to make the compiler not fool me!

Scene_Cast2 10mo ago

This post assumes C/C++ style business logic code. Anything HPC will benefit from thinking about how things map onto hardware (or, in case of SQL, onto data structures). I think way too few people use profilers. If your code is slow, profiling is the first tool you should reach for. Unfortunately, the state of profiling tools outside of NSight and Visual Studio (non-Code) is pretty disappointing.

layer8 10mo ago
I don’t disagree, but profiling also won’t help you with death by a thousand indirections.
- lmm 10mo ago
  Sure, but that's mostly a myth.
  - 1718627440 10mo ago
    So how do you see in a profiler, that everything is 1.2x slower than it could be?
    - lmm 10mo ago
      No-one's getting out of bed for 1.2x.
      - 1718627440 10mo ago
        Depends. If you have a real-time system, that might very well will be what you chase after. Also why not make your program a bit faster when it is no work, by starting it the right way upfront. I mean I wouldn't rewrite a program for this, but when I program some new part and I can avoid an indirection, why not do it? Less complexity, less (failure) state, better performance.
        10mo ago

asah 10mo ago

I want an AI optimization helper that recognizes patterns that could-almost be optimized if I gave it a little help, e.g. hints about usage, type, etc.

Jaxan 10mo ago
Why does it have to be AI?

stabbles 10mo ago

For people who enjoy these blogs, you would definitely like the Julia REPL as well. I used to play with this a lot to discover compiler things. For example: $ julia julia> function f(n) total = 0 for x in 1:n total += x end return total end julia> @code_native f(10) ... sub x9, x0, #2 mul x10, x8, x9 umulh x8, x8, x9 extr x8, x8, x10, #1 add x8, x8, x0, lsl #1 sub x0, x8, #1 ret ... it shows this with nice colors right in the REPL. In the example above, you see that LLVM figured out the arithmetic series and replaced the loop with a simple multiplication.

lifthrasiir 10mo ago
This and add_v3 in the OP fall into the general class of Scalar Evolution optimizations (SCEV). LLVM for example is able to handle almost all Brainfuck loops in practice---add_v3 indeed corresponds to a Brainfuck loop `[->+<]`---, and its SCEV implementation is truly massive: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/ScalarEvolution.cpp https://github.com/llvm/llvm-project/blob/main/llvm/lib/Anal...
Someone 10mo ago
LLVM can do more complex sums, too. See https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo...
eigenspace 10mo ago
Another nice thing in julia is that if you dont want the optimizer to delete something, you can just ask it nicely :) julia> function f(n) total = 0 for x in 1:n total += Base.donotdelete(x) end return total end will keep the loop

matja 10mo ago

You can fool the optimizer, but you have to work harder to do so: unsigned add(unsigned x, unsigned y) { unsigned a, b; do { a = x & y; b = x ^ y; x = a << 1; y = b; } while (a); return b; } becomes (with armv8-a clang 21.1.0 -O3) : add(unsigned int, unsigned int): .LBB0_1: ands w8, w0, w1 eor w1, w0, w1 lsl w0, w8, #1 b.ne .LBB0_1 mov w0, w1 ret

thaumasiotes 10mo ago
Since I had to think about it: unsigned add(unsigned x, unsigned y) { unsigned a, b; do { a = x & y; /* every position where addition will generate a carry */ b = x ^ y; /* the addition, with no carries */ x = a << 1; /* the carries */ y = b; /* if there were any carries, repeat the loop */ } while (a); return b; } It's easy to show that this algorithm is correct in the sense that, when b is returned, it must be equal to x+y. x+y summing to a constant is a loop invariant, and at termination x is 0 and y is b. It's a little more difficult to see that the loop will necessarily terminate. New a values come from a bitwise & of x and y. New x values come from a left shift of a. This means that, if x ends in some number of zeroes, the next value of a will also end in at least that many zeroes, and the next value of x will end in an additional zero (because of the left shift). Eventually a will end in as many zeroes as there are bits in a, and the loop will terminate.
- gfaster 10mo ago
  In C, I'm pretty confident the loop is defined by the standard to terminate. Also I did take the excuse to plug it (the optimized llvm ir) into Alive: https://alive2.llvm.org/ce/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:14,j:1,lang:llvm,selection:(endColumn:8,endLineNumber:1,positionColumn:8,positionLineNumber:1,selectionStartColumn:8,selectionStartLineNumber:1,startColumn:8,startLineNumber:1),source:'define+i32+@src(i32+noundef+%25x,+i32+noundef+%25y)+%7B%0Aentry:%0A++br+label+%25do.body%0A%0Ado.body:%0A++%25y.addr.0+%3D+phi+i32+%5B+%25y,+%25entry+%5D,+%5B+%25xor,+%25do.body+%5D%0A++%25x.addr.0+%3D+phi+i32+%5B+%25x,+%25entry+%5D,+%5B+%25shl,+%25do.body+%5D%0A++%25and+%3D+and+i32+%25x.addr.0,+%25y.addr.0%0A++%25xor+%3D+xor+i32+%25x.addr.0,+%25y.addr.0%0A++%25shl+%3D+shl+i32+%25and,+1%0A++%25tobool.not+%3D+icmp+eq+i32+%25and,+0%0A++br+i1+%25tobool.not,+label+%25do.end,+label+%25do.body%0A%0Ado.end:%0A++ret+i32+%25xor%0A%7D%0A%0Adefine+i32+@tgt(i32+noundef+%25x,+i32+noundef+%25y)+%7B%0A++++%25add+%3D+add+i32+%25x,+%25y%0A++++ret+i32+%25add%0A%7D'),l:'5',n:'0',o:'LLVM+IR+source+%231',t:'0')),k:49.32378679395386,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:alive,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'1',trim:'1'),fontScale:14,j:1,lang:llvm,libs:!(),options:'',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'alive-tv+(Editor+%231,+Compiler+%231)+LLVM+IR',t:'0')),k:50.67621320604614,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://alive2.llvm.org/ce/#g:!((g:!((g:!((h:codeEditor,i:(f...

raverbashing 10mo ago

I'm curious what is the theoreme-proving magic behind add_v4 and if this is prior LLVM ir

Joker_vD 10mo ago

Wait, why does GAS use Intel syntax for ARM instead of AT&T? Or something that looks very much like it: the destination is the first operand, not the last, and there is no "%" prefix for the register names?

Karliss 10mo ago
That's not Intel syntax that's more or less ARM assembly syntax as used by ARM documentation. Intel vs AT&T discussion is primarily relevant only for x86 and x86_64 assembly. If you look at GAS manual https://ftp.gnu.org/old-gnu/Manuals/gas-2.9.1/html_chapter/as_toc.html https://ftp.gnu.org/old-gnu/Manuals/gas-2.9.1/html_chapter/a... almost every other architecture has architecture specific syntax notes, in many cases for something as trivial comments. If they couldn't even decide on single symbols for comments, there is no hope for everything else. ARM isn't the only architecture where GAS uses similar syntax as developers of corresponding CPU arch. They are not doing the same for X86 due to historical choices inherited from Unix software ecosystem and thus AT&T. If you play around on Godbolt with compilers for different architectures it seems like x86 and use AT&T syntax is the exception, there are a few other which use similar syntax but it's a minority. Why not use same syntax for all architectures? I don't really know all the historical reasoning but I have a few guesses and each arch probably has it's own historic baggage. Being consistent with manufacturer docs and rest of ecosystem has the obvious benefits for the ones who need to read it. Assembly is architecture specific by definition so being consistent across different architectures has little value. GAS is consistent with GCC output. Did GCC added support for some architectures early with the with help of manufacturers assembler and only later in GAS? A lot of custom syntax quirks which don't easily fit into Intel/AT&T model and are related to various addressing modes used by different architectures. For example ARM has register postincrement/preincrement and the 0 cost shifts, arm doesn't have the subregister acess like x86 (RAX/EAX/AX/AH/AL) and non word access is more or less limited to load/store instructions unlike x86 where it can show up in more places. You would need to invent quite a few extensions for AT&T syntax for it to be used by all the non x86 architectures, or you could just use the syntax made by developer of architecture.
- Joker_vD 10mo ago

torginus 10mo ago

Awesome blog post - thanks to this I found out that you can view what the LLVM optimizer pipeline does, and which pass is actually responsible for doing which instruction. It's super cool to see this in practice, and for me it helps putting more trust in the compiler that it does the right thing, rather than me trying to micro-optimize my code and peppering inline qualifiers everywhere.

dlenski 10mo ago

Today I learned that Matt Godbolt is British!

jmcomets 10mo ago

Obvious caveat: pushing this a bit further it can quickly fallback to the default case. The optimizer is a superpower but you still need to try to write efficient code. unsigned add_v5(unsigned x, unsigned y) { if (x == y) return 2 * x; return x + y; } Results in: add_v5(unsigned int, unsigned int): lsl w8, w0, #1 add w9, w1, w0 cmp w0, w1 csel w0, w8, w9, eq ret (armv8-a clang 21.1.0 with O3) If compiler folks can chime in, I'm curious why incrementing in a loop can be unrolled and inspected to optimize to an addition, but doubling the number when both operands are equal can't?

Someone 10mo ago
> I'm curious why incrementing in a loop can be unrolled and inspected to optimize to an addition, but doubling the number when both operands are equal can’t? I expect because the former helps more in optimising real-world code than the latter. It’s not worth the LLVM developer's time to make the compiler better for programs that it won’t see in practice. It’s not as if the compiler did nothing with that code, though. It replaced the multiplication by a left shift and removed the branch.
DullPointer 10mo ago
I’m not a compiler expert, an assembly expert or an ARM expert, so this may be wildly wrong, but this looks optimized to me. The trick is that it’s doing both the add and the left shift in parallel then selecting which to use based on a compare of the two values with csel. (To see this, rather than reading the code sequentially, think of every instruction as being issued at the same time until you hit an instruction that needs a destination register from an earlier instruction) The add is stored in W9 but only read if the two arguments are unequal. If the compare succeeds and the lsl retires before the add, the add is never read, so nothing stalls waiting for it and the answer can be returned while the add is still in flight. The result of the add would then be quietly discarded assuming it ever started (maybe there’s some magic where it doesn’t even happen at all?). It’s not clear to me that this is power efficient, or that on many real cpus there’s a latency difference to exploit between add and lsl, so it may not be faster than just unconditionally doing the addition. That said, it is definitely faster than the code as it was written which if translated to asm verbatim stalls on the compare before executing either the add or the left shift.

anon-3988 10mo ago

What I am curious about is, is the compiler smart enough to be lazy with computation and or variables? For example consider: let a = expr let b = expr2 if (a || b) { return true; } is the compiler allowed to lazily compute this if it is indeed faster to do that way? Or declaring a bunch of variables that may or may not be used in all of the branches. Is the compiler smart enough to only compute them whenever it is necessary? AFAIK this is now allowed in C-like languages. Things have to materialize. Another one is, I like to do memcpy every single time eventhough it might not even be used or overwritten by other memcpys. Is the compiler smart enough to not perform those and reorder my program so that only the last relevant memcpy is performed? A lot of times, my code becomes ugly because I don't trust that it does any of this. I would like t write code in consistent and simple ways but I need compilers to be much smarter than it is today. A bad example recently is something like const S * s =; let a = constant; let b = constant; let c = constant; let d = constant; let e = constant; let f = constant; let g = constant; let h = constant; let i = constant; let j = constant; let k = constant; let l = constant; if (s->a == a && s->b == b /* etc */ ) { return true; } It did not turn all of this into a SIMD mask or something like that.

jcranmer 10mo ago
> Is the compiler smart enough to only compute them whenever it is necessary? This is known as "code sinking," and most optimizers are capable of doing this. Except keep in mind that a) the profitability of doing so is not always clear [1] and b) the compiler is a lot more fastidious about corner-case behavior than you are, so it might conclude that it's not in fact safe to sink the operation when you think it is safe to do so. [1] If the operation to sink is x = y + z, you now may need to keep the values of y and z around longer to compute the addition, increasing register pressure and potentially hurting performance as a result.
Denvercoder9 10mo ago
> It did not turn all of this into a SIMD mask or something like that. Did you try using bitwise and (&), or a local for the struct? The short-circuiting behaviour of the logical means that if `s->a != a`, `s->b` must not be dereferenced, so the compiler cannot turn this into a SIMD mask operation, because it behaves differently. Generally compilers are pretty smart these days, and I find that more often than not if they miss an "obvious" optimization it's because there's a cornercase where it behaves differently from the code I wrote.

Scubabear68 10mo ago

I liked the idea behind this post, but really the author fairly widely missed the mark in my opinion. The extent to which you can "fool the optimizer" is highly dependent on the language and the code you're talking about. Python is a great example of a language that is devilishly hard to optimize for precisely because of the language semantics. C and C++ are entirely different examples with entirely different optimization issues, usually which have to do with pointers and references and what the compiler is allowed to infer. The point? Don't just assume your compiler will magically make all your performance issues go away and produce optimal code. Maybe it will, maybe it won't. As always, the main performance lessons should always be "1) Don't prematurely optimize", and "2) If you see perf issues, run profilers to try to definitively nail where the perf issue is".

gpderetta 10mo ago
I think the author is strictly talking about C and C++. Python is famously pessimal in all possible ways.
- Scubabear68 10mo ago
  Digging around, OK that makes sense. But even in the context of C and C++, there are often more ways the compiler can't help you than ways it can. The most common are on function calls involving array operations and pointers, but a lot of it has to do with the C/C++ header and linker setup as well. C and C++ authors should not blithely assume the compiler is doing an awesome job, and in my experience, they don't.
  - gpderetta 10mo ago
    > C and C++ authors should not blithely assume the compiler is doing an awesome job Agree. And I'm sure the author agrees as well. That's why compiler-explorer exists in the first place.

gpderetta 10mo ago

Interesting, even this can't fool the optimizer (tried with a recent gcc and clang): unsigned add(unsigned x, unsigned y) { std::vector vx {x}; std::vector vy {y}; auto res = vx[0]+vy[0]; return res; }

senfiaj 10mo ago

I wonder if compilers do multiple passes on the intermediate code in order to optimize / simplify it. For example, during each pass the optimizer searches some known harcoded patterns and replaces them with something else and repeats until no possible improvement is found. Also optimizers have a limit, they can't reason as abstractly as humans, for example: bool is_divisible_by_6(int x) { return x % 2 == 0 && x % 3 == 0; } bool is_divisible_by_6_optimal(int x) { return x % 6 == 0; } I tried with both gcc and clang, the asm code for is_divisible_by_6 is still less optimal. So no, there are plenty of easy ways to fool the optimizer by obfuscation. The morale is that you still have to optimize algorithms (O notation) and math operations / expressions.

jakobnissen 10mo ago
They do, and the order of the passes matter. Sometimes, optimizations are missed because they require a certain order of passes that is different from the one your compiler uses. On higher optimization levels, many passes occur multiple times. However, as far as I know, compilers don't repeatedly run passes until they've reached an optimum. Instead, they run a fixed series of passes. I don't know why, maybe someone can chime in.
- titzer 10mo ago
  It's a long-standing problem in compilers, often referred to as the "phase ordering problem". In general, forward dataflow optimizations can be combined if they are monotonic (meaning, never make the code worse, or at least, never undo a previous step. It's possible to run forward dataflow problems together repeatedly to a fixpoint. In TurboFan a general graph reduction algorithm is [1] instantiated with a number of reducers, and then a fixpoint is run. The technique of trying to combine multiple passes has been tried a number of times. What doesn't seem so obvious is how to run optimizations that are not traditional forward dataflow problems or are indeed backward dataflow problems (like DCE) together with other transformations. Generally compilers get tuned by running them on lots of different kinds of code, often benchmarks, and then tinkering with the order of passes and other heuristics like loop unroll factors, thresholds for inlining, etc, and seeing what works best. [1]was? TurboFan seems to have splintered into a number of pieces being reused in different ways these days

derefr 10mo ago

Even better / potentially more surprising: unsigned mult(unsigned x, unsigned y) { unsigned y0 = y; while (x--) y = add_v1(y, y0); return y; } optimizes to: mult(unsigned int, unsigned int): madd w0, w1, w0, w1 ret (and this produces the same result when substituting any of the `add_vN`s from TFA)

deleted 10mo ago

[deleted]

Findecanor 10mo ago

I'm wondering how the compiler optimised add_v3() and add_v4() though. Was it through "idiom detection", i.e. by recognising those specific patterns, or did the compiler deduce the answers them through some more involved analysis?

fooyc 10mo ago
add_v3() is the result of induction variable simplification: https://llvm.org/doxygen/IndVarSimplify_8cpp_source.html https://llvm.org/doxygen/IndVarSimplify_8cpp_source.html
j2kun 10mo ago
Scalar Evolution is one way loops can be simplified

abainbridge 10mo ago

The examples are fun, but rather than yet another article saying how amazing optimizing compilers are (they are, I already know), I'd probably benefit more from an article explaining when obvious optimizations are missed and what to do about it. Some boring examples I've just thought of... eg 1: int bar(int num) { return num / 2; } Doesn't get optimized to a single shift right, because the that won't work if num is negative. In this case we can change the ints to unsigneds to tell the compiler we know the number isn't negative. But it isn't always easy to express to the compiler everything you know about your data and use case. There is an art in knowing what kinds of things you need to tell the compiler in order to unlock optimizations. eg 2: int foo(void) { return strlen("hello"); } We all know that strlen will return 5, but some compilers don't: https://godbolt.org/z/M7x5qraE6 https://godbolt.org/z/M7x5qraE6 eg 3: int foo(char const *s) { if (strlen(s) < 3) return 0; if (strcmp(s, "hello") == 0) return 1; return 0; } This function returns 1 if s is "hello". 0 otherwise. I've added a pointless strlen(). It seems like no compiler is clever enough to remove it. https://godbolt.org/z/Koj65eo5K https://godbolt.org/z/Koj65eo5K. I can think of many reasons the compiler isn't able to spot this.

commandlinefan 10mo ago
> won't work if num is negative I remember reading (although I can't find it now) a great analysis of all the optimizations that Javascript compilers _can't_ do because of the existence of the "eval" instruction.
- astrange 10mo ago
  A JIT can do any optimization it wants, as long as it can deoptimize if it turns out it was wrong.
  - adrianN 10mo ago
    You also want to prove that the „optimization“ doesn’t make things slower.
    - 10mo ago

CodeArtisan 10mo ago

Recursive Popcount: unsigned int popcount(unsigned int n) { return (n &= n - 1u) ? (1u + popcount(n)) : 0u; } Clang 21.1 x64: popcount: mov eax, -1 .LBB0_1: lea ecx, [rdi - 1] inc eax and ecx, edi mov edi, ecx jne .LBB0_1 ret GCC 15.2: popcount: blsr edi, edi popcnt eax, edi ret Both compiled with -O3 -march=znver5

pbsd 10mo ago
Because the function is not quite correct. It should be return n ? (1u + popcount(n & n - 1u)) : 0u; which both Clang and GCC promptly optimize to a single popcnt.
- 1718627440 10mo ago
  There should be testsuites, which are based on testing which compilation passes the compiler chose.

norir 10mo ago

For me, compiler optimization is a mixed bag. On the one hand, they can facilitate the generation of higher performance runtime artifacts, but it comes at significant cost, often I believe exceeding the value they provide. They push programs in the direction of complexity and inscrutability. They make it harder to know what a function _actually_ does, and some even have the ability to break your code. In the OP examples, instead of optimization, what I would prefer is a separate analysis tool that reports what optimizations are possible and a compiler that makes it easy to write both high level and machine code as necessary. Now instead of the compiler opaquely rewriting your code for you, it helps guide you into writing optimal code at the source level. This, for me, leads to a better equilibrium where you are able to express your intent at a high level and then, as needed, you can perform lower level optimizations in a transparent and deterministic way. For me, the big value of existing optimizing compilers is that I can use them to figure out what instructions might be optimal for my use case and then I can directly write those instructions where the highest performance is needed. But I do not need to subject myself to the slow compilation times (which compounds as the compiler repeatedly reoptimizes the same function thousands of times during development -- a cost that is repeated with every single compilation of the file) nor the possibility that the optimizer breaks my code in an opaque way that I won't notice until something bad and inscrutable happens at runtime.

msarnoff 10mo ago

I was very surprised that GCC could optimize NEON SIMD intrinsics. After spending hours trying to optimize my vector code, trying to get the spacing between register dependencies right to reduce stalls, breaking long reduction operations into intermediate results, messing with LLVM-MCA, etc., I realized that I just couldn’t beat the compiler. It was doing its best to allocate registers and reorder instructions to keep the pipeline filled. I don’t think it always did the best job and saw a bunch of register spills I thought were unnecessary, but I couldn’t justify the time and effort to do it in assembly…

WalterBright 10mo ago

There are general optimizations, based on DFA (Data Flow Analysis). These recognize things like loops, loop invariants, dead code, copy propagation, constant propagation, common subexpressions, etc. Then, there are is a (very long) list of checks for specific patterns and replacing them with shorter sequences of code, things like recognizing the pattern of bswap and replacing it with a bswap instruction. There's no end to adding patterns to check for.

DannyBee 10mo ago
This is true but there is actually an end ;) There are limits on provable equivalence in the first place. things like equality saturation also try and do a better job of formalizing equivalence based rewrites.

bgbntty2 10mo ago

I'm not well-versed in compilers, so it was a bit surprising to see how it optimizes all the add_vX functions. What I most enjoyed, though, was how the guy in the video (linked at the bottom of the article) was typing - a mistake on every few characters. Backspace was likely his most-used key. I found it encouraging, somehow. I know typing speed or correctness isn't really important for coders, but I always felt like I'm behind others with regards to typing, even though when I really concentrate, I do good on those online typing tests. Even when writing this comment, I made like 30 mistakes. Probably an useless comment, but it may give some people hope or validation if they feel like they not great typists.

anonymousiam 10mo ago

Sometimes you can fool the (C) optimizer by using the 'volatile' keyword in front of a variable in code that would otherwise be optimized out. https://www.embeddedrelated.com/thread/4749/when-and-how-to-use-the-volatile-keyword-embedded-c-programming https://www.embeddedrelated.com/thread/4749/when-and-how-to-...

mattnewport 10mo ago
That's not really "fooling" the optimizer, that's kind of the point of volatile. The optimizer not making optimizations is the intended behaviour.
- anonymousiam 10mo ago
  You're right, but the article failed to mention that there was a way around the optimizations.
1718627440 10mo ago
Fooling for you is making someone not do X by telling them not to do X?

Panzerschrek 10mo ago

I can: https://godbolt.org/z/Kc8cTddd5 https://godbolt.org/z/Kc8cTddd5 Compilers still struggle to optimize non-trivial recursive functions, where obvious non-recursive approach is possible.

raluk 10mo ago

Years ago I wrote c++ library for stream compostion. Something like C++20 ranges. It turns out that as long as you compose everything with lambdas, compiled code is same as it would be with naive loops. Everything gets optimised. For example, you can write sum of numbers less than n as: count(uint64_t(0)) | take(n) | sum<uint64_t>(); Clang converted this into n*(n-1)/2.

amai 10mo ago

> This process of converting different code patterns into a standard, canonical form is what lets the compiler treat them all identically. Wouldn‘t it be nice if we could transform back from the canonical form into the most readable code? In the example that would convert all functions into x + y.