Clang Format Tanks Performance
travisdowns.github.io
travisdowns.github.io
I'll own up to misleading-and-possibly-clickbait title, I just gave up trying to think of anything better without revealing the conclusion.
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.
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.
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.
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.
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.
I'm just explaining the HN title rules, you can see them here (do a find title):
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.
I didn't submit it to HN so I can't comment on the title choice, other than say it at least reflects the literal title of the page which I guess would be the default when submitting.
I tend to outsource my comments to HN, since my blog is a github pages static site and introducing comments without tracking and ads is a pain, but I definitely don't choose my post titles to satisfy HN rules.
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.
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.
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.
Fixed now [1], although the HN title will remain hyphen-free free I guess.
---
[1] https://github.com/travisdowns/travisdowns.github.io/commit/...
It is quite common to have an auto-generated configuration header, for instance; or a precompiled header; or optional headers that, when present, mutate the behaviour of other headers.
Every time you run a configure script for a C project there's a good chance you're interacting with code in this way.
It's not like clang-format was written by idiots who never used the language before. Maybe read up on what the tool actually does before you get all mad at them?
I think it's a harmful anti-feature that's worthy of criticism.
This helps ensure that your specific project level header files have all the necessary forward declares and includes to be a fully functioning and complete header.
In the end though you'll have to make a decision on how to sort the projects and which one is more or less specific than another. Kind of like deciding to just sort by pointer address if all else is equal.
The crucial __NO_CTYPE define is in <bits/os_defines.h>, which is part of the GCC paraphernalia. I don't know if clang's stdlib would also have to end up defining it.
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.
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.
IMO this is a library bug. <algorithm> shouldn't be limping toupper or anything else.
That's not really because performance doesn't matter, but because toupper() shouldn't really matter in most modern C and C++ programs: it just can't support Unicode. So either you are using a different way of supporting strings entirely (if you need any kind of Unicode or multibyte support), or this is some internal ASCII-only text processing in which case you are better off using your own methods (e.g., the lookup table I mention at the end) since they'll provide an easy speedup and you aren't accidentally introducing locale-dependent code where you don't want it.
In addition to more instructions and a function call, the slow version has many more memory dereferences, so if everything is very cold it is likely to suffer more misses.
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-i...
[2] https://lemire.me/blog/2019/10/16/benchmarking-is-hard-proce...
[3] https://lemire.me/blog/2019/10/15/mispredicted-branches-can-...
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.
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.
This is a _bad_ clang-format bug.
C/C++ headers are literal code-injection mechanisms; they aren't modifying a runtime environment by importing symbols, they inject code into the compilation unit.
Those are some pretty dumb coding standards if that's true.
(I mean, yeah, the original fault is with the C preprocessor and the fact that header order matters, but since we're stuck with that, having those kinds of coding standards is pretty darn silly!)
The article describes false complexity caused by looking atr the issue in the wrong way: a "mysterious" performance problem, to be diagnosed, rather than the obvious consequence of a broken workflow that includes an extremely hazardous operation.
In a voluntary header reordering experiment, all kinds of breakage could be detected with a trivial before and after comparison of compiled code.
Given that headers can have order dependency, it is sadly part of a C++ programmer's responsibility to know which do, just as it is their responsibility to know which functions have side-effects, etc. If they are using clang-format, it is then their responsibility to communicate this knowledge to it.
SortIncludes: falseI agree that a formatting tool changing the behavior or performance is a serious issue, but I don't think it's a bug in clang-format in that I suspect it is deliberate design choice, and users can opt out if they want. Maybe the default could be changed or more visible warnings added to the documentation, but the real fix here needs to be in glibc.
I’d be pissed if the issue were introduced by a formatting pass.
Guess I won't be clicking on the link now.
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.
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.
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.
But I -- like yourself -- am much more interested in the applicability of a language in everyday tools, plus in getting the most performance with the least amount of dark magic involved.
BTW, `ripgrep` definitely made me work better and faster.
But they use llvm instead of gcc for c++, and gcc is in average 20% faster than clang. Therefore, rust is 30% slower, at least on heavily optimised programs.
And hyper is not the fastest http server, but the actix one is one of the fastest yes.
That does not show it's 10% slower on average; it shows that C++ is 0.9917938291x as fast as Rust. They both have some where they win by 30%, most are closer, Rust is just faster on average.
> But they use llvm instead of gcc for c++,
C++ g++ g++ (Ubuntu 9.2.1-9ubuntu2) 9.2.1 20191008
?
> gcc is in average 20% faster than clang.
Extremely citation needed.
What kind-of time measurements? What kind-of average?
This chart shows some time measurements:
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
:and the geometric mean is faster for the C++ programs, but the median seems faster for the rust programs.
Statistical artifacts?
I interpreted the parent to mean a simple average, so I did exactly that: calculated the percentage for each, and averaged them. In the colloquial term, "mean".
If that claim was true …
> gcc is in average 20% faster than clang
and if that claim was true …
then we might guess the rust programs average could be 10% faster than the C++ programs average, if both used the same compiler backend
— because those rust programs were compiled with llvm but those c++ programs were compiled with gcc.
Looking at https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
While the worst case is 40% slower (where even C perfored abysmally), most of the time the Rust is within a 10% margin of error, and in quite a few cases it's faster.
Probably the one scenario where it would be far more slower than that would be a heavily AVX-512 intrinsics program because Rust doesn't have those yet (I think), but then that isn't really either language anymore. its intrinsics.
Truthfully, even if Rust can be 2x-5x slower than C++ somewhere, I'll still choose it as my static-and-strongly-typed / compiled-to-machine-code language regardless. Least WTFs per minute is my most important metric.
But I am open to see any and all benchmarks which show both strengths and weaknesses of Rust. So far I sadly haven't seen many of them (but I've been mightily impressed by `actix` in the TechEmpower benchmarks!).
But oh well, most benchmarks aren't pure or non-opinionated so there's that as well.
So far I like Rust quite a lot but -- as I said in another sibling comment -- its procedural style and syntax aren't stellar, in my eyes at least.
Just having some healthy skepticism, apologies if it reads like anything else.
There are also... I don't know how to frame this, social issues? Rust's guarantees often let you do some very aggressive things that you could write in C++, but wouldn't, because it's not maintainable. For example, if you must use reference counting, but don't need threads, Rust has a split between Rc<T> and Arc<T>. You can afford to not use the atomic version in Rust code because if you ever refactor later, you know the compiler will catch this for you, whereas you're just asking for latent, hard to track down bugs if you tried this in C++.
This goes both ways; there is some stuff that C++ is better at than Rust too. It's more complex than "unsafe Rust lets you do anything C++ can do directly and so if it's 100% unsafe in Rust it will be the same speed and if it's safe Rust it will be slower."
Rust can use less ways to do the same thing, I keep hearing from people, and I am hopeful it can be tackled in the future with clever deprecations or simply de facto libraries / ways of doing things.
Thanks for your hard work, it's much appreciated.
If you are looking for performance though, other languages have similar but different pitfalls and bits of esoteric knowledge that you need. Constructs that you should use or avoid, the layout of data in memory, when to run or prevent running of a GC, etc.
For example: Haskell has been trying to bring the performance of C to a functional language for almost 30 years now. While Haskell is a great language with impressive performance for its category, I don’t think anyone believes it renders C/C++ obsolete for scenarios where predictably high performance is crucial.
This is an interesting topic to me, because while I try to find ways to write high-performance code as functionally as possible, I can’t seem to escape the relationship where more procedural-styled code usually yields consistently/predictably higher performance.
Functional (and other paradigms) can sometimes match C’s performance -- but in non-toy scenarios, the “sometimes” clause here compounds its probabilities to ultimately become “virtually never”, as the scope and complexity of a real project grows.
As a result, performance-critical projects written in languages without predictable performance characteristics often evolve into a situation later in development where 90% of your development time is spent poking at 'black boxes' (the compiler optimizer and garbage collector), hoping (sometimes futilely) that you can prod it into spitting out the procedural machine code patterns you already knew you needed anyway — if you’re lucky. And what makes this even worse is that this situation usually arises late enough into development that it's very costly (if not impossible) to backtrack and rewrite everything in a procedural language.
Of course, writing procedurally ends up trading off readability and robustness too human error, vs better performance. I too wish there was a better way to achieve both — I just haven’t found it yet.
So, isn't there a way to emulate FP's `map` mechanics for example, in Rust, without losing performance?
EDIT: To reflect your edits, this is why I want to learn Rust. I am as happy as one can be with Elixir due to Erlang's transparent super-robust and predictable parallel performance; this thing simply does not lag! However, I'd like to be prepared and be able to utilise Rust on the performance hot-spots.
But the scenario you outline, yep, it does seem impossible with a borrow checker.
And don't get me wrong. I am gradually learning Rust and I love it. But I can see myself being a little grumpy with the procedural style and often quirky syntax. Oh well, can't have it all, right?
And, this works in Rust just as it does in C. But at this point, you lose out on the benefits of Rust's static type system and borrow-checker:
1. The compiler will no longer be able to correctness-check the validity of these 'int' style references to other memory.
2. If something does go wrong and you read the array with a bad integer index, Rust will just 'panic' and crash the application. Unlike C, there will be no risk of memory errors or related security vulnerabilities. But on the other hand, each read being bounds-checked will make such Rust code slightly slower than is possible with C/C++. (Though I think you can use 'unsafe' blocks if you want to hyper-optimize akin to C.)
But regarding GC langauges, I generally agree; they're almost always more trouble than they're worth in any performance-sensitive context. You often end up using approaches like this to optimize around the GC (e.g. int indexes into pre-allocated arrays) which ultimately means you're coding C-style in a GC language anyway, which defeats the whole point of GC's productivity-enhancing benefit -- at that point, why not just go all the way and use C or Zig or Rust etc.?
Rust is more mature, well-known, and akin to C++ in its philosophy (big language with powerful features and abstraction capabilities), while Zig[2] is less well-known but IMO a beautifully designed language akin to C in its emphasis on simplicity, while remaining modern in design (e.g. unlike Google Go, which is very simple but intentionally repeats many of C's mistakes[3]).
[1] Such powerful generics usually come with unavoidable explosions in compile time (and sometimes mental complexity for the coder). This is because while it may look like you're simply calling a library function and passing in a reference to your callback function, what it's really doing most of the time (to achieve good performance) is recompiling the entire library from scratch (or nearly so) with your function inlined. Also, the performance characteristics of any given block of code won’t be as obvious and predictable at-a-glance as it would be in a simpler language.
[3] https://www.lucidchart.com/techblog/2015/08/31/the-worst-mis...
I think people don't understand just how badly C++ is broken in reality (vs conceptually) until their paycheck is tied to a real, years-old, multi-developer C++ project. It is not trash talking, it is pointing out truths.
It goes well beyond "any long-lived project has its issues." I think you and I (and many others) know that it is much larger than this, it is a fundamental issue with the language, the standards body surrounding it, and the mess of toolings.
This persists today because C++ is often used to bridge a performance gap between scripted languages and C among younger programmers and academics. (Admit it: we all like that sweet sweet dopamine hit when we take our Python to C++ and the syntax is almost the same.) But that slight performance boost and that "hey this looks like Python but it's really C++" feeling are soon demolished by the accretion of unresolved issues which have enumerated ad-nauseum on HN, including this article.
I've been working with C++ since 1993 (I got a big Borland C++ Compiler as an intern plus 12 VHS tapes of Bjarne himself explaining the language)... my experience with C++ continues right up to today as a contractor having to deal with Arm mbedOS (even Keil struggles to manage hypersensitivity, GNU is a trainwreck for embedded C++) and Tensorflow/OpenCV... and C++ has yet to shake off its flaws. In fact, I think it has added to them exponentially.
> It goes well beyond "any long-lived project has its issues."
I heard this mantra as a justification for bad coding practices likely 500 times.
I appreciate that C++ still drives a lot of our virtual world but that's more a proof of the tenacity of those programs' creators than the virtues of C++ itself. IMO it's time tools like `ripgrep`, `dua` / `ds-cli` (both calculate directory contents' sizes) to become the norm: Rust tools, multicore friendly, insanely fast, and with no quirks and weirdly interacting CLI switches.
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');
}
}
See https://godbolt.org/z/xHYKft
Disclaimer: I haven't actually run this function. That would be too much like work.
The conditional jump remains even with -march=native.
> 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>.
std::transform(buf, buf + size, buf, toupper);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/...
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
size_t is also defined in stddef.h, and including that likely won't cause the same issues.
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.
For something more formal, the official Intel programming manuals describe what each instruction does in painstaking detail.
- Chapter 10, Assembly Language (https://www3.nd.edu/~dthain/compilerbook/compilerbook.pdf#ch...) of http://compilerbook.org/
- intro_x86-64: Introduction to x86_64 assembly - 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/
- Introduction to Computer Organization with x86-64 Assembly Language & GNU/Linux - Robert G. Plantz - 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-progr...
- Understanding Assembly Language - a.k.a. Reverse Engineering for Beginners; https://yurichev.com/blog/UAL/ - https://beginners.re/
- x86-64 Assembly Language Programming with Ubuntu - Ed Jorgensen - http://www.egr.unlv.edu/~ed/x86.html
- Assembly Programming and Computer Architecture for Software Engineers (APCASE) - https://github.com/brianrhall/Assembly - Videos: 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
- Modern x64 Assembly - 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
- Enough x86 Assembly to Be Dangerous - CppCon 2017; Charles Bailey - https://www.youtube.com/watch?v=IfUPkUAEwrk
More:
- Arm / AArch64: https://github.com/MattPD/cpplinks/blob/master/assembly.arm....
- RISC-V: https://github.com/MattPD/cpplinks/blob/master/assembly.risc...
- x86: https://github.com/MattPD/cpplinks/blob/master/assembly.x86....
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.
$ dpkg -S '*/libc.a'
libc6-dev:amd64: /usr/lib/x86_64-linux-gnu/libc.a
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.
That's how I've been told to build fully statically linked rust binaries, I can't say I've dug into why glibc isn't used for those.
You can do a moral version of the same thing using linker scripts, but nobody bothers with linker scripts.
musl, on the other hand, never supports NSS, whether static or dynamic, and exclusively supports DNS. You can't resolve things like mDNS names, or even resolve localhost if on a system that doesn't hardcode it in /etc/hosts.
So either way, static linking and name resolution don't mix well, and musl and non-DNS name resolution don't mix well.