That's an interesting question. One partial answer is that the hash table speedup likely involves an interface change, replacing "insert single item" with batching. This is a generally helpful principle, but unfortunately does not match some existing abstractions.
I assumed I must be doing something wrong. Eventually took a look and found the SGI rope library constructs a tree where each heap allocated leaf node only contains a single character from the document. No wonder its so inefficient. I'm somewhat horrified by the idea that anyone is using that implementation in their software.
Sometimes I think about how much money people would pay to make their computer run 20x faster. Our society spends a truckload of money on computing hardware - but most of that hardware is wasted running wildly inefficient programs. Modern computers should do basically everything instantly. Its weird to me that we'll pay thousands of dollars for faster CPUs then write new software in python, electron or a docker container running in a VM.
I think people who can reliably do this are paid $250-750k/year at top paying companies.
Much of this optimization work requires specific knowledge of the details of the operating environment (e.g. Linux) and silicon microarchitecture (e.g. AVX-512), which can be poorly documented. You have to be comfortable doing experiments and digging into system arcana to surface properties of the system that you can't trivially google. While algorithm selection is important, doing that well is table stakes and part of the role is knowing when and why an "optimal" algorithm is worse than e.g. selectively applied brute-force.
Computational efficiency and throughput is worth a lot of money at scale but most of it is designed and implemented at the scale of a single machine. Every software engineer owns the tools required to become proficient at this. It is genuinely a rare skill even among systems programmers and is a good way to separate yourself from the crowd.
I also like the talk by Nicholas Ormrod “The strange details of std::string at Facebook":
A closely related area is slightly bending the scaling linearity curve on e.g. big multi-core servers or scale-out systems, so that it is possible to efficiently throw hardware at problems. However, this operates from a pretty different set of theoretical principles than classic performance optimization.
Two domains that have an almost unlimited appetite for improved performance and efficiency right now due to current bottlenecks are AI and sensor processing.
Bottlenecks that can make a computer 20x faster are very rare. First, pay $1m for a specialist to find the bottlenecks. However, it is even rarer that it is a bottleneck of the entire service. Rather, it is more likely to be an accidental drop in performance. Thus, basically performance monitoring is the best use of money.
> Its weird to me that we'll pay thousands of dollars for faster CPUs then write new software in python, electron or a docker container running in a VM.
There are more labor costs and lost commercial opportunities due to delays in development.
This kind of guarantees that custom code, written competently, will always be able to outpace standard library code. The standard library is one of the few things that probably always needs to handle the general case.
Python has a REPL, Duck typing and hooks for many libraries including gui libraries.
Electron is basically a browser you can program via JavaScript with everything you'll ever need to make a gui application.
They both make a lot of sense when you consider the alternatives. However, I do wonder why there isn't yet an option to AOT compile python and electron projects into fast executables.
> then write new software in ... electron
And about Python: Almost no one is doing CPU intensive work in pure Python. They are using C-language extensions like Pandas, NumPy, etc.
But the software runs on the computers of all of their users. How much money do their users' computers cost? If you have just 10k users, probably $10M or so? But software companies don't pay for my computer's resources. The money I need to spend on computer hardware isn't priced in to your calculus at all. They don't care.
I find it pretty frustrating and sad.
I've always understood stl to prefer rock solid safety+stability+compatibility (+ a bit of dogfooding) with the widest applicable domain (scale etc) over pure, unadulterated performance, but I haven't coded in c++ since college so I know nothing
Some parts of the standard library like std::vector is already good enough. Other parts like std::unordered_set are rarely used in industry unless low-dependency is a requirent.
There are some niches where exceptions are frowned upon, but those are small.
But most people using it in industry fall into two camps:
1. using it because the project is old enough that C++ was a reasonable default when the project started. You may also be right here
2. using it because performance is absolutely critical to the application, here I would actually imagine you're wrong. noexcept removes a ton of stack-unwinding code, and you can absolutely get a significant performance boost out of it. It would be weird if they didn't pull this lever, given the perf boost and that errors as values is also a fairly reasonable way to handle problem
In the second category, google famously had a "no exceptions" rule at one point (could still be in effect, I have no knowlegde of google)
Ref: https://google.github.io/styleguide/cppguide.html#Exceptions
> Because most existing C++ code at Google is not prepared to deal with exceptions, it is comparatively difficult to adopt new code that generates exceptions.
I'd imagine when people say "not using exceptions", it is about using compiler flags to completely disable the exception mechanisms from the language. And this also invalidates many of the design patterns C++ is known and sometimes praised for, at least RAII and operator overloading.
Basically they've overspecified their datastructures and we're now paying the price
Just because Hyrum's Law applies to an implementation of the standard doesn't mean that you should pessimise your implementation. You should actively hurt those who rely on implementation quirks
Of course, the detail is in trying it out, intuition does not always capture hardware behavior. I remember looking at this many years ago and B-trees were considerably faster. The code was far from being optimal though. Maybe if one pulls all tricks in the book the additional complexity of managing multiple comparisons will outweigh saving from reducing loads.
For a perfect drop-in replacement of std::lower_bound, the best you can do without breaking anything is to make the search branchless and maybe add some prefetching [1]. Some compilers actually try to implement std::lower_bound this way, but these things can sometimes break from version to version because there are no semantics to reliably make compiler use predication instead of branching.
Your intuitions are very much correct: you can get rid of pointers in a B-tree and make it static and implicit and fast, especially if you use SIMD to search for the lower bound within a node [2], but it would technically not be a replacement to std::lower_bound as we need to build an additional structure (even though it's very hard to imagine a scenario where you obtain a sorted array but can’t afford to spend linear time on preprocessing). C++23 has since added std::flat_set, which seems to be an appropriate place to implement it (in the article I compared against std::lower_bound because neither I nor the vast majority of the readers knew what std::flat_set was).
You can also add pointers back to support insertion and deletion with a moderate penalty to performance [3], but this dynamic B-tree is also technically not a replacement to std::set because of the extra pointer invalidations when a node merges or splits (even though in most cases you don't need pointer stability). You can fix it by, e.g., storing separate pairs of pointers so that each iterator knows where its key is in the tree and vice versa. That would add some overhead (especially in terms of memory) but make it compliant with the standard and still quite a bit faster and lighter than std::set.
The three articles combined are like 50 pages long so for a tl;dr version you might be interested in a talk I did at CppCon [4]. You can also extend the trick for heaps, ropes, segment trees, and other tree-like structures. There is a lot of work to be done here.
[1] https://en.algorithmica.org/hpc/data-structures/binary-searc... [2] https://en.algorithmica.org/hpc/data-structures/s-tree/ [3] https://en.algorithmica.org/hpc/data-structures/b-tree/ [4] https://www.youtube.com/watch?v=1RIPMQQRBWk
> For a perfect drop-in replacement of std::lower_bound, the best you can do without breaking anything is to make the search branchless and maybe add some prefetching [1]. Some compilers actually try to implement std::lower_bound this way, but these things can sometimes break from version to version because there are no semantics to reliably make compiler use predication instead of branching.
What's imperfect about a radix-4 (or higher) search instead of a binary search for replacing std::lower_bound? For a radix-k search, you'll have k-1 fetches in flight before you decide which subarray to recurse on, and your dep chain will be log_2(k) times shorter.
(You can prefetch k layers ahead for radix-2^k search, but searching in small arrays will become more expensive this way.)
I didn't benchmark it, but I guess on mid-to-large arrays it would actually work somewhat slower than prefetching because it is more instruction-heavy, and, more importantly, prefetches are "cancelable": if the memory bus is too busy with actual requests, they will be skipped, while in explicit radix-k search you would have to wait for all (k-1) elements even if the middle element happened to be already cached and you already know which elements you need next.
That said, it could probably work with small arrays where caching is not a concern and especially if you optimize for latency and not throughput. You can also try to do the comparisons with SIMD (Wojciech Mula tried something similar and got a small boost: http://0x80.pl/articles/simd-search.html).
In my opinion, the main challenges are:
1. Lack of suitably narrow abstractions. E.g., my "binary search" implementation requires building a small static structure (6-7% of the original array size), and although it is extremely hard to imagine a practical use case where you get a sorted array but can't spend linear time on its preprocessing, it's technically not a drop-in replacement for std::lower_bound.
2. Backwards compatibility. E.g., std::set has a requirement that a node deletion should not invalidate other iterators, which makes it harder to implement it as a B-tree, which has to move a lot of keys around after a node merge/split.
3. Performance regressions. Sometimes a change can make a program 2x faster in most use cases but 1.5x slower in some specific one. If the hardware handling that use case was already at 90% capacity, it will now start to fail after the upgrade, while a 2x improvement on other use cases is just "nice" and doesn't offset it.
4. Vagueness of "better". There are about 10 blog posts on the internet now claiming they have designed the fastest hash table in the world—and every one of them is right because they are using different benchmarks tailored to their specific data set and their specific hardware.
5. Desire to implement things more generically in the middle-end of a compiler instead of the standard library, which is much harder to do. You don't want to hand code the optimal SIMD procedure for calculating the sum of an array for each CPU microarchitecture; you want the compiler to do it automatically for everything that resembles a simple "for" loop. This also leads to a diffusion of responsibility, with compiler people and library maintainers arguing over the appropriate place for an optimization to be implemented.
6. Lack of incentives. Most people who can implement these optimizations work for big tech and would look better in their performance review by contributing to their employer's library (e.g., Abseil for Google, Folly for Meta), or at least to a library with a less Kafkaesque review process like Boost, rather than the standard library.
7. Things still being in the research stage. For example, I recently discovered (but haven't published yet) a new GCD algorithm that seems to yield another ~2x improvement over binary GCD (~4x over std::gcd), and so the guy who recently pushed it in libc++ has in a certain sense wasted work.
I haven't rerun benchmarks myself, but I believe some relatively decoupled parts of the STL have actually since been upgraded in some compilers (std::lower_bound is now branchless, std::gcd now uses binary GCD, std::accumulate and similar reductions now use instruction-level parallelism when they see it) although in all these cases I didn't discover but at most only popularized them.
Great job on this book. Lots of great content that can be used as reference.
That is, The style is very kitchen-sink and generalized, which means implementers have little flexibility.
Every “real” C++ codebase I’ve worked on has its own data structures for most things. And that’s a feature of C++, not a bug.
For example, don’t use std::unordered_map for anything performance sensitive. It’s a shockingly slow hash table because the interface constrains it to allocate a lot.
The STL isn’t designed for optimum performance. It’s easy to do better by satisfying your app’s requirements and nothing else.
* prefetch + cmov. These should be part of the STL but languages and compilers struggle to emit the cmov properly (Rust’s been broken for 6 years: https://github.com/rust-lang/rust/issues/53823). Prefetch is an interesting one because while you do optimize the binary search in a micro benchmark, you’re potentially putting extra pressure on the cache with “garbage” data which means it’s a greedy optimization that might hurt surrounding code. Probably should have separate implementations as binary search isn’t necessarily always in the hot path.
* Eytzinger layout has additional limitations that are often not discussed when pointing out “hey this is faster”. Adding elements is non-trivial since you first have to add + sort (as you would for binary search) and then rebuild a new parallel eytzinger layout from scratch (i.e. you’d have it be an index of pointers rather than the values themselves which adds memory overhead + indirection for the comparisons). You can’t find the “insertion” position for non-existent elements which means it can’t be used for std::lower_bound (i.e. if the element doesn’t exist, you just get None back instead of Err(position where it can be slotted in to maintain order).
Basically, optimizations can sometimes rely on changing the problem domain so that you can trade off features of the algorithm against the runtime. These kinds of algorithms can be a bad fit for a standard library which aims to be a toolbox of “good enough” algorithms and data structures for problems that appear very very frequently. Or they could be part of the standard library toolkit just under a different name but you also have to balance that against maintenance concerns.
Because it seems “obvious” to enable programs that don’t depend on the over-constraining parts of things like std::unordered_map, to specialize the implementation they’re using so that it doesn’t employ the overhead-laden parts required to make those uncalled methods function. And “just have two copies of the code and pick between them based on control-flow info” seems like a very trivial way to do it for at least some low-hanging-fruit cases.
<< Among the cool things that we will speed up:
>>If true, why haven't these appeared in the C++ STL?
EDIT: Formatting only