Algorithms for Modern Hardware
en.algorithmica.org
en.algorithmica.org
March 7, 2022 - 62 comments - https://news.ycombinator.com/item?id=30583808
Feb 17, 2022 - 49 comments - https://news.ycombinator.com/item?id=30376140
Feb 12, 2022 - 44 comments - https://news.ycombinator.com/item?id=30311112
Nov 1, 2022 - 33 comments - https://news.ycombinator.com/item?id=33427349
Of course nothing can be complete, but I had the following pieces of feedback (plan on opening a GitHub issue later):
The compiler flags section is missing the following:
* Os - optimize for size
* LTO
* Compiling -ffunction-section -fdata-sections & then linking with —-gc-sections (arguably this one just reduces the size of the binary through dead code elimination)
Other:
PGO should probably be mentioned in the flags and targets section as “we’ll describe this in situational optimizations“ (not sure why it’s written there but whatever).
AutoFDO isn’t discussed which is important since it makes running FDO actually feasible in production.
Cold annotations and hot/cold code splitting (hot/cold code splitting isn’t even discussed).
I do intend to translate it someday, but it has nothing to do with performance engineering :)
Specifically, in what way should a language be designed to aid the compiler in finding the optimal code?
For example for the matrix multiplication, why can't the compiler find the optimal code? Why are BLAS written in assembly for each CPU architecture? Isn't this a question of having a high level CPU spec (how many ports, instruction latency, throughput) and then using a constraint solver to find the optimal code?
So yes there has been an enormous amount of research into both the programming language design side of this equation, the compiler design, and the area in the middle. Probably hundreds of thousands of research papers since the 50s or 60s.
Compilers and automated systems, in the general case at least, still can't out compete a domain expert that is familiar with the specific hardware being targeted, a good profiler, and the time to fiddle with the raw assembly.
Level 3 BLAS functions like matrix on matrix products perform O(N^3) operations on O(N^2) data.
The main way BLAS boosts Level 3 functions is cache optimization which is hardware dependent.
But optimization problems in general are not trivial for computers.
On that specific subject of SIMD portability, embedded DSL like Highway developed by Google [0] can help. Hopefully it'll gain traction and usage.
However, there are some takes beyond the “Algol68 on PDP11” design of most languages. There’s Intel’s SPMD C compiler that extends the language to make auto-vectorization a first-class feature.
There is Halide lang specifically for image processing, which separates the goal from the algorithms used to archive it.
A language that helps the compiler has the usual properties we already know: provide as much info as possible with types, and restrict the set of allowable expressions to make the search tractable (like CUDA, ownership and alias analysis, and so on).
One of my favourite write-ups: https://cp-algorithms.com/string/z-function.html
For reference, Quake style Rsqrt hasn't been practical on x86 for more than a decade, as Intel processors internally separate integer and float SSE registers, and converting between the two is costly.
Instead, they have a built-in intrinsic of _mm_rsqrt_ps which does a limited precision rsqrt in hardware.
https://en.algorithmica.org/hpc/arithmetic/rsqrt/
> In fact, it is so good that it has been implemented in hardware, so the algorithm is no longer relevant by itself for software engineers, but we are nonetheless going to walk through it for its intrinsic beauty and great educational value.
<< 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
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.
I also like the talk by Nicholas Ormrod “The strange details of std::string at Facebook":
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.
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
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?
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/
> 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.
step-0 sit quietly in a room with paper and pencil, and ... T.H.I.N.KYou can't throw more compute at a problem ad infinitum.