7 ms·
Exploiting Undefined Behavior in C/C++ Programs: The Performance Impact [pdf]
- jonstewart 1y ago> The results show that, in the cases we evaluated, the performance gains from exploiting UB are minimal. Furthermore, in the cases where performance regresses, it can often be recovered by either small to moderate changes to the compiler or by using link-time optimizations. _THANK YOU._
- ryao 1y ago> by using link-time optimizations These are almost never used by software.
- mgaunard 1y agoOnly places where I've seen LTO not be used are places with bad and unreliable build systems that systematically introduce undefined behaviour by violating the ODR.
- jeffbee 1y agoThe only organization I've worked in that had comprehensive LTO for C++ code was Google. I've worked at other orgs even with 1000s of engineers where LTO, PGO, BOLT, and other things you might consider standard techniques were considered voodoo and too much trouble to bother with, despite the obvious efficiency improvements being left on the table.
- com2kid 1y agoI helped with pgo work at Microsoft over 15 years ago, back when it was a Microsoft Research project. The issue with early pgo implementations was getting a really good profile, as you had to have automation capable of fully exercising code paths that you knew would be hot in actual usage, and you needed good instrumentation to know what code paths those were! The same problem exists now days, but programs are instrumented to hell and back to collect usage data.
- jeffbee 1y agoI am willing to assume that organizations dedicated to shipping software to customers like Microsoft or Autodesk or somebody like that are almost certainly all in on optimization techniques. The organizations where I worked are ones that are operating first party or third party software in the cloud where they're responsible for building their own artifacts.
- loeg 1y agoFacebook uses LTO/PGO for C++ pretty broadly.
- jeffbee 1y agoYeah they just never hired me. They also invented BOLT. I think there is a valley in terms of organization size where you have tons of engineers but not enough to accomplish peak optimization of C++ projects. These are the orgs that are spending millions to operate, for example, the VERY not-optimized packages of postgresql from Ubuntu, in AWS.
- spookie 1y agoWell, Ubuntu isn't really a good project to look up upon :) Hell, their latest upgrade broke one of their flavours. Not to mention how fragile their installer is.
- UncleMeat 1y agoGoogle doesn't have full-lto either, since binaries are way too big. Thin-lto is vastly less powerful.
- jeffbee 1y ago"Vastly" eh? I seem to recall that LLVM ThinLTO has slight regressions compared to GCC LTO on specCPU but on Google's own applications the superior whole-program devirtualization offered only with ThinLTO is a net win.
- UncleMeat 1y agoI'll adjust my phrasing. As a user, building with thin-lto vs full-lto generally produces pretty similar performance in no small part because a huge amount of effort has gone into making the summaries as effective as possible for key performance needs. As a compiler developer, especially when developing static analysis warnings rather than optimization passes, the number of cases where I've run into "this would be viable if we had full-lto" has been pretty high.
- pcwalton 1y agoYeah, I would have liked to see the paper specify whether the LTO they tried is fat LTO or ThinLTO.
- mgaunard 1y agoIn practice the default ABI on linux x86-64 is still limiting you to binaries that are 4G or thereabout. Not exactly a problem for LTO since any reasonable build machine will have 128GB of ram.
- astrange 1y agoPGO is pretty difficult. In my experience compilers don't seem to know the difference between "this thing never runs" and "we don't have any information about if this thing runs". Similarly it might be useful to know "is this branch predictable" more than just "what % is it taken". CPUs are so dynamic anyway that there often isn't a way to pass down the information you'd get from the profile. eg I don't think Intel actually recommends any way of hinting branch directions.
- jeffbee 1y agoIt's implied by the target offset. Taken branches jump backwards, unlikely branches jump forward.
- saagarjha 1y agoSurely you are not putting code behind an if/else
- atq2119 1y agoNot generally, no. This is true for some chips, especially (very) old or simple cores, but it's not something to lean on for modern high end cores.
- jeffbee 1y agoGenerally yes. This is not for "simple" cores this is the state-of-the-art static branch prediction algorithm as described by Intel in their optimization manual. "Branches that do not have a history in the BTB ... are predicted using a static prediction algorithm: Predict forward conditional branches to be NOT taken. Predict backward conditional branches to be taken." It then goes on to recommend exactly what every optimizing compiler and post-link optimizers like BOLT do: "Arrange code to be consistent with the static branch prediction algorithm: make the fall-through code following a conditional branch be the likely target for a branch with a forward target, and make the fall-through code following a conditional branch be the unlikely target for a branch with a backward target." This is why a reduction in taken forward branches is one of the key statistics that BOLT reports.
- tialaramex 1y agoViolating ODR doesn't introduce UB it's IFNDR, Ill-formed No Diagnostic Required which is much worse in principle and in such cases probably also in practice. UB is a runtime phenemenon, it happens, or it doesn't, and we may be able to ensure the case where it happens doesn't occur with ordinary human controls. But IFNDR is a property of the compiled program, if you have IFNDR (by some estimates that's most C++ programs) your program has no defined behaviour and never did, so there is no possible countermeasure, too bad game over.
- ryao 1y agoI am curious where you have seen LTO used. Linux distributions and open source projects in general rarely use LTO. Their build systems are usually very good.
- jandrewrogers 1y agoLTO is heavily used in my experience. If it breaks something that is indicative of other issues that need to be addressed.
- yxhuvud 1y agoMain issue isn't that it break stuff but that it tend to be pretty slow to compile with it.
- jorvi 1y ago.. that's why you compile without LTO during development and do a final 'compile with LTO > profile > fix / optimize > compile with LTO' pass. Compilation happens once and then runs on hundreds of thousands up to billions of devices. Respect your users.
- astrange 1y agoThis assumes that LTO is strictly better than no-LTO, ie only gets faster, has the same optimization hotspots, and doesn't break anything. I would recommend only doing things that fit within the 'build > text > fix' loop.
- Sharlin 1y agoWhich doesn't matter at all in a release build. And in a dev build it's rarely necessary.
- steveklabnik 1y agoIt's on by default for Rust release builds, so at least the codepaths in LLVM for it are well-exercised.
- alpaca128 1y agoThat must have been changed sometime in the last year then. When I enable LTO for one of my projects on a Rust compiler from 2024 the compilation time more than doubles.
- steveklabnik 1y agoI should have been more clear: thin LTO is, not full “fat” LTO, for exactly that reason.
- vlovich123 1y agoI don't think that's right unless the docs are stale: [profile.release] lto = false https://doc.rust-lang.org/cargo/reference/profiles.html#release https://doc.rust-lang.org/cargo/reference/profiles.html#rele...
- steveklabnik 1y agoSo the thing is that false means thinlto is used depending on other settings, see https://doc.rust-lang.org/cargo/reference/profiles.html#lto https://doc.rust-lang.org/cargo/reference/profiles.html#lto > false: Performs “thin local LTO” which performs “thin” LTO on the local crate only across its codegen units. I think this is kind of confusing but whatever. I should have been more clear.
- LegionMammal978 1y agoThere is no cross-crate LTO with 'lto = false', but there is cross-crate thin LTO with 'lto = "thin"'. The codepaths might still be getting hit, but individual CGUs within a crate are generally invisible to the user, which can create the impression that LTO doesn't occur. (That is, if you operate under the mental model of the crate being the basic compilation unit, then 'lto = false' means you'll never see LTO.)
- Rusky 1y agoIt's worth noting (and the paper does go into this) that this is limited to a very specific subset of UB, which they call "guardable." They are not removing UB around things like out-of-bounds or use-after-free, which would likely be more expensive.
- jonstewart 1y agoI don’t understand the down votes. Conducting empirical research on the performance impact of undefined behavior is fantastically needed, as the C++ committee’s obsession with undefined behavior strictness (in contrast with longstanding semantics, e.g., uninitialized memory accesses being just fine) has been justified largely by how they enable optimizing compilers. This research shows that many types of UB have a negligible impact on performance.
- saagarjha 1y agoYou're getting downvoted because you're looking for a particular result ("UB optimizations don't help performance") rather than actually evaluating the quality of this analysis (which doesn't really support what you want anyway).
- atq2119 1y agoPossibly somebody downvoted because "thank you" in all caps is not a substantial contribution to discussion. It feels like the kind of low effort stuff you'd see on reddit. Also, commenting on downvotes is generally frowned upon.
- mwkaufma 1y agoReading e.g. the 13% perf regression in simdjson from disabling UB: A simpler alternative is to compile the program with LTO. We confirmed that LLVM’s inter-procedural analyses can propagate both alignment and dereferenceability information for this function, which allows the LTO build to recover the performance loss. "can" is doing a lot of heavy-lifting here. Guaranteeing expected optimizations "will" be applied are hard-enough, without leaving it entirely to an easily-derailed indirect side-effect.
- UebVar 1y agoThis is "can" has exactly the same meaning as in "UB can make your programms faster". You could replace it with "it does, at least with clang". LTO is, in this regard, the same as UB, and unlike guaranteed optimizations, such as the single member optimization, or the empty base optimization.
- mwkaufma 1y agoConcretely, here, the UB-exploitation in question in this case is assuming that the "this" pointer in C++ is aligned and non-null, meaning it's a pervasive annotation throughout C++ codebases, not an edge-case. Relying on LTO to "discover" this annotation through interprocedural analysis -- based on my experience of looking at LTO in practice -- will not be as comprehensive, and even when it works it accomplishes its task in an achingly-slow and expensive way. This is a real devil-is-in-the-details case.
- quotemstr 1y agoI love when papers disagree with their own abstracts.
- gitroom 1y agoperfect, this is right up my alley - honestly i keep wondering if teams avoid optimizations like lto just because build pain sucks or if theres some deeper trust issues around letting the toolchain be clever. you think peopled deal with slow builds if it bought way more speed for the final product?
- pcwalton 1y agoI notice that the paper doesn't claim to eliminate all reasoning about undefined behavior for optimizations. For example: int f() { int arr[3], i = 0; arr[3] = 5; return i; } Optimizing this to "return 0" is relying on UB, because it's assuming that i wasn't laid out directly after arr in the stack frame. I believe this is what the paper calls "non-guardable UB". I don't agree with the claim in the paper that their semantics offers a "flat memory model". A flat memory model would rule out the optimization above. Rather, the memory model still has the notion of object bounds; it's just simplified in some ways.
- throwawayqqq11 1y agoSorry, i dont get why the memory layout should have any effect, when its clear in the AST that i=0 should be returned.
- bregma 1y agoIt's clear in the AST that there is undefined behaviour and it is malformed code. It is not valid C code, so what the compiler chooses to do with it is not defined by the language.
- pcwalton 1y agoNote that if you change the code to this you have the same issue: int g(int n) { int arr[3], i = 0; arr[n] = 5; return i; } Without "exploiting UB" it's incorrect to optimize this to "return 0", because of the possibility that i was allocated right after arr and n == 3.
- screcth 1y agoIf we consider writing out of bounds to be legal, we make it impossible to reason about the behavior of programs.
- 1y ago
- nikic 1y agoOne peculiar thing about the benchmark results is that disabling individual UB seems to fairly consistently reduce performance without LTO, but improve it with LTO. I could see how the UB may be less useful with LTO, but it's not obvious to me why reducing UB would actually help LTO. As far as I can tell, the paper does not attempt to explain this effect. Another interesting thing is that there is clearly synergy between different UB. For the LTO results, disabling each individual UB seems to be either neutral or an improvement, but if you disable all of them at once, then you get a significant regression.
- imtringued 1y agoAmazing that the pain of C is unnecessary and offers few benefits.
- hyperhello 1y agoC is very much one level above assembly, the way dipping a jug in the river is one level above bending down to drink. It's a whole lot easier to mechanically translate *ptr++ = 0 to the corresponding machine code than to memorize and write those actual instructions. Neither is going to automatically check the security of your memory access through any more than the jug is going to test the water.
- pjmlp 1y agoIn the good old days of dumb CPUs. There is a world apart between C code and auto-vectorization into AVX 512.
- hnaccountme 1y agoYou don't program C. You program your OS using C. If you look at it this way, does most complaints about undefined behavior go away?