51 replies
3d13h
This is a wild quote:
<< Among the cool things that we will speed up:
2x faster GCD (compared to std::gcd)
8-15x faster binary search (compared to std::lower_bound)
5-10x faster segment trees (compared to Fenwick trees)
5x faster hash tables (compared to std::unordered_map)
2x faster popcount (compared to repeatedly calling popcnt)
35x faster parsing series of integers (compared to scanf)
?x faster sorting (compared to std::sort)
2x faster sum (compared to std::accumulate)
2-3x faster prefix sum (compared to naive implementation)
10x faster argmin (compared to naive implementation)
10x faster array searching (compared to std::find)
15x faster search tree (compared to std::set)
100x faster matrix multiplication (compared to “for-for-for”)
optimal word-size integer factorization (~0.4ms per 60-bit integer)
optimal Karatsuba Algorithm
optimal FFTIf true, why haven't these appeared in the C++ STL?
EDIT: Formatting only
About a decade ago I wrote a fast rope library in C, with support for arbitrary inserts & deletes at arbitrary locations in large strings. I benchmarked it, and I was shocked to discover that my library was ~20x faster than the SGI C++ rope library that shipped with my compiler.
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.
I think there are almost 0 positions in industry for this sort of thing.
There are plenty, actually. Source: did this professionally for a bit
I'm interested to hear more. What kind of companies pay for this? Hardware companies like Intel and Nvidia? What are the roles called?
There are several branches, but all of them typically run at a scale where performance costs them money. People with large server deployments (any "hyperscale" company) hire these people to save millions of dollars a year. People who do client performance attract and retain users. Those who do trading bank on being the fastest. And many other areas; these are just the big ones.
Interesting. Does it need a PHD or a specific Master? Because I feel no one needs that kind of performance at home so the only place to train is academy or industry while industry usually does not train a junior on that topic.
No. Usually you learn this stuff by doing it at a smaller scale elsewhere.
This type of optimization isn't something you typically study as an academic. Everyone I know that does this kind of work (these jobs definitely exist) was self-taught by experimenting in their own time because they had a passion for performance optimization. It is a rewarding specialization in that there is a quasi-objective measure of incremental progress.
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 just became an AVX2 programmer for fun. You can too, if you go to the highload.fun group chat then I or someone else will suggest blazing fast ideas for every problem that happen to be about half as fast as our own approaches.
Algotrading companies.
The FAANGS certainly have people doing this kind of work. For example, Andrei Alexandrescu has a bunch of keynote talks at CPPCon where he talks about 1-4% speed optimisations he makes to the std library at Facebook.
https://youtu.be/FJJTYQYB1JQ
I also like the talk by Nicholas Ormrod “The strange details of std::string at Facebook":
https://youtu.be/kPR8h4-qZdk
Various types of hyper-scale or high-performance computing where incremental improvements in throughput, efficiency, latency, and resource utilization saves millions of dollars. Hardware companies are not where you go for this, though they do offer some limited micro-optimization support for the companies that do care about this kind of thing. You want to focus on companies that spend enormous amounts of money on compute infrastructure. The appetite to invest in compute efficiency waxes and wanes with the economy. If companies can get away with throwing money at a problem they will, but that can quickly become untenable.
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.
I'm certainly intrigued and I'll shoot you an email.
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.
And about Python: Almost no one is doing CPU intensive work in pure Python. They are using C-language extensions like Pandas, NumPy, etc.
the semantics make aot compiling based speedup basically impossible. Python is just way too dynamic to do anything with. If you need speed and nice language features, you're much better off using a high level language that has better semantics for speed. Julia is my preferred option, but Lua and a few others fit this niche well.
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.
There are more labor costs and lost commercial opportunities due to delays in development.
It should also be noted that you can also get a significant speed up by writing situation specific code, instead of handling the general case, if your problem allows it.
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.
Isn't stl notoriously slow relative to most c++ implementations given equivalent functionality?
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
The standard library has a bunch of requirements that a random third party library likely does not have. Like ABI compatibility (most people recompile from source often so it isn't needed). Like exception safety (most people turn off exceptions anyways so they don't need such safety).
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.
I very much doubt most people coding in C++ would turn off exceptions. Virtually every new runtime construct being added is designed for exceptions.
There are some niches where exceptions are frowned upon, but those are small.
Define most here a little bit more. I would imaging most people using it are hobbyists/students and, in that case, I think you're right.
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)
I see noexcept as a part of the language that works together with exceptions, it is a valid optimization for certain (typically small) pieces of a code base that otherwise uses 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.
They do have that rule, but not for performance reasons. The full decision is here https://google.github.io/styleguide/cppguide.html#Exceptions and probably worth a read but the two main take away I think is:
The latest version the Google C++ Style Guide of says: "We do not use C++ exceptions."
Ref: https://google.github.io/styleguide/cppguide.html#Exceptions
Unfortunately a significant portion of feedback for the C++ standard library comes from Google LLC
ABI compatibility is needed in 99% of the cases since you basically never compile your own STL. You dynamically (or statically if you will) link against the one you have on a system since most software does not have a control over the machines/environment where it's going to be deployed. Even in cases where you do have a control over your environment deployment, compiling your own libc++/libstdc++ is a complication which you usually want to avoid.
The C++ standard library is about 90% template code in headers. Yes, you compile it all the time, in your own environment. You have no choice.
The fact that you will use a class or function template from STL, and compile it, doesn't change the fact that, regardless of that, you will have to link against the libstdc++ or libc++ which you didn't compile yourself. I am not sure I understand the argument you're trying to make.
One also needs to look at the context of these quotes. For example, for the binary search they change the array layout to improve cache locality. This is not really helpful if you have to work with sorted arrays (as many binary search algorithms do). If instead you have the freedom to optimize the data structure itself (and you do the search often enough to amortize the construction), you might as well build some variant of a B-tree which is going to be much faster than binary search anyway.
I'd like to see a benchmark showing a B-tree beating an array with the correct layout. I think you only want a tree if you also want to update the array.
You can implement your B-tree as an array if that's what you like. The advantage of the B-tree-like-layouts is that you need fewer indirections. With binary search you do one node jump per comparison. With a B-tree you do one jump per N comparisons.
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.
Author here.
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
First, what a great resource you've put together! You're presenting a lot of useful material clearly and concisely, together with the reasoning behind it. I wish I had this when I started doing performance work.
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.
When you add prefetching (that is, compare against the middle element and fetch both the middle of the left half and the middle of the right half ahead of time) you are essentially doing radix-4 search, just with fewer actual comparisons.
(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).
Thanks, this is great! I think this conversation is a great illustration for the idea that data structures can be seen as more fundamental than algorithms.
Because the STL makes a bunch of guarantees that can't be broken. Like that an object won't ever move within a hashmap, even on edits. Or that std::set has to use buckets and linked lists.
Basically they've overspecified their datastructures and we're now paying the price
I strongly disagree, and I'm perplexed how anyone can describe fundamental traits such as object lifetimes of fundamental infrastructure such as standard data structures of being over specified.
Just imagine the shit show it would be if upgrading your compiler broke your code because std::set started leading your code to throw exceptions because they sneaked a major breaking change such as moving objects that should not be moved.
It's also perplexing how breaking backward compatibility is depicted as a perfectly acceptable thing to do to a major programming language while completely ignoring the ability to release code as a third-party library. If the new implementation of a std::set alternative is any good, people would be lining up around the block to adopt it. I mean,it's already a standard practice in game development to use custom data structure implementations with custom allocators. Why is this not an option, but breaking half of the world's code suddenly is?
Because if you need something to remain in the same place you box it yourself. Ruining the performance for everyone else because you don't want to handle some boxing on your own is hardly reasonable. This goes fully against the C++ mantra of if you don't use it, you don't pay for it. It's why you have sort and stable_sort rather than unstable_sort and sort.
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
Std::set is using red black trees, did you mean std unordered set?
yes, the common complaint about separate chaining being effectively mandatory is about unordered_map and unordered_set. It looks like std::set suffers from essentially the same pathology though: you cannot use implementations with good data layouts (b-trees) because the standard imposes unreasonable requirements about iterator invalidation.
See https://stackoverflow.com/a/26552219
Author here. I published most of these in one batch two years ago, and this is a relatively short time for compilers and libraries to catch up (when Daniel Lemire publishes something, it also usually takes a few years before it makes its way to the standard libraries, and he is much more involved in the downstreaming process than I am).
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.
For the binary search index speed up, is that documented somewhere? The English version talks about Eytzinger layout but I think you’re referring to something else since that’s not an ancillary array size.
Great job on this book. Lots of great content that can be used as reference.
https://en.algorithmica.org/hpc/data-structures/s-tree/
https://www.youtube.com/watch?v=1RIPMQQRBWk
The API design of STL is often over-constrained.
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.
There’s also other reasons. For example, take binary search:
* 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.
Is there a statically-compiled language where the subset of methods of an API or ADT that ever get referenced, determines at link time which implementation of the API or ADT gets linked + WPOed against?
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.
C++ STL is generic and cross-platform, but I suspect they are doing specific optimisations (x86 Asm), and it's very easy to beat a compiler that way.
It’s not that easy to beat compilers, they know how to generate processor specific instructions too.
I am inclined to believe those numbers :)
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.