Do Low-Level Optimizations Matter? (2020)
cantrip.org
cantrip.org
I've long since implemented that in pdqsort [2], along with other techniques described by me in [3] which is a drop-in replacement for std::sort that's ~twice as fast as std::sort for small data with branchless comparisons. It's also available in Boost.sort [4].
[1] https://arxiv.org/abs/1604.06697 [2] https://github.com/orlp/pdqsort [3] https://arxiv.org/abs/2106.05123 [4] https://www.boost.org/doc/libs/1_76_0/libs/sort/doc/html/sor...
Why don’t default sort implementations provide multiple approaches under the hood and switch based on collection size?
At least, in Python, the default sort is https://en.m.wikipedia.org/wiki/Timsort
“Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving insertion sort to order the MAX_THRESH items within each partition. This is a big win, since insertion sort is faster for small, mostly sorted array segments.”
The comment on the definition of MAX_THRESH is very funny/something worth crying about.
“This particular magic number was chosen to work best on a Sun 4/260.”
That was a 16.67MHz machine with 128 megabytes of RAM, tops. If that magic constant has been checked since 1990, maybe, it’s worth updating that comment.
A factor of 2 would IMO be worth it, though.
Cursory reading https://github.com/freebsd/freebsd-src/blob/de1aa3dab23c06fe..., I get the impression FreeBSD switches over to a ¿bubble sort? (I didn’t look close) at <7 elements.
That function also seems newer (it claims to implement https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engi..., which is from 1993)
I agree that a factor of 2, or even 1.03, would be worthwhile. But the biggest problem facing standard library authors is not frequently performing 1.5× or 2× worse than optimal; it's occasionally performing 10000× worse than optimal, like the story Bentley & McIlroy start out with in that paper about the organ-pipe array. (And that's why the Golang stdlib uses introsort.)
BTW, just because someone was optimizing their library parameters on a machine from 01987 (like the Sun-4/260) doesn't necessarily mean they were doing it before 01993. In 01993 I was using a VAX-11/785 from 01984. Hardware lasted longer in those days (it was less common to drop your SPARC on the sidewalk and spiderweb the touchscreen) and its higher cost forced it into longer service. https://books.google.com.ar/books?id=JRgDwCkMX_cC&pg=PP121&l... says the VAX-11/785's list price in 01984 was US$200k, equivalent to US$513k in 02021 according to the BLS CPI. Not counting the terminals and printers! (About 2000 kids learned to program on that beast, so it was probably a good expenditure for the school district.) In 01988 Sun listed the Sun-4/260 at a base price of US$40k (http://www.bitsavers.org/pdf/sun/Sun_Price_List_Dec88.pdf) but probably more realistically US$80k if you wanted a disk and some way to back it up. US$80k in 01988 is US$180k in 02021. So you might find yourself running a big machine long after it was obsolete.
But surely that sort of penny-pinching was unique to high schools like mine, not serious professionals like those writing FreeBSD's libc, GNU libc, and Bentley's SP&E article, written from the lofty sanctuary of Bell Labs? Well, Bentley's 01993 paper reports benchmark results (from 01992) on a MIPS R3000 (introduced 01988) and a VAX 8550 (introduced 01986).
Why didn't he benchmark it on any machine from that decade? Probably he didn't have one. And the glibc folks were mostly volunteers at that point. CSRG was still DoD-funded, but they disbanded in 01995 after 4.4. (I think a bunch of them were at BSDI for a while.)
— ⁂ —
The FreeBSD code is doing an insertion sort. Insertion sort looks a lot like bubble sort, and it took me a long time to appreciate the difference. One difference that's sometimes relevant for this sort of thing is that, on nearly-sorted data, insertion sort is O(N) and bubble sort is O(N²). But in this case that's not relevant because it's not running a single insertion-sort pass over the whole array after nearly-sorting it via quicksort; it's insertion-sorting each tiny partition. (The sorted part of the partition is the range from a up to pm.)
After N iterations of the outer loop of either insertion sort or bubble sort, one end of your array has N sorted items in it. (The bottom of the partition from a to a+n, in this case.) The difference is that insertion sort grows that sorted region by inserting the nearest unsorted element into it, while bubble sort grows it by inserting the smallest unsorted element into it (or largest, if you're sorting toward the top). So bubble sort only makes as much progress per pass as insertion sort, but it does a bunch of unnecessary extra work to do it (basically, the same work selection sort does); when sorting M randomly ordered items, insertion sort does on average ¼M† comparisons and swaps on each of the M passes, while bubble sort does ½M comparisons (and still ¼M swaps).
Never use bubble sort.
______
† Actually the number is something like ¼√(M² - M), I think. I'd have to go calculate it to be exact.
I don't understand why you would complain it is missing reference to Edelkamp and Weiss when its second and third references are to papers by Edelkamp and Weiss. My [3] is identically the paper labeled [1] in the complaint.
Is it possible for me to write and test a robust custom compressor that does better in both storage and compression costs than any of the modern compressors? Possibly.
Is that true even though one of FB's goals was specifically optimizing JSON compression? Maybe.
Can I build it for the few hundred bucks per month in S3 costs I might save? Definitely not.
L1 blocking, prefetching, column vs row, etc etc. You can probably spend a whole semester just optimizing matrix multiplication and understanding each incremental low level optimization.
Julia is definitely promising for that reason
[0] https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#BLAS-...
The overhead of BLAS is significant for small matrices. However, a compiler can tell if matrices are small at compile time (or JIT time) and inline the expressions which presents enormous speed gains. It can also make judgement calls about when to use sparse or dense arrays but that's a bit trickier. Compilers can do this without knowing that matrices or linear algebra exist, but it usually takes PGO which can be difficult to use.
Iirc there's a linear algebra library for Julia that can beat the LAPACK backends for small matrices, which is a pretty big deal.
There are also classes of optimizations like SIMD that don't just depend on matrix size but the target platform, which may not be the platform the software was compiled on. The way to do this is with function multiversioning but not all compilers/languages support it, this is kind of a classic usecase for a JIT compiler.
One of the reasons Eigen is great is because it can use template semantics to make these optimizations at compile time. It's just slightly annoying in how it harms compile times.
While ARM had such instructions from the beginning and other computers had them even earlier, in the Intel/AMD x86 instruction set the CMOV instructions (including FCMOV for floating-point) have been introduced in the Pentium Pro, in November 1995 and all later Intel models have them. AMD has added the CMOV/FCMOV instructions in Athlon, in June 1999.
The 64-bit extension of x86 has just inherited them from the 32-bit ISA and Itanium had them later than Pentium Pro.
The CMOV instructions were an important new feature of Pentium Pro, besides the out-of-order execution and triple instruction decoding and execution.
>The latest designs from Intel and AMD are said to avoid the cmov pipeline stall, often, but Gcc has not caught up with them yet.
This is why you don't optimize first - even things that you think you know might not be true in the next HW iteration, compiler version, etc. This pattern shows up all the time. The only sane way to do optimization is to measure, write tests to catch regressions, otherwise always write for readability first.
The internals of an optimizing compiler might very well be the worst place to apply that principle. Who else is supposed to implement these optimizations, if not the compiler?
But more generally, optimizations eventually stop being true in general, and start being true only in a specific context -- and the lower that optimization, the more specific that context gets. If you want to "teach" GCC how to optimize something properly (more commonly in the form of attribute notations e.g. inlining, but more extreme is poking around godbolt), you start falling into this trap
There is no single worst case for sorting, and in fact most benchmarks use a several different inputs, and even the best algorithms win some and lose some. It's important not to overfit to a specific distribution.
For example, fully random integers can benefit MSB-radix-type sorts, because it's enough to look at a log(n) prefix of the integer to have the data almost sorted, so the later passes have very predictable behavior.
Also the chance of duplicates is negligible, and duplicates are problematic for some quicksort implementations.
for (auto& v : buckets) v.reserve((end - begin)/128);
But when you are investigating how and why your CPU has the performance characteristics it has evolved, all those complications directly interfere with learning. The goal here was not to make a production-grade sorting tool; it was to understand what affects performance, using the sorting problem as a microscope.
The method is generally useful. Some years back I spent months refining a one-page program[1] to generate a list of word puzzles. After the first day, the list of puzzles was of no interest, but refining the means to produce it faster taught me a great deal.
In general it makes sense to program for the platform/CPU, not the compiler. Respect the CPU first, the compiler second. This turns into second nature just like everything else.
From my experience, 99% of the people out there disagree, doing so for a good reason. They code for the compiler, not the system. When that's good enough, then that it is.
1) In practice, how much of low level optimization is writing code differently, vs compiler tweaking? How much is done by offloading to other (specialized) hardware?
2) How could someone learn to do something like this. I’ve never had any situations where micro optimization is necessary or even useful. Never had to work with extremely large amounts of data, worry about tight timing of concerns, etc. and it seems like outside of an industrial setting it seems like getting access to the types of problems requiring this is the most difficult part. I mean, I suppose simply doing sorts on massive quantities of numbers is one thing, but it feels limited.
Optimizations are very slow to move into compilers, but once there improve potentially millions of programs, so there is a lot of value in it. But there is practically no value to be extracted from a better compiler, so the money to pay for that is very limited.
Any optimization that can be pushed into a compiler can be done "by hand" instead. All are done that way at first, and just a few move into compilers, eventually, after enough people get tired of doing them by hand, or seeing them not being done by hand when they ought to be.
The only way anyone learns to do it is to first need to do it. Most people don't need to, and so never do. But the highest-paying jobs are the ones that either make somebody a lot of money or save them a lot of money. The former have more upside; there is no upper limit to how much money could be made. The latter is strictly limited: you can't save anybody more money than the difference between what they are paying and what they pay you. But the latter is easier to get paid for, because people know what they are paying and hate it. Money you save them is money into their pocket over and over again.
Sorting is something people write about optimizing because everybody understands what it means. Few people depend on how fast ordinary sorting is (or, anyway, know they do), but the techniques you need to make sorting fast are the same as you need to make other things fast. Studying lots of optimizations makes you better able to reason about what you can do to optimize.
But Zen2 / Zen3 don't seem to have this idea referenced anywhere. I can only imagine that AMD managed to beat their neural-net branch predictor with some boring methodology.
EDIT: https://fuse.wikichip.org/news/2458/a-look-at-the-amd-zen-2-...
Wikichip has done an article on it.
1. They matter a _lot_.
2. (Mentioned but not covered in the article) adaptation to known features of your input distribution also matters a lot.
Often, it didn't matter before, and now does. Facebook was coded in PHP, so they obviously didn't care about performance when they wrote it. But now Facebook is stuck with millions of lines of PHP, and has people going to crazy lengths to get it a few percent faster.