7 ms·
Can you trust a compiler to optimize your code?
- anonymoushn 3y agoThis is good advice. Still, a lot of problems seem to remain firmly in the "write it with intrinsics" region even if you do your best to help the compiler out. For any operation that involves filtering a list, the compiler will not generate the lookup table of shuffles that is used in the fastest solutions (maybe the story is different on AVX-512 where there are dedicated filtering instructions or on NEON where movemask costs more because there isn't such an instruction). For parsing and formatting strings, the compiler usually will not take branchy code and decide to compute both branches and vectorize it even if it is guaranteed chunks of the appropriate size. Some concrete examples of the how simple these problems can be while remaining out of reach are "Given a mutable list of u32, remove all multiples of 3" and "Given a list of newline-separated UUIDs and an equally large list of mutable u128, parse the hexadecimal bytes of each UUID into the corresponding u128".
- sakras 3y agoThis is overall very solid. However you have to be careful to not go overboard with this line of reasoning. I've seen people try to explain away inefficient code by inventing a chain of optimizations that the compiler could conceivably do. If this chain is too long, it probably won't happen! The most common pitfall I've seen is relying on inlining too much (specifically a C++ template monster). As far as I can tell, compilers have a fixed number of inline passes, and don't keep inlining until they hit a fixed point.
- Pannoniae 3y agoMany absolutely fall into the trap of "don't optimise because premature optimisation etc., compiler is smarter than you, and library authors are definitely smarter than you". The result of that approach is that in 2023, our desktop is worse in usability and performance than what is was in 1998. With SIMD, you always have to check what the compiler generates, you can't just write something and expect it to be vectorised. Similar to other optimisations such as de-virtualisation - it might happen or it might not. If it doesn't, you have to do it yourself by hand, or somehow convince the compiler to do it.
- saagarjha 3y agoMachines aren’t slow because people don’t use SIMD.
- Pannoniae 3y agoOf course, that was a jab at the lack of optimisation in general, not SIMD specifically.
- galkk 3y agoYou don’t even get information/ diagnostics about copy elision / return value optimization in c++, if that happened or not in particular place in the code. Only by looking into assembler :(
- leni536 3y agoNote that RVO is mandatory when returning a prvalue since C++17. IME NRVO happens pretty reliably in the simple case, even on low optimisation levels. There is a proposal for mandatory NRVO in some cases. It would be pretty great, but the proposal didn't move forward for quite a while.
- mlazos 3y agoNah that’s not lack of premature optimization, that’s just electron apps and everyone learning JavaScript.
- wredue 3y agoJavaScript can be quite “fast” if you’re not copying an array 30 times to get one number out of it. Yeah. It’s still slow, as it were. But the JavaScript community also very much aligns with various functional programming ideals like immutability, which takes “kind of slow” to “immensely slow”.
- DarkNova6 3y ago> The result of that approach is that in 2023, our desktop is worse in usability and performance than what is was in 1998. No. This is undoubtedly because every UI nowadays is using JavaScript. This is problem is way waaaaay larger than any premature optimization considerations.
- declanhaigh 3y agoKen Thompson once made a similar point about compilers and trust but in terms of security: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
- mrweasel 3y agoAdding to the security part, there are also situations where compilers will optimize something, only to introduce security issues, hence the need to functions such as explicit_bzero (https://man.openbsd.org/explicit_bzero https://man.openbsd.org/explicit_bzero).
- pests 3y agoHalf of Linus rants are just about compiler bugs .
- magicalhippo 3y ago> Compilers are tools. They can reliably vectorize code if it is written in an amenable-to-vectorization form. This goes for regular scalar code as well, it's just less obvious in mature compilers with ton of work put into them. I've long since given up handwriting scalar assembly code for speed. Instead I've studied the output of the compilers I use, and through iteration learned how to write optimization-friendly code. If I have a hot spot that matters in my code I check just to be sure. Sometimes the most innocent looking changes can cause issues.
- PhilipRoman 3y agoIn my experience, one of the biggest benefits that isn't too hard to implement is letting the compiler write/read more than it strictly needs to. For example, pad your arrays to a multiple of 8, 16, etc. and where possible, run loops on the entire array including the padding. IIRC both GCC and Clang are smart enough to understand loops whose limit is rounded to the nearest multiple of 2^n via bitwise operators and they won't have to emit ugly loop tails which bloat code size. This is a bit off topic, but I remember discovering a missed optimization in GCC this way: I wanted to signal to the compiler that it is allowed to read a particular pointer earlier than C semantics would allow and did something along the lines of (void)*p; Well it turns out that dead-end reads are removed pretty early in the optimization pipeline, so GCC removed the read and then refused to touch the pointer. Replacing it with some __builtin, I was able to confirm that was indeed the case.
- Cthulhu_ 3y agoThat sounds like an optimization the compiler could / should do for me, if I enable the option. Same with things like struct ordering and / or padding, although that can affect the functionality in subtle ways, because the language gives you too much power at that low level.
- gpderetta 3y agoIt sounds like that, but turns out that those are extremely hard optimizations to do as they require whole program analysis.
- MereInterest 3y agoAlso, because they involve trade-offs. Ideally, a compiler optimization would result in code that is better in every measurable aspect. For example, dead code elimination results in a smaller binary, fewer branch points, and fewer runtime computations. Array padding, on the other hand, requires a larger memory footprint to accommodate the padding. If an optimization is only beneficial in some cases, compiler authors are rightfully wary of enabling it in all cases.
- tialaramex 3y ago> A higher level language might choose to always represent functions with function pointers This is a dig at C++ in case anybody didn't notice. In C++ if I write three predicates X, Y and Z which decide if a > b, b < a and a == b respectively, for two ints named a and b -- their types are identical, X, Y and Z have the same type, the type of any function which takes two integers and return a boolean even though of course these are different functions. Imagine if your other types worked like this. Oh IPv4Address and OldMacFileType both consist of four bytes, so now they're interchangeable and your code which takes an IPv4Address also works with a OldMacFileType. Very sensible. As with many things in C++ this is inherited from C where it wasn't considered a bad problem because nobody has a decent optimising compiler on the PDP-11 anyway.
- hfkwer 3y agoI'm not sure I understand the criticism. You have three functions of type (int, int) -> bool. Where the type system accepts one, it accepts the others. I fail to see the issue here? How is the type system supposed to distinguish them? It's up to you, the developer, to do it. If you have two ints x and y, and you mess up and pass y to a function where you wanted to write x, the compiler is never going to catch it for you either.
- tialaramex 3y agoI have three different functions, and what you wrote is not their type, that's their signature. Actually they are really only two different functions - a < b and b > a are the same thing for this integer type - but whether or not the optimiser knows that will not always be obvious. Yes, the C++ type system doesn't express this, that's the defect (well, it's the consequence here of a larger defect). Once they have different types there are two different interesting things we can do, we could just coerce them into a function pointer type based on the signature which is what you've seen in C++ and seem to assume is just naturally the only possibility. Or, we can use parametric polymorphism.
- hfkwer 3y agoWhat do you mean by the "type" of a function? It doesn't sound like you're using any kind of standard definition for the word.
- andrewaylett 3y agoOne thing I really want in my compilers is a way to express expectations: if I expect an auto-vectorisation, or a block of unreachable code, I should be able to tell the compiler explicitly! For dead code, this is different from assertions, or Rust's `unreachable!` macro, in that they tell the compiler to trust me, and crash at runtime if I'm wrong. I want the compiler to check my logic and fail to compile if it can't prove me right. If I write a switch block and I know that only a limited subset of values can possibly happen, I still have to provide code for all possible values. But I expect that code to be subject to dead code elimination, and I'd quite like to be sure that actually happens. I'm not aware of any automation around checking that code I expect to compile to SIMD actually winds up doing that.
- The_Colonel 3y agoWhat does the compiler do with that expectation? If the code can't be vectorized for target architecture, does it emi a warning?
- andrewaylett 3y agoI'd quite like it to emit an error and fail. If some target architectures won't vectorise the code, I can always add the expectation conditionally. I'm not so much trying to catch deliberate changes, where a warning might make sense as I'd be (maybe) looking for it, but changes that break autovectorisation as a side effect -- maybe something can't be inlined any more, maybe a new compiler version introduces a new optimisation that causes a cascade of tiny changes. I'd hope that we would catch the difference in performance, but it's easier to notice a compilation failure than a performance drop.
- 10000truths 3y agoThe problem with autovectorization is that there's no good tooling for it. icc at least has #pragma simd to force vectorization, but gcc and clang don't. And there's no way to annotate a loop to say "throw a compile error if this loop fails to autovectorize". You either pray that someone else doesn't cause a silent 4x regression by adding a loop-carried dependency, or you perform some brittle hackery trying to read the output of -fopt-info-vec-missed flag and killing the build when you see a file name + line number that corresponds to a hot loop. At that point, it just becomes easier to use SIMD intrinsics. You're still deferring to the compiler for the instruction scheduling and register allocation, but you no longer have to worry about whether the SIMD is being emitted at all.
- bick_nyers 3y agoOr you can have some automated benchmarks as part of your CI pipeline that will compare performance numbers to previous builds to know if there is a regression that ends up mattering. An added benefit is that you can use it to do PGO and potentially eek out some more performance: https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization
- 10000truths 3y agoAutomated benchmarks are good practice, but they're not a substitute for compile-time feedback. I would much prefer the immediate results from a compiler error, over the minutes-long wait for a traditional CI pipeline to finish.
- voidbert 3y agoIt shouldn't be too hard to write a script that objdumps a list of functions and checks if SIMD instructions are used. Strap it to your build system / CI pipeline and you're good to go. Of course, it'd be better if compilers could do that natively.
- rowls66 3y agoReally surpising to me that compilers don't support a feature like this. Anybody know why?
- jeffbee 3y agoHow does this `chunks_exact` business handle alignment?
- secondcoming 3y ago> ‘&’ doesn’t short circuit Is this always true? I’ve experimented with this optimisation before but backed away from using it in production because it felt iffy to do. The codegen was far better though
- Izkata 3y agoSingle & (and single | for "or") are bitwise and/or, not logical and/or. They have to evaluate both sides to be able to return a result. For example: 1100 & 0101 -> 0100 1100 | 0101 -> 1101
- bick_nyers 3y agoThis comment is tangential at best, but coming from someone who has never written a compiler (i.e. I'm a Dunning-Kruger peak), I'm curious to know if ML approaches could drive more optimizations. As I understand it, compiler optimizations are NP-hard so they use heuristics and clever ways to constrain the search space for optimizations, which I would think could be potentially guided by ML? I think that there would be a lot of cases where engineers would accept 10x longer compile times if it gave 10% more application performance.
- pjc50 3y agoML systems do not guarantee valid output. If you have a system that can prove a given transformation is behavior-preserving, then sure you can let the AI have a go at it and then check the result, but having such a checker is much harder than it sounds.
- brickteacup 3y ago> ML systems do not guarantee valid output no one said this has to be an LLM or whatever. you could have a compiler that just uses ML-based cost heuristics. iirc some research has already been done in this direction
- compiler-guy 3y agoThere is a fair amount of academic research on this topic. Eg, MLGO[1], but I don't know of any being used for production work. 1. https://arxiv.org/pdf/2101.04808.pdf https://arxiv.org/pdf/2101.04808.pdf
- bick_nyers 3y agoThanks for the link, I've seen statistical models used in computer architecture e.g. branch predictors, so I figured it might translate to compilers as well. Excited to learn more when I take a compiler course next year, as compilers are the most "dark magic" part of software to me.
- stabbles 3y agoRust's borrow checker could probably be used for alias analysis, and avoid emitting redundant load instructions. That would give it a competitive advantage to C++. Does something like this exist yet?
- cwzwarich 3y agoRust actually already does this to some degree, using LLVM’s noalias annotations (after many years of exposing latent LLVM bugs and having to disable them). There’s more that can be done here, see e.g. https://github.com/rust-lang/rust/issues/16515 https://github.com/rust-lang/rust/issues/16515 There are also soundness issues around async/await: https://github.com/rust-lang/rust/issues/63818 https://github.com/rust-lang/rust/issues/63818 LLVM’s aliasing model isn’t really optimal for a language like Rust with very precise memory dependence information, but using anything else would mean making a whole new optimizer/backend from scratch.
- hirvi74 3y agoThe people who worked on the compiler are far more intelligent and knowledgeable than I am, so I would say that I can trust the complier with great confidence. I do not think most people are writing software where niche optimizations are truly necessary. Well, at least I am not.
- deleted 3y ago[deleted]
- Dwedit 3y agoYou can't trust compilers anymore because they are way too aggressive about considering well-defined but platform-specific behavior to be "Undefined behavior".
- quelltext 3y agoI think there's probably an underexplored sweet spot where IDEs gain the ability to hint at what type of optimizations the compiler will be able to do, and you could even specify which ones you want to select visually. Which in term is left as a textual annotation that's "statically checked", i.e. if the compiler cannot perform the expected optimization anymore it will reject the annotation with an error or warning whichever degree of freedom you decided to give the compiler. Could get a bit unwieldy but it might not have to. You could also combine this with generative ML to suggest refactors that lead to potentially more easily optimizable code. It doesn't have to be perfect just assist enough for you to gradually build intuition. ML could also provide estimated guesses on how an optimization might speed up a given logical unit of code. What you get is writing readable code but still a clear idea of how it will behave / impact the compiler. It does of course go counter the idea of abstraction. But if we do advocate for people to learn how the compiler will optimize or not we might as well invest in tooling to support that.
- dwrodri 3y agoLike this? https://en.cppreference.com/w/cpp/language/attributes/likely https://en.cppreference.com/w/cpp/language/attributes/likely
- quelltext 3y agoNo quite, those are hints to guide the optimizer to do a better job based on programmer knowledge. They aren't attributes to indicate "I expect / need this particular optimization A to be done on this code block".
- afmos 3y agoI don't think the argument "Compilers are tools. They can reliably vectorize code if it is written in an amenable-to-vectorization form." is proved correct here. I think I'll stay at level 2. In my experience relying on auto-vectorization is brittle: - Even if the compiler should be able to auto-vectorize code written in an amenable-to-vectorization form, that doesn't mean it will. Maybe the particular compiler and version you're using does auto-vectorize, but that doesn't mean other compilers will. This might be a less of a problem in Rust, where you effectively have only compiler (although there are still compiler updates). - Even if you managed to once write the code in an amenable-to-vectorization form, that doesn't mean that the code will stay that way forever. Code tends to change. - Sometimes it's far less obvious what the amenable-to-vectorization form should look like, or what the reasons are for the compiler failing to auto-vectorize. The classic example is the compiler failing to auto-vectorize a floating point sum, since the order in which floating point numbers are added affects the result.
- gumby 3y agoAnother important aspect not brought up is the semantics of the programming language itself. FORTRAN doesn't have memory aliasing (at least in arrays -- it's been a while since I wrote any FORTRAN code) so the compiler can make assumptions (and from them optimizations) that it cannot in, say, C or C++. The author points out the "myopic" nature of compilation, implying that a more global view of the code might allow the compiler to prove that no aliasing happens in a particular code path. I think that problem is Turing complete.
- ssivark 3y agoOn a related note, folks who found this interesting might also like to read “There’s plenty of room at the top” where computer scientists showed how orders of magnitude performance is left unused when a naive high-level implementation is not optimized for the hardware (combination of coding style and compiler insufficiency). https://news.ycombinator.com/item?id=36921588 https://news.ycombinator.com/item?id=36921588 Much broader in scope than OP, that also has many insightful nuggets there about how to think about software and system design, especially in the post Moore’s law era.
- LorenPechtel 3y agoIn my experience the human should do the gross optimizations--choose the right algorithm. And beware the operator--I've had multiple things where an O(n^2) was perfectly reasonable (and probably the fastest runtime given the lack of overhead of setting up better answers) given the original problem--but then n blew up down the road.
- Remnant44 3y agoThe article is spot on about SIMD. Often, if you can write your code in exactly the specific form that you would if you were using intrinsics, the compiler will go ahead and SIMDify for you. But you have essentially a 0% chance of writing in that form unless you already have experience writing SIMD code! Things like branches, loop termination not being regular, alignment, aliasing, function calls, etc all can and do stop your otherwise totally amenable code from vectorizing. In the terminology of the article, I'm still at Phase 2. By the time I've worked out the dataflow and constraints needed to make a loop parallelize, I've more or less converted it into the form needed for intrinsics already, so why not write them and be sure. More broadly, the biggest impact I've seen using MSVC (which most of my code is written in), is the function inliner makes absolutely terrible decisions, particularly with lambdas, which is really unfortunate because there's no way to force-inline the lambda. Combine that with the above - the presence of the lambda will prevent vectorization, even though if it was inlined it would then be trivially vectorizable. :(