13 ms·
Clang Format Tanks Performance
- BeeOnRope 7y agoAuthor here, happy for any feedback. I'll own up to misleading-and-possibly-clickbait title, I just gave up trying to think of anything better without revealing the conclusion.
- acemarke 7y agoClickbait, but _good_ clickbait :) I do so love good deep technical blog posts that dig into why something works a certain way, and the title is a legit statement based on the initial cause. Thanks for writing this!
- Someone 7y agoclang format can tank performance” would, IMO, not decrease the number of people who click the link, yet remove the clickbait.
- BeeOnRope 7y agoCould be, but I feel it would equally dishonest? This really has nothing to do with clang-format: I only mention that once (twice with an update: where clang format actually helps because it reorders stdlib.h after ctype.h) - it's all about header include order.
- mipmap04 7y agoMaybe someone should make a tool that randomly reorders your header includes until optimal performance is found.
- emmelaich 7y agoI think clang-format is definitely relevant; the take-away here is that no formatter should change the order of includes. I was wondering about this only yesterday - tidying up some C++ and C code. I don't remember any standard that says it's OK to re-order headers, and clearly it can matter a lot.
- BeeOnRope 7y agoThat wouldn't be my take away. My takeway would be anything that changes in semantics or performance due to header includes should be considered a bug by the (possibly joint) writers of the involved headers. clang-format is an innocent victim here. Maybe I should make that clearer.
- flukus 7y agoClang isn't the root cause, but as a (relatively) new tool in an existing ecosystem it needs to work with the existing ecosystem and not some imaginary idealistic world.
- mypalmike 7y agoChanging semantics due to header order is considered a feature in C/C++. If you aren't willing to waste hours working through esoteric header issues, you just aren't tough enough.
- BubRoss 7y agoWhy does every title have to be a mystery? Why not tell people what it contains?
- BeeOnRope 7y agoIn this case it's an excerpt of a larger post that I was writing while I ran into this. I don't think there is a good single-sentence title that would encapsulate the whole thing without being an already well-known fact, like say "Header include order matters". Also, I wrote this one as a narrative, not revealing the conclusion at the start - basically a reconstructed version of how I encountered it myself. I don't write all my posts like that and it's not for everyone: but once I've decided on that, it makes no sense to reveal the conclusion in the title, I think? The HN headline could be changed though if it places a priority on information-full titles.
- pvg 7y agoIt places priority on not-clickbait, above most things. You could have a title that isn't super descriptive, asks a question, maintains an air of mystery, whatever. But a title that deliberately elevates some near-irrelevant detail for attention is purposefully deceptive and, well, less than good (by HN's rules, that is).
- BeeOnRope 7y agoEh, sure - but you are arguing for non-clickbait titles, while I was replying to the OP who complained about not revealing more about the conclusion in the title. It seems we agree there that some mystery is allowed: the point of contention is on "click-baitiness". I don't have a similar principled defense of clickbait titles, either in general or mine specifically! I just thought it was a funny one and didn't expend more effort on coming up with a non-clickait one. That's an independent issue from revealing more info in the title.
- pvg 7y agoOh, I don't really have any argument about what titles you should put on your own writing. It's your writing, if you feel its narrative purpose is served by an intricate web of title feints, line noise, whatnot, more power to you. I'm just explaining the HN title rules, you can see them here (do a find title): https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html There's nothing in there about titles having to be 'information-full'. Lots of perfectly HN-good titles aren't.
- JonathonW 7y agoJust to make sure I'm understanding this correctly: the performance issue you found actually amounts to include-order dependent behavior in GCC and glibc; clang doesn't really have anything to do with anything here except that you used its code formatter to sort your include statements. If that's the case, the clickbait-y headline's bordering on useless, since the performance differences here have nothing to do with clang itself-- you'd see the same results if you had ordered your includes the same way by hand.
- big_chungus 7y agoNo, the headline pretty clearly states "Clang Format". I've used clang-format on MSVC codebases, and imagine there are some who use it with GCC (say, for instance, the author). It's still the best C++ formatter, as far as I know, and is compiler-independent.
- BeeOnRope 7y agoIt's basically the gorilla in the space, and it's good. There is no gcc equivalent. In any case there no 1:1 relationship between formatters anyways: you might compiler you codebase with N compilers, but you'll only have one formatter unless you are insane. So my codebases are not "gcc" or "clang" codebases, but basically "linux" codebases - but the formatter is always clang-format.
- BeeOnRope 7y agoI'm talking about clang-format, a formatting tool for C and C++ code, which has nothing to do with compiling your code with clang. You can use it with any compiler. That said, the title is still a lie in that clang-format is not really at a fault here at all: clang-format triggered the issue on my codebase, by sorting header files, and this in turn triggered a libc performance issue. So as I initially say it, a commit which purely clang-format 'd my codebase caused a massive regression - but the full story is doesn't implicate clang-format at all, really.
- glandium 7y ago
- pydave 7y ago> Are my standard algorithms letting me down? Does std::transform have some fatal flaw? Not really. Well, not at all. This part lost me because I can't see how you can use std::transform (which is in <algorithm>) without hitting this flaw. Unless you edit the headers? I guess you mean the algorithm isn't flawed. I also didn't understand the title because I don't use clang-format and I skimmed past the single mention of it (my fault). Regardless, interesting post.
- deleted 7y ago[deleted]
- BeeOnRope 7y agoThe title was basically clickbait. It reflects how I encountered the issue, but the investigation doesn't have much of that, because I was starting from a point where I suddenly had a slow and fast algorithm (the actual scenario was more complicated than shown). The investigation doesn't have much to do with clang-format because I'm just trying to see why a raw loop is faster, and ultimately has nothing to do with "raw" vs "std" at all, really. Only when I understood that includes and include order matter was I able to map it back to a header order swap made by clang-format. > This part lost me because I can't see how you can use std::transform (which is in <algorithm>) without hitting this flaw. No, two ways. You can get the fast performance with std::transform if you happen to include <ctype.h> before <algorithm>. The order matters. Similarly, you can get the slow performance with a raw loop if you happen to include <algorithm> before <ctype.h> in the file for the raw loop. In fact, I'd say that the raw loop and std::transform will have the same performance almost all the time. If they are in the same file, they will have the same performance. If they are in a C++ file, you are almost certainly including some C++ header that triggers the issue. Only in special cases, like a coding convention that separates C and C++ headers with whitespace with C first (clang-format doesn't sort headers separated by whitespace) are you likely to come into it "natively". Even if you do, it's absolutely no fault of std::transform or <algorithm> - it's a weird effect of interaction between C, C++ and OS headers, nothing inherent to the C++ algorithms.
- TwoBit 7y ago
- fyp 7y agoThe "three observations that aren’t really part of the story" were really interesting and doesn't seem to be fully resolved. Will you be discussing them more in the future post?
- BeeOnRope 7y agoMaybe. This is really a three part answer, since there were three quite-different effects I glossed over. The first one is interesting, but it is also well-covered elsewhere, e.g., [1], [2] and [3]. That said, I have a ton of stuff to say on branch prediction, so I probably will at some point. Those posts are slow going, however. It may never emerge. For the second and third points, I am partly blocked by the fact the effect disappeared or is only intermittently reproducible. I am more interested in the third uninteresting effect than the second. The second thing could be a lot of things, since it shows up when running a python script with results piped to disk. What I've seen in the past is that the "driver" program (driver.py) undergoes some kind of phase change, e.g., suddenly causing a bunch of context switches or allocating/freeing a munch of memory which affects the program under test (despite CPU pinning, since there are shared resources). They are phantoms (but still interesting!). The third one is very interesting to me, because it involves a CPU-bound loop with only L1 hits. It goes to the core of the Skylake uarch and the kind of fine-grained uarch details I'm interested in. However, it disappeared as I was tracking it down. I was getting a mix of 2.07 cycles and 1.57 cycles (slow and fast) running the benchmark repeatedly, trying differnet perf counters and doing the needful to track it down and then suddenly I only got 2.07. A new plot showed "blue" only at ~2.07. So I don't know. I have seen similar things though, and I've tracked down an similar "mode shift" and will post on it soon. Stay tuned. --- [1] https://lemire.me/blog/2019/11/12/unrolling-your-loops-can-improve-branch-prediction/ https://lemire.me/blog/2019/11/12/unrolling-your-loops-can-i... [2] https://lemire.me/blog/2019/10/16/benchmarking-is-hard-processors-learn-to-predict-branches/ https://lemire.me/blog/2019/10/16/benchmarking-is-hard-proce... [3] https://lemire.me/blog/2019/10/15/mispredicted-branches-can-multiply-your-running-times/ https://lemire.me/blog/2019/10/15/mispredicted-branches-can-...
- gpm 7y agoI'm going to take the contrarian view here, and say it's not clickbait. I admit that I'm not a C++ expert, but naively I would never have expected clang-format to have any effect on my code. If you stopped and suggested header re-ordering to me my first thought would have been "I guess it must not do that. Maybe in practice header re-ordering doesn't actually matter with reasonable code?". The title here doesn't describe the contents of the article, but it describes a very important consequence of it that C++ programmers should be aware of. It gives a specific example of the consequence. I'm ok with that.
- BeeOnRope 7y agoI agree with most of that, although as the author I think it's still clickbait in the sense that: 1) clang-format is not really at fault here at all - the same effect could have happened by adding a new header, reordering the headers manually, switching to a system with a different libc version or a different transitive header include tree, etc. 2) The title doesn't tell you wtf is up. You have to get at least half way through the post to figure that out. It's in the vein of "This one food could wreck your health" posts. That said, other aspects of clickbait are advertising or monetization to profit from the clicks. Except for the crypto mining bot I load into your browser, and which subsequently writes itself to your MBR or UEFI partition, I have no ads, affiliate links, patreon-alikes or other monetization vectors.
- fizwhiz 7y ago> Except for the crypto mining bot I load into your browser, and which subsequently writes itself to your MBR or UEFI partition Guess I won't be clicking on the link now.
- skrebbel 7y agoYou're missing out. It's a great article, definitely worth all that monero.
- TehCorwiz 7y agoAt least you’re forthcoming.
- iameli 7y agoI clicked because of the title and laughed when I read the reason, don't sweat about anyone accusing you of clickbait
- jimbo1qaz 7y agoI read the title and thought the article was about (clang-format's performance) on a (program simulating military tanks)... Apparently you meant "tanks" as a verb...
- BeeOnRope 7y agoYes, although a quick search reveals that Oxford considers this a US usage so it was probably not the ideal choice for a title.
- deleted 7y ago[deleted]
- lazyjones 7y agoMessy (esp. standard library) header files like in this case is why C/C++ isn't really fun today, for me anyway.
- ufo 7y agoCan the std::transform version be written without a lambda? std::transform(buf, buf + size, buf, toupper);
- BeeOnRope 7y agoYes, it can! In fact I had that at some point and clobbered it with a git reset (the perils of developing on two machines and once and using git a sync mechanism). Fixed [1] and credited. --- [1] https://github.com/travisdowns/travisdowns.github.io/commit/cff0322d9b45d9ec18a8a069f7429589574b8b83 https://github.com/travisdowns/travisdowns.github.io/commit/...
- account42 7y agoThis could actually change performance though as the lambda version gives you a unique templace instantiation of std::transform while the non-lambda version requires std::transform to be inlined into the caller (or cloned to an argument-specific version) before the compiler can make any optimizations based on its knowledge of toupper.
- BeeOnRope 7y agoGood point. I would usually expect std::transform to be inlined, since it is quite simple - but it may not be and it's a very good point in general regarding the optimization probability for function pointers versus lambdas. Ultimately, I ended up reverting the change, so using a lambda based on the advice the taking the address of a standard-library function is verboten, since they may introduce overloads at any time [1]. --- [1] https://twitter.com/foonathan/status/1197051249822195712 https://twitter.com/foonathan/status/1197051249822195712
- YSFEJ4SWJUVU6 7y agoYes and no. Technically that results in UB with many inputs with platforms that use a signed char type.
- thestoicattack 7y agoYou also get the slow version if you include <cctype> instead of <ctype.h>. https://godbolt.org/z/cbeGc4 https://godbolt.org/z/cbeGc4
- BeeOnRope 7y agoYes, I saw that too and mention it: > As a corollary, if you include <cctype> rather than <ctype.h> (the C++ version of the C header which puts functions in the std:: namespace) you also get the slow behavior because <cctype> ultimately includes <bits/os_defines.h>.
- thestoicattack 7y agoOh, so you do!
- ufo 7y agoA fascinating read. Is there a sane way to fix this in a future version of glibc?
- BeeOnRope 7y agoI mean if you wanted the inline body to be visible to C++ you just have to slightly reorganize the ctype.h header so those definitions are available to C++ code (i.e., visible when __cplusplus is defined), because right now the bodies are getting caught the same #ifdef net that macro definitions are (but the body is not a macro). That said, any exposure of implementation details, including inline bodies like this, is risky and constraining for future changes, since you bake in part of the implementation and also commit to supporting that implementation as far as you backwards compatibility strategy requires. So it is entirely possible that the non-inlining is intentional, but then the part about include ordering mattering doesn't make sense, and if you are willing to commit for C programs, you are probably willing to commit in C++ too. You'd have to really spelunk the history of this files or ask the people responsible to be sure. It seems more likely that that conditional compilation block is intended to avoid implementing standard library functions as macros, which is probably barred by the C++ standard (e.g., so you can use the name `std::tolower`) - and the inline bodies just got caught in the crossfire.
- MiSeRyDeee 7y agoThis is both technically in-depth while so hilarious. Love this post!
- sesuximo 7y agocctype is such garbage. not real functions, takes/returns int, not contexpr, and now this trash. bleh
- goalieca 7y agoLink time inlining would solve this.
- BeeOnRope 7y agoIn a sense, yes - specifically if libc could be link-time inlined. I don't think many people are proposing that for libc though because it would shut down the possibility to patch libc for anything that has been link-timed inline, and more generally expose the internal implementation of libc in a way that will make evolving it very difficult. That is, link-time inlining will see a lot more use within an application before it will ever apply to system libraries.
- quotemstr 7y agoApplying LTO to libc would be no worse than statistically linking it. I don't like static linking, but on Linux, we're stuck with supporting it.
- gpm 7y agoIsn't glibc almost always dynamically linked on linux? I thought half the point of musl was that it supported static linking.
- quotemstr 7y agoAlmost everyone does dynamically link Glibc. You should dynamically link glibc too. But if you really want, you can statically link glibc. $ dpkg -S '*/libc.a' libc6-dev:amd64: /usr/lib/x86_64-linux-gnu/libc.a But please don't. Static linking doesn't give you a compatibility advantage: dynamically linked glibc is specifically designed to be forward and backward compatible. Static linking only makes life more difficult later, since it complicates use of NSS and PAM and precludes nice, clean shims between user and kernel mode. Seriously. It was a mistake for Linux to make the kernel-user transition the stable system ABI instead of putting that stability boundary at the libc layer like most other operating systems. As for static linking being a competitive advantage of musl: I don't know where you got that idea. Musl is less featureful than glibc, not more. In particular, I'm not going to use it until it supports dlclose like every other full-featured computing platform.
- _kst_ 7y ago> I was including stdlib.h just to get the definition for size_t. size_t is also defined in stddef.h, and including that likely won't cause the same issues.
- hombre_fatal 7y agoPlease give us more than one pixel of color in the legend of your graph.
- john-radio 7y agoYeesh, I can't read assembly. Is there somewhere I learn what all movsxd, lea, cmp, ja, and friends do in plain english?
- wilsonthewhale 7y agoThis online reference is helpful: https://www.felixcloutier.com/x86/index.html https://www.felixcloutier.com/x86/index.html For something more formal, the official Intel programming manuals describe what each instruction does in painstaking detail.
- squirrelmaker 7y agoNot sure plain, but still: http://kipirvine.com/asm/gettingstartedvs2010/ http://kipirvine.com/asm/gettingstartedvs2010/ https://software.intel.com/en-us/articles/intel-sdm https://software.intel.com/en-us/articles/intel-sdm
- slavik81 7y agoFollow the links in the article to the godbolt compiler explorer. The disassembly there has a short description of each instruction when you hover over it, and links to the full reference.
- matt_d 7y agoFocusing on x86-64 (don't waste your time starting with the 32-bit variant when learning, let alone x87 FPU instructions, there's plenty of up-to-date materials for contemporary architectures nowadays): - Chapter 10, Assembly Language (https://www3.nd.edu/~dthain/compilerbook/compilerbook.pdf#chapter.10 https://www3.nd.edu/~dthain/compilerbook/compilerbook.pdf#ch...) of http://compilerbook.org/ http://compilerbook.org/ - intro_x86-64: Introduction to x86_64 assembly - https://gitlab.com/mcmfb/intro_x86-64 https://gitlab.com/mcmfb/intro_x86-64 - Introduction to 64 Bit Assembly Language Programming for Linux and OS X - Ray Seyfarth - http://rayseyfarth.com/asm/ http://rayseyfarth.com/asm/ - Introduction to Computer Organization with x86-64 Assembly Language & GNU/Linux - Robert G. Plantz - http://bob.cs.sonoma.edu/IntroCompOrg-x64/book.html http://bob.cs.sonoma.edu/IntroCompOrg-x64/book.html - Modern X86 Assembly Language Programming - 2018; Daniel Kusswurm - Covers x86 64-bit, AVX, AVX2, and AVX-512 - https://github.com/Apress/modern-x86-assembly-language-programming-2e https://github.com/Apress/modern-x86-assembly-language-progr... - Understanding Assembly Language - a.k.a. Reverse Engineering for Beginners; https://yurichev.com/blog/UAL/ https://yurichev.com/blog/UAL/ - https://beginners.re/ https://beginners.re/ - x86-64 Assembly Language Programming with Ubuntu - Ed Jorgensen - http://www.egr.unlv.edu/~ed/x86.html http://www.egr.unlv.edu/~ed/x86.html - Assembly Programming and Computer Architecture for Software Engineers (APCASE) - https://github.com/brianrhall/Assembly https://github.com/brianrhall/Assembly - Videos: https://www.youtube.com/channel/UCr0svQEez3UQvlj6-5EYS6w https://www.youtube.com/channel/UCr0svQEez3UQvlj6-5EYS6w Or, if you prefer talks: - Just enough Assembly for Compiler Explorer - Anders Schau Knatten - NDC TechTown 2019 - https://www.youtube.com/watch?v=soeFwz0cOqU https://www.youtube.com/watch?v=soeFwz0cOqU - Modern x64 Assembly - https://www.youtube.com/playlist?list=PLKK11Ligqitg9MOX3-0tFT1Rmh3uJp7kA https://www.youtube.com/playlist?list=PLKK11Ligqitg9MOX3-0tF... - Bluff your way in x64 assembler - ACCU 2017; Roger Orr - https://www.youtube.com/watch?v=RI7VL-g6J7g https://www.youtube.com/watch?v=RI7VL-g6J7g - Enough x86 Assembly to Be Dangerous - CppCon 2017; Charles Bailey - https://www.youtube.com/watch?v=IfUPkUAEwrk https://www.youtube.com/watch?v=IfUPkUAEwrk More: - Arm / AArch64: https://github.com/MattPD/cpplinks/blob/master/assembly.arm.md https://github.com/MattPD/cpplinks/blob/master/assembly.arm.... - RISC-V: https://github.com/MattPD/cpplinks/blob/master/assembly.riscv.md https://github.com/MattPD/cpplinks/blob/master/assembly.risc... - x86: https://github.com/MattPD/cpplinks/blob/master/assembly.x86.md https://github.com/MattPD/cpplinks/blob/master/assembly.x86....
- krzat 7y agoIt's 2019 and people are still using languages where order of imports matters...
- deleted 7y ago[deleted]
- abainbridge 7y agoIsn't the correct way to write this loop actually: void toupper_cmov(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { char c = buf[i]; buf[i] = c - 32 * (c >= 'a' && c <= 'z'); } } Because that persuades gcc and clang to transform the conditional branch into a conditional move which avoids the branch mispredict penalty and removes the need for a lookup table. See https://godbolt.org/z/xHYKft https://godbolt.org/z/xHYKft Disclaimer: I haven't actually run this function. That would be too much like work.
- nocturnial 7y agoWhy not use -march=native? When I look at it, I hope the compiler knows what it's doing wrt cache and whatnot. https://godbolt.org/z/zRQRkr https://godbolt.org/z/zRQRkr
- abainbridge 7y ago> Why not use -march=native? The conditional jump remains even with -march=native. https://godbolt.org/z/2p7uAB https://godbolt.org/z/2p7uAB
- nocturnial 7y agoYep just noticed it.. wanted to delete the comment but was to slow apparently
- pdimitar 7y agoI may eat downvotes but here's an honest opinion nonetheless: this article shows almost exactly why I wouldn't touch C++ with a ten-foot pole still, after running away screaming from it 11-12 years ago. Not saying it's an unique problem with C++'s tooling. I'm just saying that it has been my experience that one is much more likely to stumble upon such horrors while working with C++ as opposed to at least 7 other languages I worked with. I'll take the slower Rust and Go and Elixir, thank you very much. Don't take this as trash-talking, though. I simply want to get things done, not fight my environment.
- wffurr 7y agoRust is slower than C++?
- The_rationalist 7y agoYes, at best 20% slower but can be far more slower if you hit worst case scenario.
- johnzabroski 7y agoWhy is Mozilla Firefox written in Rust, then? The last time I looked at browser benchmarks was in 2016 when Google released benchmarks to brag about its performance over Firefox and Edge. It appears Webkit has released JetStream2 to benchmark JavaScript, WebAssembly and web workers, among other things. But I can't find data showing Mozilla Firefox is ~20% slower than Chrome/Edge today.
- dthul 7y agoUsing Firefox to evaluate Rust performance is probably not a good idea since only parts of it are written in Rust today. But it's the first time I hear someone say that Rust is supposedly fundamentally slower than C++. I don't believe this to be a statement that can be substantiated, seeing that some of the fastest programs out there (ripgrep and hyper to name just two) are written in Rust.
- LessDmesg 7y agoOrder of headers should not matter in any sane language. This just proves that C++ is not a sane language. Yet Bjarne Stroustrup keeps getting engineering awards! If I were king of programming languages, I would forbid any new lines of C++ to be brought into this world, and install mandatory programmes for rewriting legacy C++ code in sane languages.
- intea 7y agoBut the root cause here lies with GCC or rather glibc and not the language? C++ is but a tool, just like every other language.
- devit 7y agoIt likes with C++ not having a proper module system enforcing properties like module import order being irrelevant, and the glibc developers apparently failing to produce modules having such properties even if the language doesn't enforce it.