14 ms·
LLVM merges machine function splitter for reduction in TLB misses
- gosukiwi 6y agoLLVM is one impressive (and scary) piece of technology.
- axaxs 6y agoImpressive, sure. But curious what makes it scary to you?
- mulcahey 6y agohave you seen their logo?
- BoorishBears 6y agoHave you heard of the dragon book?
- jasonmp85 6y agoLLVM's logo is a wyvern
- BoorishBears 6y agoYou mean > a winged two-legged dragon with a barbed tail ? https://llvm.org/Logo.html https://llvm.org/Logo.html > The LLVM logo is a stylized wyvern (a kind of dragon). Dragons have connotations of power, speed and intelligence, and can also be sleek, elegant, and modular (err, maybe not). In addition, there is a series of influential compiler books going back to 1977 which featured dragons on the cover. Leave it to HN to jump to nitpick something as meaningless a wyvern vs a dragon but not even take 5 seconds to check the primary source
- anoncareer0212 6y agowhat
- BoorishBears 6y agoWell the nitpicking is pretty well accepted at this point, but since when are spammy comments like this a thing?
- rmdashrfstar 6y ago99% of readers either read and voted or moved on, it’s just one guy who decided to nitpick you, not some nebulous “HN” hive mind collective.
- BoorishBears 6y agouseless nitpicks is a time honored HN tradition.
- mhh__ 6y agoThe LLVM way of doing C++ is basically a wet dream when it comes to C++-isms e.g. not many C++ projects do their own dynamic casts and get away with it. LLVM is fairly well-structured, especially compared to GCC. I don't find it scary but it is a big fat fucker of a codebase.
- ndesaulniers 6y agoAll dyn_cast does is move runtime polymorphism to compile time polymorphism.
- pjmlp 6y agoOWL and MFC come to mind.
- deleted 6y ago[deleted]
- bonzini 6y agoFWIW this particular optimization has been in GCC for about 15 years, though it was only enabled by default in GCC 8. It's not rocket science.
- isatty 6y agoIdk, not learning compiler theory is one of my regrets from school and this does seem like rocket science to me.
- jjice 6y agoThere are a ton of great books out there! If you're looking for a bit of the whole shebang, check out Compilers: Principles, Techniques, and Tools (aka, The Dragon Book). It's an older book, but a lot of what is described in there is still very relevant and good info. If you want a more high level overview at first, I'd recommend Crafting Interpreters [0] and Writing a Compiler/Interpreter in Go [1]. The latter two focus more on lexing, parsing, and intermediate code generation. [0] https://craftinginterpreters.com/ https://craftinginterpreters.com/ [1] https://compilerbook.com/ https://compilerbook.com/
- isatty 6y agoI know I should get to it - maybe I should've done that during the COVID lockdown eh? Thanks for the links, I'll check them out.
- why_only_15 6y agoCommenters elsewhere in the thread are saying this optimization existed in LLVM as well, just that this is a more deep/efficient version of it.
- bonzini 6y agoYes, I'm referring to this particular version.
- emerged 6y agoI take it this is a form of profiler guided optimization? Does MSVC already do this during its PGO? It seems like an obvious thing to do.
- DSingularity 6y agoYes it is, not sure what MSVC does.
- neerajsi 6y agoMSVC does have this optimization. It has 3 sections: 'live', 'sick' (referenced, but uncommon), 'dead' (unreferenced in the profile).
- jeffbee 6y agoYes, this is a pretty old technique. There were papers about hot/cold function splits based on profile data as early as 1996.
- caf 6y agoThe technique itself isn't new in clang either. This is about a new implementation of it, where the difference to the existing implementation is that this happens later in the process (it's deferred to the machine-specific code generation phase, whereas the existing implementation happens in the middle-end and is target-agnostic).
- vlovich123 6y agoThe other major piece is that the hot-cold split is more efficient. Rather than thunking out the cold code via a function call it just jumps to the basic block, making it a more efficient approach (no register spilling and function call overhead)
- caf 6y agoThe function call overhead itself is irrelevant, because by definition these blocks are cold. The saving/restoring of callee-clobbered registers does affect the code size of the hot function though, so that's important.
- jeffbee 6y agoThe post on llvm-dev is ever so much more interesting. https://lists.llvm.org/pipermail/llvm-dev/2020-August/144012.html https://lists.llvm.org/pipermail/llvm-dev/2020-August/144012...
- snehasish 6y agoThe llvm-dev google group retains the formatting of the original email and is slightly easier to read though it requires a gmail login. https://groups.google.com/g/llvm-dev/c/RUegaMg-iqc/m/VFyV9cX4BQAJ https://groups.google.com/g/llvm-dev/c/RUegaMg-iqc/m/VFyV9cX...
- goalieca 6y agoSince when did it require a Google login to view?
- mcpherrinm 6y agoThe "old" groups UI (URLs like https://groups.google.com/forum/#!topic/llvm-dev https://groups.google.com/forum/#!topic/llvm-dev) doesn't require a login right now. It briefly did, and the Golang team complained and got the change rolled back (probably temporarily). The "new" UI (URLs like https://groups.google.com/g/llvm-dev/ https://groups.google.com/g/llvm-dev/) has always needed to be logged into google afaik.
- judge2020 6y agoThat's linking to a specific reply, here's the main reply: https://groups.google.com/g/llvm-dev/c/RUegaMg-iqc/m/wFAVxa6fCgAJ https://groups.google.com/g/llvm-dev/c/RUegaMg-iqc/m/wFAVxa6... Looks like it requires a Google account now though, I can't get it in incognito.
- moonchild 6y ago> requires a gmail login https://archive.is/pqLgW https://archive.is/pqLgW
- MaxBarraclough 6y ago> Google engineers found a 2.33% runtime improvement with a ~32% reduction in iTLB and sTLB misses Not bad. Presumably this will benefit every compiler that uses LLVM, not just Clang.
- monocasa 6y agoOr at least any that supports gathering and utilizing profiling information. Last time I checked, that didn't include Rust yet for instance, but my information could be out of date there.
- kibwen 6y agorustc does support PGO, but I don't know how mature the support is. https://doc.rust-lang.org/rustc/profile-guided-optimization.html https://doc.rust-lang.org/rustc/profile-guided-optimization....
- rmdashrfstar 6y agoCan I create profile data by running the instrumented binaries through testcases? Perhaps integration test cases which represent typical end to end functionality of my application.
- fluffy87 6y agoRust does support PGO
- ladberg 6y agoFYI, this requires profile data to do the splitting. Yet another reason to do PGO!
- repsilat 6y agoFor many use-cases FDO ("feedback-driven") can be more convenient and sometimes mkre effective than PGO ("profile-driven"). The difference is sampling prod vs sampling separately in test. The arguments for FDO: - Prod behaviour/data is always "representative", whereas synthetic or recorded data can go out of date quickly. -PGO test fixtures can contain sensitive user data. Instrumenting production processes doesn't put data in more places. The benefits of both are huge though. The rule of thumb I've seen is a 20% improvement for FDO over -O3.
- throwaway17_17 6y agoI’m interested in reading some more on this concept, The Wikipedia, which usually my first stop for a broad overview and maybe some linked research, seems to suggest that profile directed/guided and feedback guided are the same thing. Is there anywhere I can read about the varying approaches?
- jeffbee 6y agoThey are the same thing. The GP makes a distinction which does not exist. Witness the fact that two different compilers refer to the exact same feedback technique as either AutoFDO or SamplePGO.
- repsilat 6y agoAh, I definitely worked in a place where that distinction in terminology was used, but maybe it isn't widespread. In any case, whatever you call either one of them, sampling from production processes can have benefits over sampling from synthetic workloads.
- 6y ago
- saagarjha 6y agoNote that LLVM has already had a function outliner; you may have seen these paths already if you've ever looked inside a binary on macOS and noticed * .cold. * functions, which is the unlikely-to-execute code cut out from the function they came from. This appears to be an improvement on that effort.
- quotemstr 6y agoRight. The improvement that this work brings is that it performs the function split very late and at a low level. Basically, while the previous outliner split a function into two functions (the hot one literally calling the cold one as needed) this new thing takes a single function and splits it into two parts connected to each other by jumps. The cold part of the function isn't really a function --- it's just a group of basic blocks that happen to be located far away from the other group of basic blocks. By avoiding the call into the cold function and the return to the hot function, the generated code can be smaller and more register-efficient.
- simcop2387 6y agoThat'll make it more stack efficient too since it doesn't have to go through the same dance for a function call. It probably didn't do them while adhering to the C ABI but it'd still put at least a return address and I suspect some registers during the call.
- saagarjha 6y agoThere’s no need, though: the entry point and return address are unique; it’s literally code that is sliced out, jumped to, and it jumps back to the function it was cut out of. The only thing you’d need to save is a register or two if you can’t make the jump without doing some math.
- quotemstr 6y agoX86 should always be able to jump directly, and ARM sets aside x16 and x17 just for this kind of math. But all jumps should be PC relative, so you shouldn't have to clobber anything anyway
- Ericson2314 6y agoThis + multi-return (push multiple code addresses in stack frame) together mean I think we can just use Result/Either and never unwinding, and leave no performance behind.
- zelly 6y agoIt doesn't work in Rust, only Clang
- Ericson2314 6y agoWhy? Other commenters were talking about PGO and saying Rust did support it.
- IvyMike 6y ago> We find that most functions 5 KiB or larger have inlined children more than 10 layers deep Ok, I would not have expected that.
- jackpirate 6y agoI wouldn't have expected any functions to be 5KiB or larger. That seems like a lot of assembly to me, and so it makes sense to me that these functions would be "accidentally" generated by inlining. I'm curious what percent of functions are this large?
- mac01021 6y agoI've seen plenty of c/c++/java functions that exceeded 200 lines of high level code. It seems reasonable to me that such a function would be 5k bytes of machine code, especially on a 64-bit architecture. Not that such functions are the right way to structure your program...
- account42 6y ago> especially on a 64-bit architecture Pointer size has little impact on code size. amd64 code can even be smaller than x86 in some cases.
- knaq 6y agoI think you could easily get past a megabyte with auto-generated parser code. That would be stuff like lex, yacc, bison, antlr, flex, etc. Anything with a big switch would qualify too, such as an emulator.
- jcranmer 6y agoTotally non-scientific measurement (I took a few applications I had lying around, got size of symbols with nm -S) suggests that you're looking at around 0.1-1% of all functions are larger than 5KiB. Interestingly, the largest function all cases seemed to be something on the order of "initialize a large static hashtable."
- 6y ago
- vlovich123 6y ago2% better perf isn't anything to sneeze at but also not super drastic. Will be curious to see if this unlocks more optimizations over time. I'm also curious if there's been any work to organize code layout to make it more efficient to page stuff out efficiently to reduce memory pressure (so that you're using all code in the pages you are bringing in) & reduce paging thrash (you're not evicting a code page only to bring it back for a few hundred bytes).
- hinkley 6y agoGiven the greatly improved TLB hit rate, I sort of wonder if the test isn't abusing the code enough. Does this change the inflection point where throughput falls from trying to run too many tasks in parallel or sequentially? 2% response time won't do much, but 10% higher peak load would change quite a few priorities on a lot of backlogs.
- vlovich123 6y agoIt’s not too surprising to me. If TLB misses cost your program to run 6% slower, wouldn’t you expect a 30% reduction in that to be a 2% overall improvement? Why would it be more? If you’re surprised that TLB misses are not so costly, consider that cache locality and CPU prediction are largely going to hide the cost of misses (cache locality means the miss rate is low to begin with, prediction reduces the cost of a miss). TLBs are also super complex involving a few layers of caching (TLB look aside, L1 cache of your TLB table, L2 cache, L3 and then RAM).
- emerged 6y agoOne issue with PGO is you are optimizing for the particular subset of use cases which are profiled, on the exact machine you profile on. The 2% quoted improvement will not necessarily generalize across all use cases for the software and all machines it runs on. In fact, you may often be taking that 2% or more away from other use cases.
- drivebycomment 6y ago> One issue with PGO is you are optimizing for the particular subset of use cases which are profiled, on the exact machine you profile on. The exact machine part is not true. There's nothing about this particular optimization that's machine specific - e.g. as the original post explains, this optimization gives performance boost on Intel and AMD, on Intel due to reduction in iTLB misses, and on AMD due to reduction in L1 and L2 icache misses. i.e. this kind of "working-set" reduction translates to any platform. > In fact, you may often be taking that 2% or more away from other use cases. In general, it is correct that profile-guided optimization can theoretically reduce performance, as some of the aggressive optimizations are only done with profile because of inherent trade-off the optimization has (e.g. aggressive inlining which can be detrimental for the performance if hot functions are entirely different). However, empirically this is not true in most cases, unless you picked really bad training input, and your code has extremely different behavior under different input. Moreover, nowadays with sampled profile, which you can collect from the real, production runs, it's extremely unlikely for this to happen.
- kevincox 6y agoYes, taking advantage of PGO is hard. But with the right infrastructure you get very accurate profiles. For example many large companies will gather the profiles from the previous version running in production. I have even seen cases where the new version was fed replayed requests then recompiled with the recorded profiles. So yes, PGO is hard, but if you collect representative profiles it is a massive improvement.
- voldacar 6y agoSo to use this new optimization pass you have to specify it explicitly with an additional command line flag instead of it simply being turned on as an ordinary part of PGO? It seems like most people who just want to squeeze the last drop of speed out of their code will probably never become aware of it then unless they are specifically seeking it out
- mafuy 6y agoIt's an experimental feature. If it works well for a while, it may become part of the default. But it should definitely not be forced on everyone if it's not yet sure how well it works.
- account42 6y agoIn their comparisons they explain that the existing Hot Cold Split creates new functions for the cold parts which brings overheads due to calling conventions and exception handling. Their new method avoids that by using simple jumps. I wish compilers were able to optimize functions boundaries for visible but not inlined better so they could optimize those function call overheads away automatically. There is no reason for a compiler to limit itself to the system ABI for completely internal functions. Besides leaving values in the registers they are already in instead of moving them to where the ABI says they should be, this could enable passing C++ objects such as std::unique_ptr in registers where the current ABI forbids this. Or to eliminate nop destructors for objects that are always moved from in the called functions. In general, I think compilers should see function boundaries in the source code as a mere hint when it comes to code generation just like they already do with the register keyword. Is there any existing compiler work to optimize function calls where the implementation and all uses are visible in the translation unit?
- saagarjha 6y agoFunctions by default have external linkage, and as such can be called by anyone. So of course this could only apply to functions that are static or internal in some way. Once you have that down, you have to deal with the fact that the things you would want to optimize may differ at each call site (one may like to keep rdx free, one may be able to give up rdi) so I am unsure it would be worth the effort to not follow the ABI.
- account42 6y ago> So of course this could only apply to functions that are static or internal in some way. Or with LTO / -fwhole-program: functions that have hidden visibility. Which is all of them for Windows executables and the default for DLLs (and -fvisibility=hidden is a sane default for other systems too). > Once you have that down, you have to deal with the fact that the things you would want to optimize may differ at each call site (one may like to keep rdx free, one may be able to give up rdi) so I am unsure it would be worth the effort to not follow the ABI. Sure, that makes things harder. But in many cases will only be one call site. In others you can still figure out which optimizations you can apply to all of them - for example passing std::unique_ptr and similar objects by register should always be doable as long as you control all call sites. Further, the compiler has the option to clone functions in order to apply optimizations specific to a group of call sites if it decides that an optimization is worth the increased code size. And some optimizations will be purely on the caller side - for example not spilling caller-saved registers if you know they won't be clobbered by the callee.
- derangedHorse 6y agoIt always surprises me how many people are familiar with LLVM internals. Just looking at the 60 unique commenters at the time of posting this is blowing my mind.
- person_of_color 6y agoGoogle improving an Apple project. The high ground!