C++ Headers are Expensive
virtuallyrandom.com
virtuallyrandom.com
/*
* The point of this file is to contain all the LLVM C++ API interaction so that:
* 1. The compile time of other files is kept under control.
* 2. Provide a C interface to the LLVM functions we need for self-hosting purposes.
* 3. Prevent C++ from infecting the rest of the project.
*/
// copied from include/llvm/ADT/Triple.h
enum ZigLLVM_ArchType {
ZigLLVM_UnknownArch,
ZigLLVM_arm, // ARM (little endian): arm, armv.*, xscale
ZigLLVM_armeb, // ARM (big endian): armeb
ZigLLVM_aarch64, // AArch64 (little endian): aarch64
...
static_assert((Triple::ArchType)ZigLLVM_UnknownArch == Triple::UnknownArch, "");
static_assert((Triple::ArchType)ZigLLVM_arm == Triple::arm, "");
static_assert((Triple::ArchType)ZigLLVM_armeb == Triple::armeb, "");
static_assert((Triple::ArchType)ZigLLVM_aarch64 == Triple::aarch64, "");
static_assert((Triple::ArchType)ZigLLVM_aarch64_be == Triple::aarch64_be, "");
static_assert((Triple::ArchType)ZigLLVM_arc == Triple::arc, "");
...
The file that has to use C++ headers takes about 3x as long to compile than Zig's ir.cpp file which is nearing 30,000 lines of code, but only depends on C-style header files.
The compiler firewall strategy works fairly well in C++11 and even better in C++14. Create a public interface with minimal dependencies, and encapsulate the details for this interface in a pImpl (pointer to implementation). The latter can be defined in implementation source files, and it can use unique_ptr for simple resource management. C++14 added the missing make_unique, which eases the pImpl pattern.
That being said, compile times in C++ are going to typically be terrible if you are used to compiling in C, Go, and other languages known for fast compilation times. A build system with accurate dependency tracking and on-demand compilation (e.g. a directory watcher or, if you prefer IDEs, continuous compilation in the background) will eliminate a lot of this pain.
Does a client of the framework you are writing -- which is probably using STL internally -- need a single instruction operation for adding a value for a call that you make less than 0.001% of the time?
Optimization is about end results. Apply the Pareto Principle, and don't forget that your users also need to compile your code in a reasonable amount of time.
Premature optimization is not really a thing but foreclosing future avenues of optimization definitely can be.
Okay. I'm going to stop this thread right there and take some opportunity to provide some mentoring. I hope you accept this, as it will help in your career.
Read this paper. It is a classic.
No one is claiming that we should ignore performance all together. But, understanding through profiling where performance issues are and designing toward a faster implementation is more important than trying to inline definitions up front.
Some implementation details are so well understood that you really don't need a profiler to do what is probably the right thing by default.
No, but neither do I pass types that fit in a native integer by const reference because copies should be avoided at all costs. There is always a tradeoff.
> Some implementation details are so well understood that you really don't need a profiler to do what is probably the right thing by default.
Avoiding any and all indirection at all costs is not one of these.
The pImpl pattern, much like virtual methods, function pointers, etc., are each tools. Indirection is a trade-off that is either worth the expense in cache misses or is not. The cost is not so cut and dried as others in the thread have assumed.
"Any and all"? Perhaps not. However, I believe the context here was standard library headers. Those are full of small, often-used functions, so avoiding idioms based on indirection such as pImpl is about as close to a black and white rule as you're ever going to find in the programming world.
The article may have discussed standard headers, but it was neither titled to indicate that it was talking about only standard headers, nor are the problems it discussed localized only to standard headers. My original comment did not limit the discussion to only standard headers.
As always the answer is... it depends. Programmer time costs money, CPU time is cheap by comparison.
If you're building something that runs occasionally, or is IO/UI/network bound... CPU time is largely irrelevant. But if you're building something that runs in a tight loop or a library that will be compiled in millions of lines of code, then the wasted programmer time will absolutely be worth the ROI.
It is not always possible to just throw more hardware at the problem of compilation. For instance, one may be using a build pipeline that requires specific steps to be followed as part of gating tasks. The time it takes to compile code over and over again for unit testing, behavioral testing, acceptance testing, integration testing, etc., each impacts delivery time and handoff.
Earlier in my career, I worked with a code base that was approximately 10 million lines of code in size. Compiling this code base would take approximately 7 hours on the best hardware we could buy. The C++ developers were adamant about ensuring that their headers were "complete" as they called it. With a few changes, such as forward declarations, abstract interfaces, and encapsulation, my team was able to reduce that compile time to less than 35 minutes. Based on profile feedback, we saw less than a quarter of a percent difference in overhead. Productivity-wise, we managed to reduce developer workflows so significantly that it was a better use of our time for overall cost than working on a billable project.
Most projects aren't nearly that bad, but it does go to show that it is possible to significantly reduce compilation time without significantly impacting runtime performance, even in C++.
All of that is solved by throwing more hardware at it.
Alternatively if compile time is not the slow part of that pipeline, then you're prematurely optimizing the wrong thing anyway.
> Earlier in my career, I worked with a code base that was approximately 10 million lines of code in size. Compiling this code base would take approximately 7 hours on the best hardware we could buy. The C++ developers were adamant about ensuring that their headers were "complete" as they called it. With a few changes, such as forward declarations, abstract interfaces, and encapsulation, my team was able to reduce that compile time to less than 35 minutes.
In other words you only optimized the critical 3% of the codebase rather than prematurely optimizing everything with pImpl abstractions?
Developer productivity does not matter in your world?
> In other words you only optimized the critical 3% of the codebase rather than prematurely optimizing everything with pImpl abstractions?
Yes, because nowhere in this thread have I advocated prematurely optimizing everything with pImpl abstractions. Those are words you have put in my mouth. pImpl abstraction is a single tool that can be used to improve compile-time performance. Not all the time, but in a fraction of the 3% of the time where it is appropriate.
Understanding what you are optimizing FOR and where the most attention should be spent is the crux of Knuth's argument. Trying to be clever up-front is often counter-productive.
There is nothing wrong with making some architectural decisions up front, but that is much different than avoiding pImpls at all costs because indirection is slower. Indirection doesn't always matter, and it should only be tackled when and where it does.
However, if compilation times have gotten painful enough that we need to examine performance improvements to our headers, the pImpl pattern is one of many tools in the toolbox. So are forward headers and other compiler firewall techniques.
HTH
Given that it makes every object instantiation perform a memory allocation, followed by required indirection to accesss it, and will also prevent the creation of default copy constructor and assignment operator etc. due to use of unique_ptr, it adds complexity as well as two sources of performance loss.
As a result, I would use this pattern only where strictly necessary. For example, I've used it when wrapping C libraries with C++ classes. It means the C headers aren't included in the public C++ headers, only the implementation, making the implementation cleaner. Or I might use it in situations where private members drag in dozens of headers which expose a lot of unnecessary implementation details to the user, which might drag in transitive library dependencies simply by #including the headers. The fact that the compilation speed might be marginally faster is incidental to this.
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3 %. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified"
We know that cache misses are not a small in-efficiency. This has been measured & observed on many real systems as a real, systemic problem. It's why data-oriented design is currently the King of game engine world, because cache misses kill performance. It is not premature to warn against it as a general practice as a result, as that's systemic de-optimization that will likely impact the critical 3%.
I was told that "premature optimization is not really a thing" as a response to a reply I received that pImpls should be avoided at all costs.
When we analyze the performance impact of software, we don't shotgun change things because of a generalized fear of cache misses. We examine critical code paths and make changes there based on profile feedback. That is the spirit of what Knuth is saying in this quote. Look carefully at critical code, BUT ONLY AFTER that code has been identified.
A cache miss is critical when it is in a critical path. So, we write interfaces with this in mind. Compilation time matters, as does runtime performance. Either way, we identify performance bottlenecks as they come up and we optimize them. Avoiding clearer coding style, such as encapsulation, because it MIGHT create faster code, is counter-productive.
We can apply the Pareto Principle to understand that 80% of the performance overhead can be found in 20% of the code. The remaining 80% of the code can use pImpls or could be rewritten in Haskell for all it matters for performance. But, that code still needs to be compiled, and often by clients who only have headers and library files. Subjecting them to long compiles to gain an unimportant improvement in performance in code that only rarely gets called is a bad trade. Spend that time optimizing the parts of the code that matter, which, as Knuth says, should only be done after this code has been identified.
EDIT: the downvoting on this comment is amusing, given that "avoid pImpls" is exactly the sort of 97% cruft that Knuth was addressing.
Again, no, it isn't. You seem to be severely underestimating the systemic impact of cache misses if you are considering them a "small" impact to efficiency.
It's a well-proven, well-known problem. Ignoring it falls under Knuth's guidance of "A good programmer will not be lulled into complacency by such reasoning."
pImpls are the sort of thing you use at API boundaries to avoid leaking implementation details into users, but that's trading efficiency & complexity for a more stable API boundary. Scattering them throughout your code base would be like compiling with -O0. It's a silly, nonsensical waste of a user's constrained resources for a slight gain at compile time at a cost of code complexity.
Or, alternatively, using pImpls to optimize for compile time is a premature optimization. You should only optimize for compile time at most 3% of your source files, ever. The other 97% of your source files should be written for clarity & simplicity, which means no pImpls.
You are severely overestimating the impact of cache misses if you think that all indirection must be eliminated and any use of pImpls at all is always wrong, as you seem to be implying.
> pImpls are the sort of thing you use at API boundaries to avoid leaking implementation details into users, but that's trading efficiency & complexity for a more stable API boundary. Scattering them throughout your code base would be like compiling with -O0.
It's a good thing that I never advocated using them everywhere then. Where did you read me saying this?
> Or, alternatively, using pImpls to optimize for compile time is a premature optimization.
Only if this is done by default, which I have not advocated for anywhere in this thread. I called it a tool in the toolbox. I mentioned it as one of several possibilities. Somehow you have translated this into "use pImpls everywhere", which is a strawman.
This pendulum swings back and forth, and we went from "every bit counts" madness of the early days, to the polar opposite of "just burn cycles, whatever".
Systems where every interaction feels sluggish are a pain to use, and often nearly impossible to refactor for better performance.
That extra indirection often means a cache miss. That isn’t cheap. Accessing each item traversed through a pointer can easily halve program speed.
Java tries hard to prevent the indirections (local objects may live in the stack, their memory layout need not follow what the source code say, objects may even only exist in cpu registers)
:-(
There are still more platforms with a C++ compiler available than Ada, Java or C# ones, let alone Go, D, Rust, Swift.
So if the goal is to make the code available to all platforms, without having to deal with C's lack of safety, then C++ it is.
It's also not infallible and you might find it difficult to track a regression if introduced by someone silently breaking a heurestic in the optimiser.
However with VC++ it doesn't seem to be that bad, when incremental compilation and linking are enabled.
[0] https://docs.microsoft.com/en-us/cpp/build/reference/ltcg-li...
That's what happens when I spend most the time on JVM/.NET worlds. :)
It's a tradeoff between compile time and complexity.
Edit: Something like https://github.com/beached/stack_pimpl
Was it just a oversimplistic example and the benefit is actually if priv_t has a bunch of internal methods that you want to keep out of the stack_pimpl.h interface?
So with that, it keeps the data(state) in the public facing class. This allows one to keep everythign stack allocated instead of defaulting to the heap. So for something this is created en mass(A vector of them) or created and destroyed often, this is a runtime win.
What it does is have a proxy that mirrors the public interface that is passed the this pointer. That proxy a friend class. Because only the proxies header(in this case private.h which I should probably rename firewalled.h) has static members that mirror the public members on the public class that limits the interaction between your classes users and it's implementation, as it is also with unique_ptr(or whatever pointer/heap way) based PIMPL designs. So changes in private.cpp that does all the work are only reflected in that one file. This file also brings in the heavy templates or algorithm code that may have large compile times.
However...
> So with taht, it keeps the data(stat) in the public facing class. This allows one to keep everything stack allocated instaed of defaulting to the heap.
Ok, having it on the stack is useful, but in my personal experience, the state is exactly the thing that I find changes the most (typically together with the code), so by keeping the state in the public header, changes will still require recompiliation of anything that includes the header, so I’m not sure this really wins much (at least, based on my own C++ projects).
Large-Scale C++ Software Design[0]
The techniques set forth therein are founded in real-world experience and can significantly address large-scale system build times. Granted, the book is dated and likely not entirely applicable to modern C++, yet remains the best resource regarding insulating modules/subsystems and optimizing compilation times IMHO.
0 - https://www.pearson.com/us/higher-education/program/Lakos-La...
Recently, after a ten year absence of not using ccache, I was playing with it again.
The speed-up from ccache you obtain today is quite a bit more more than a decade ago; I was amazed.
ccache does not cache the result of preprocessing. Each time you build an object, ccache passes it through the preprocessor to obtain the token-level translation unit which is then hashed to see if there is a hit (ready made .o file can be retrieved) or miss (preprocessed translation unit can be compiled).
There is now more than a 10 fold difference between preprocessing, hashing and retrieving a .o file from the cache, versus doing the compile job. I just did a timing on one program: 750 milliseconds to rebuild with ccache (so everything is preprocessed and ready-made .o files are pulled out and linked). Without ccache 18.2 seconds. 24X difference! So approximately speaking, preprocessing is less than 1/24th of the cost.
Ancient wisdom about C used to be that more than 50% of the compilation time is spent on preprocessing. That's the environment from which came the motivations for devices like precompiled headers, #pragma once and having compilers recognize the #ifndef HEADER_H trick to avoid reading files.
Nowadays, those things hardly matter.
Nowdays when you're building code, the rate at which .o's "pop out" of the build subjectively appears no faster than two decades ago, even though the memories, L1 and L2 cache sizes, CPU clock speeds, and disk spaces are vastly greater. Since not a lot of development has gone into preprocessing, it has more or less sped up with the hardware, but overall compilation hasn't.
Some of that compilation laggardness is probably due to the fact that some of the algorithms have tough asymptotic complexity. Just extending the scope of some of the algorithms to do a bit of better job causes the time to rise dramatically. However, even compiling with -O0 (optimization off), though faster, is still shockingly slow, given the hardware. If I build that 18.2 second program with -O2, it still takes 6 seconds: an 8X difference compared to preprocessing and linking cached .o files in 750 ms. A far cry from the ancient wisdom that character and token level processing of the source dominates the compile time.
Ancient wisdom was that more than 50% of the time is spent compiling the headers, after they become a part of your translation unit after preprocessing. I don't see why preprocessing itself would ever be singled out, given that it's comparatively much simpler than actual compilation.
Only if you explicitly disable 'direct mode'.
In my opinion, this makes any conclusion dubious. If you really care about compile times in C++, step 0 is to make sure you have an adequate machine (at least quadcore CPU/ lot of RAM/SSD). If the choice is between spending programmer time trying to optimize compile times, versus spending a couple hundred dollars for an SSD, 99% of the time, spending money on an SSD will be the correct solution.
Presumably, 127/128 runs have both the test file and the single header file in memory cache, so the distinction is moot.
Also, I find the conclusion that we should all just buy top end machines and ignore performance problems that don't manifest there fairly unconvincing. I think that kind of thinking is responsible for a good chunk of the reason the web is so bloated today. :-)
You don't need to develop on a $200 notebook to care about performance.
For any kind of even vaguely profitable software, your developers should all have kick arse machines.
But they should test on a $200 laptop :)
Note that Visual Studio, for example, does a poor job of this because it only spawns one compilation per CPU thread. This results in individual threads being idle more than they ought to be.
I've just tested one of my ~300 KLOC C++ projects, broken into 479 .cpp files and 583 .h files.
Using Linux (GCC) after dropping the disk cache, on a 5400 RPM HD, the full build on 14 threads took: 78 seconds.
On a fast SSD (same machine, after dropping caches again) it took 61 seconds.
Linking was ~7 seconds faster on the SSD, so arguably you could say that actual compilation wasn't the same ratio as fast, but overall build time is most definitely faster.
Source was on the same drive as the build target directory.
At a previous company I worked at, we got SSDs to speed up compilation (and it did).
If it doesn't make a difference, all that means is that your project is small, or doesn't have too many dependencies. Good for you. But that's not the reality for all projects.
I've seen this problem a few times, someone looks at their N core machine with M GB and says, oh look i'm only using 3/4 of M so when I buy the 4xN cores machine I'm going to put M ram in it again. Then everything runs poorly because the disks are getting hammered now that there are another 32 jobs (or whatever) each consuming a GB. Keep adding ram until their is still free RAM during the build. Its going to run faster from ram that waiting for a super speedy disk to read the next c/.o/etc file.
We'll have them Soon™.
It probably partially depends on whether old-style headers can be used simultaneously with new-style modules.
The drawback is that sources from the jumbo can not be compiled in parallel. So if one has access to extremely parallel compilation farm, like developers at Google, it will slow down things.
[1] https://api.unrealengine.com/INT/Programming/UnrealBuildSyst...
Generally the way this works is rather than compiling into one jumbo file, you combine into multiple files, and you can then compile them in parallel. UE4 supports it (disclosure, I work for them). and it works by including 20 files at a time, and compiling the larger files normally.
There is also a productivity slow down where a change to any of those files causes the all the other files to be recompiled, so you can remove those files from the individual file.
> The compilation time saving can be up to factor of 2 or more on a laptop.
The compilation time savings are orders of magnitude in my experience, even on a high end desktop. That's for a full build. For an incremental, there is a penalty (see above for workarounds)
Compilation at the time took over 2 hours.
At some point I wrote a macro that replaced all those automatically generated const uints with #defines, and that cut compilation time to half an hour. It was quickly declared the biggest productivity boost by the project lead.
Precompiled headers are a pretty ugly solution and the way they've been implemented in the past could be really nasty. (IIRC in old GCC versions it would copy some internal state to disk, then later load it from disk and manually adjust pointers!)
$ for i in `seq 3`; do gcc-6 -x c-header /dev/null -o x.h.gch; sha256sum x.h.gch; done
98d8093503565836ba6f35b7adf90330d63d9d1c76dfb8e3ad1aeb2d933d1a45 x.h.gch
17e5de099860d94aaa468c5ad103b3f0dd5e663f6cdbd01b4f12cf210023e71c x.h.gch
3cc2f1c0a517b5fedbbd49bb3a34084d9aa1428f33f3c30278a8c61f9ed9ba88 x.h.gchBasically, instead of defining a real serialization format (and thus having to write serializer/deserializer code), it's way easier to just `fwrite` out your internal structs to disk, one after another, and write some much simpler walker code to walk through any pointed fields appropriately. At some point though this becomes technical debt which needs to be repaid in the form of a total serialization rewrite.
Blender, the popular open-source 3D modelling tool, uses a format like this for their .blend files, and it is really gross. IIRC a few releases back they started working to improve the format to be a little less dependent on low-level internal details, but now they have the nightmare of backwards compatibility to deal with.
The basic problem is that C/C++ have no mechanism for native serialization, unlike e.g. Java, Python, or any number of other languages, so you're either stuck `fwrite`ing structs or reinventing the wheel.
But your basically right, everyone ends up doing it their own way which just ends up being a PITA.
They force programmers to tell the compiler what intermediate result to cache. Finding the best intermediate result to cache is a black art, and that set will change when your source code grows, forcing you to either accept that your precompiled headers may not help that much, or to spend large amounts of time optimizing build times.
Simply put - if it's #include <...>, it goes into the precompiled header. Otherwise, it goes directly into the source.
The downside of this is that every time you add a new dependency, the entire project is rebuilt, since the change in your precompiled header affects all translation units. But adding dependencies is rare, and changing code and rebuilding is far more common.
Yes, I was measuring time to rebuild everything (including the PCH) from scratch. So it's probable that incremental compilation is slightly faster using PCH, it's just not nearly as much as I was hoping for.