15 ms·

Do Low-Level Optimizations Matter? (2020)

134 points by signa11 5y ago

makapuf 5y ago
The article is indeed interesting underlining several cache miss aspects and performance impacts, but sorting 1e8 ints in 7s with standard lib vs 4s (with complex and subtle insights, and maybe sensitive to cpu arch) might not be worth it if you're dealing with a database, or with not that experienced coworkers, or deaking with a more complex computation. So does 2x matter? The article doesn't say, but it is interesting nonetheless.
reader_mode 5y ago
>Why doesn’t G++ generate cmov instructions? Older releases did, in fact, often enough to generate bug reports11. It turned out that, any time a subsequent loop iteration depends on the result, and the branch would have been predicted correctly, cmov may be slower than a branch, sometimes much slower. cmov can stall speculation all by itself. >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.
- pjmlp 5y ago
  I wish I got a penny for each C and C++ developer that fails to follow that advice.
- alex_smart 5y ago
  >This is why you don't optimize 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?
  - setr 5y ago
    GP is talking to application developers, not compiler devs.
    - alex_smart 5y ago
      I don't know how many application developers resort to manually generating the assembly, so not sure how that lesson can be gleaned out from the quoted passage.
      - setr 5y ago
        the set of over-optimizing app developers will do just that :) 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
dragontamer 5y ago
Sorting is a good 'random problem' but matrix multiplication is WOW when you get all the low level details right. 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.
- duped 5y ago
  And it's incredibly frustrating that precious few languages bake in matrix arithmetic so compilers can do this optimization for you. There's Octave and MATLAB but they're slow for other reasons. It's very frustrating when you have to either use some crazy template library that takes forever to compile or do the optimizations by yourself. Julia is definitely promising for that reason
  - jpeloquin 5y ago
    I thought baking matrix arithmetic into the language was more about making matrix-related code look nice than making it faster. That is, most languages just use LAPACK for matrix arithmetic, even Matlab and Julia, and they are distinguished only in that they provide special syntax for it. "In Julia (as in much of scientific computation), dense linear-algebra operations are based on the LAPACK library, which in turn is built on top of basic linear-algebra building-blocks known as the BLAS" [0]. How does baking matrix arithmetic into the language itself (maybe I misunderstood what you meant by this) provide new opportunities for compilers to optimize the code? Is it that if every bit of a program was implemented in the same language (e.g., Fortran), the compiler can do whole-program optimizations it otherwise could not? [0] https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#BLAS-functions https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#BLAS-...
    - _hl_ 5y ago
      I think the point they were making is that LAPACK et al are a pain to use directly (they really are!), and abstractions are limited by the capabilities of the language or heavy to compile (not sure I agree, Eigen is pretty okay).
MrYellowP 5y ago
Depends on the necessity. If you really need more performance, then they absolutely matter. 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.
wpietri 5y ago
For those interested in the question, it's worth looking at how zstd was made. I have to archive hundreds of TB of JSON about tweets, so I did a compressor bake-off last year. I was surprised at how much better zstd did. Turns out designing for the low-level details of modern processors can make a big difference: https://engineering.fb.com/2016/08/31/core-data/smaller-and-faster-data-compression-with-zstandard/ https://engineering.fb.com/2016/08/31/core-data/smaller-and-...
- userbinator 5y ago
  Somehow, I suspect not using JSON in the first place might yield better absolute results since the compressor wouldn't have to deal with all the redundancy of JSON and instead focus on the content only.
  - wpietri 5y ago
    For many applications, this one included, "the first place" is out of reach. What I've got is an awful lot of incoming JSON data. I'd like to keep a copy in case we need it later. 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.
    - kragen 5y ago
      Also, surprisingly often, doing something reasonably workable but far from optimal, and then throwing generic compression algorithms at it, can work very nearly as well as carefully doing the precisely optimal thing. SNMP uses BER, which has lots of carefully thought out compact representations for data types, and COAP has CBOR, and in both cases you can usually do as well or better on space by running a simple ASCII syntax through LZW. Usually not that much slower, either.
      - rixed 5y ago
TchoBeer 5y ago
The headline is misleading; the article isn't really about whether or not low-level optimisations matter. With that being said, the idea that one of the big speedups that computers have gotten in the past two decades is better caching and branch prediction is interesting, and the idea that we use neural nets for it is known to me but still really cool.
- atq2119 5y ago
  My understanding is that the use of neural nets in branch prediction is greatly overstated for marketing purposes. It's really more that different branch predictors are combined into a single one using a simple function (read: linear combination) that is "learned" (read: coefficients are updated sightly whenever the branch is encountered, based on the predicted vs actual branch direction).
  - dragontamer 5y ago
    AMD Zen 1 had a neural net branch predictor for real. 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-core/ https://fuse.wikichip.org/news/2458/a-look-at-the-amd-zen-2-... Wikichip has done an article on it.
    - ncmncm 5y ago
      They all (still) have it, but it is no longer worth mentioning. Zen 2 has another scheme running at the same time, and they compete. Zen 3 must have refinements, and more bits thrown at it.
  - ncmncm 5y ago
    Neural nets are themselves greatly overstated for marketing purposes. Any time you have an array of coefficients that are adjusted according to input history and combined for a result, you might as well call it that.
einpoklum 5y ago
> Do Low-Level Optimizations Matter? 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.
- ncmncm 5y ago
  They matter to the degree a factor-of-two in performance (or -of-ten, or -of-100, for other optimizations) matters. On most problems, for most people, that matters not at all. But there are people who pay a lot of money for smaller gains. Certain people make a lot of money delivering gains. 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.
inciampati 5y ago
For sorting, not really. The big development in compute power is parallelism. ips4o facto (https://github.com/SaschaWitt/ips4o https://github.com/SaschaWitt/ips4o), if you want to sort large vectors really fast it makes more sense to sort in-place and in parallel. Parallel in-place radix sort is also choice, but way less flexible than comparison sort.
nightcracker 5y ago
This article is missing the important reference to the prior work by Edelkamp and Weiss, on branchless quicksort [1]. 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 https://arxiv.org/abs/1604.06697 [2] https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort [3] https://arxiv.org/abs/2106.05123 https://arxiv.org/abs/2106.05123 [4] https://www.boost.org/doc/libs/1_76_0/libs/sort/doc/html/sort/single_thread.html https://www.boost.org/doc/libs/1_76_0/libs/sort/doc/html/sor...
- Waterluvian 5y ago
  An ignorant question: Why don’t default sort implementations provide multiple approaches under the hood and switch based on collection size?
  - abatilo 5y ago
    There's at least some precedent for conditional execution in standard libraries. At least, in Python, the default sort is https://en.m.wikipedia.org/wiki/Timsort https://en.m.wikipedia.org/wiki/Timsort
  - ot 5y ago
    They do, to a degree. Modern implementations generally use hardcoded routines for very small numbers (say, up to 5), then some quadratic sort like insertion sort, then quicksort. The dispatching can happen at all levels of the recursion, so quicksort's leaves are actually optimized sorts for small collections.
  - anaphor 5y ago
    This is a thing, see https://www.youtube.com/watch?v=FJJTYQYB1JQ https://www.youtube.com/watch?v=FJJTYQYB1JQ (talk by Andrei Alexandrescu at CppCon 2019 about this exact idea)
    - 5y ago
meisel 5y ago
It appears that sorting is done on the memory-mapped buffer? That seems like it could have extra costs (lazily paging in from disk) that we wouldn’t see for an in-memory buffer, and which could affect the benchmark.
- jandrewrogers 5y ago
  The MAP_POPULATE flag instructs mmap() to load the underlying pages into physical memory immediately. There should be no paging from disk during the benchmark run.
  - ncmncm 5y ago
    Not only that: after the first run, all the pages are still in memory, for all the subsequent runs. But you are making a private copy each time; that copying shows up as "system" time in the output.
ot 5y ago
> let us begin with a file of a hundred-million totally random integers [...] This is objectively the worst case, containing the greatest possible entropy; but also the best case, hiding no surprises. 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.
- ot 5y ago
  For example, the radix sort implementation is cheating here: for (auto& v : buckets) v.reserve((end - begin)/128); It's assuming uniform distribution of the buckets, so it can make a very accurate guess and avoid extra allocations. If that line is removed for the general case, I would expect things to get a lot slower. I would be curious to see a comparison with a good implementation of in-place radix sort. For example there is one available in boost.
  - dragontamer 5y ago
    The radix sort isn't really the crux of the article. They're trying to just see how fast radix sort is ("unfairly"), and then try to improve a different comparison-sort instead.
    - ncmncm 5y ago
      Exactly. Quicksort, also, isn't the crux of the article. Both are ways to sample how the CPU behaves. That is why the quicksort is also not production-grade. If it were more complicated, it would teach us less.
- ncmncm 5y ago
  If you are designing a sorting algorithm component for production, it is critical to take into account all the blips and wrinkles that real components will face. 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. [1] https://github.com/ncm/nytm-spelling-bee https://github.com/ncm/nytm-spelling-bee
adrian_b 5y ago
The history of the CMOV instructions mentioned in the article is incorrect. 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.
- ncmncm 5y ago
  Thank you, I will fix this.
api 5y ago
Branches matter a lot in many cases. In some cases compilers are smart enough to optimize them out and in some cases they aren’t.
ncmncm 5y ago
Author here. I didn't know this was on HN until just now.
the_only_law 5y ago
A couple of dumb questions: 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.
- ncmncm 5y ago
  All those things are done, mostly at different times by different people. 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.

134 points by signa11 5y ago

The article is indeed interesting underlining several cache miss aspects and performance impacts, but sorting 1e8 ints in 7s with standard lib vs 4s (with complex and subtle insights, and maybe sensitive to cpu arch) might not be worth it if you're dealing with a database, or with not that experienced coworkers, or deaking with a more complex computation. So does 2x matter? The article doesn't say, but it is interesting nonetheless.

reader_mode 5y ago

>Why doesn’t G++ generate cmov instructions? Older releases did, in fact, often enough to generate bug reports11. It turned out that, any time a subsequent loop iteration depends on the result, and the branch would have been predicted correctly, cmov may be slower than a branch, sometimes much slower. cmov can stall speculation all by itself. >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.

pjmlp 5y ago
I wish I got a penny for each C and C++ developer that fails to follow that advice.
alex_smart 5y ago
>This is why you don't optimize 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?
- setr 5y ago
  GP is talking to application developers, not compiler devs.
  - alex_smart 5y ago
    I don't know how many application developers resort to manually generating the assembly, so not sure how that lesson can be gleaned out from the quoted passage.
    - setr 5y ago
      the set of over-optimizing app developers will do just that :) 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

dragontamer 5y ago

Sorting is a good 'random problem' but matrix multiplication is WOW when you get all the low level details right. 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.

duped 5y ago
And it's incredibly frustrating that precious few languages bake in matrix arithmetic so compilers can do this optimization for you. There's Octave and MATLAB but they're slow for other reasons. It's very frustrating when you have to either use some crazy template library that takes forever to compile or do the optimizations by yourself. Julia is definitely promising for that reason
- jpeloquin 5y ago
  I thought baking matrix arithmetic into the language was more about making matrix-related code look nice than making it faster. That is, most languages just use LAPACK for matrix arithmetic, even Matlab and Julia, and they are distinguished only in that they provide special syntax for it. "In Julia (as in much of scientific computation), dense linear-algebra operations are based on the LAPACK library, which in turn is built on top of basic linear-algebra building-blocks known as the BLAS" [0]. How does baking matrix arithmetic into the language itself (maybe I misunderstood what you meant by this) provide new opportunities for compilers to optimize the code? Is it that if every bit of a program was implemented in the same language (e.g., Fortran), the compiler can do whole-program optimizations it otherwise could not? [0] https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#BLAS-functions https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#BLAS-...
  - _hl_ 5y ago
    I think the point they were making is that LAPACK et al are a pain to use directly (they really are!), and abstractions are limited by the capabilities of the language or heavy to compile (not sure I agree, Eigen is pretty okay).

MrYellowP 5y ago

Depends on the necessity. If you really need more performance, then they absolutely matter. 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.

wpietri 5y ago

For those interested in the question, it's worth looking at how zstd was made. I have to archive hundreds of TB of JSON about tweets, so I did a compressor bake-off last year. I was surprised at how much better zstd did. Turns out designing for the low-level details of modern processors can make a big difference: https://engineering.fb.com/2016/08/31/core-data/smaller-and-faster-data-compression-with-zstandard/ https://engineering.fb.com/2016/08/31/core-data/smaller-and-...

userbinator 5y ago
Somehow, I suspect not using JSON in the first place might yield better absolute results since the compressor wouldn't have to deal with all the redundancy of JSON and instead focus on the content only.
- wpietri 5y ago
  For many applications, this one included, "the first place" is out of reach. What I've got is an awful lot of incoming JSON data. I'd like to keep a copy in case we need it later. 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.
  - kragen 5y ago
    Also, surprisingly often, doing something reasonably workable but far from optimal, and then throwing generic compression algorithms at it, can work very nearly as well as carefully doing the precisely optimal thing. SNMP uses BER, which has lots of carefully thought out compact representations for data types, and COAP has CBOR, and in both cases you can usually do as well or better on space by running a simple ASCII syntax through LZW. Usually not that much slower, either.
    - rixed 5y ago

TchoBeer 5y ago

The headline is misleading; the article isn't really about whether or not low-level optimisations matter. With that being said, the idea that one of the big speedups that computers have gotten in the past two decades is better caching and branch prediction is interesting, and the idea that we use neural nets for it is known to me but still really cool.

atq2119 5y ago
My understanding is that the use of neural nets in branch prediction is greatly overstated for marketing purposes. It's really more that different branch predictors are combined into a single one using a simple function (read: linear combination) that is "learned" (read: coefficients are updated sightly whenever the branch is encountered, based on the predicted vs actual branch direction).
- dragontamer 5y ago
  AMD Zen 1 had a neural net branch predictor for real. 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-core/ https://fuse.wikichip.org/news/2458/a-look-at-the-amd-zen-2-... Wikichip has done an article on it.
  - ncmncm 5y ago
    They all (still) have it, but it is no longer worth mentioning. Zen 2 has another scheme running at the same time, and they compete. Zen 3 must have refinements, and more bits thrown at it.
- ncmncm 5y ago
  Neural nets are themselves greatly overstated for marketing purposes. Any time you have an array of coefficients that are adjusted according to input history and combined for a result, you might as well call it that.

einpoklum 5y ago

> Do Low-Level Optimizations Matter? 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.

ncmncm 5y ago
They matter to the degree a factor-of-two in performance (or -of-ten, or -of-100, for other optimizations) matters. On most problems, for most people, that matters not at all. But there are people who pay a lot of money for smaller gains. Certain people make a lot of money delivering gains. 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.

inciampati 5y ago

For sorting, not really. The big development in compute power is parallelism. ips4o facto (https://github.com/SaschaWitt/ips4o https://github.com/SaschaWitt/ips4o), if you want to sort large vectors really fast it makes more sense to sort in-place and in parallel. Parallel in-place radix sort is also choice, but way less flexible than comparison sort.

nightcracker 5y ago

This article is missing the important reference to the prior work by Edelkamp and Weiss, on branchless quicksort [1]. 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 https://arxiv.org/abs/1604.06697 [2] https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort [3] https://arxiv.org/abs/2106.05123 https://arxiv.org/abs/2106.05123 [4] https://www.boost.org/doc/libs/1_76_0/libs/sort/doc/html/sort/single_thread.html https://www.boost.org/doc/libs/1_76_0/libs/sort/doc/html/sor...

Waterluvian 5y ago
An ignorant question: Why don’t default sort implementations provide multiple approaches under the hood and switch based on collection size?
- abatilo 5y ago
  There's at least some precedent for conditional execution in standard libraries. At least, in Python, the default sort is https://en.m.wikipedia.org/wiki/Timsort https://en.m.wikipedia.org/wiki/Timsort
- ot 5y ago
  They do, to a degree. Modern implementations generally use hardcoded routines for very small numbers (say, up to 5), then some quadratic sort like insertion sort, then quicksort. The dispatching can happen at all levels of the recursion, so quicksort's leaves are actually optimized sorts for small collections.
- anaphor 5y ago
  This is a thing, see https://www.youtube.com/watch?v=FJJTYQYB1JQ https://www.youtube.com/watch?v=FJJTYQYB1JQ (talk by Andrei Alexandrescu at CppCon 2019 about this exact idea)
  - 5y ago

meisel 5y ago

It appears that sorting is done on the memory-mapped buffer? That seems like it could have extra costs (lazily paging in from disk) that we wouldn’t see for an in-memory buffer, and which could affect the benchmark.

jandrewrogers 5y ago
The MAP_POPULATE flag instructs mmap() to load the underlying pages into physical memory immediately. There should be no paging from disk during the benchmark run.
- ncmncm 5y ago
  Not only that: after the first run, all the pages are still in memory, for all the subsequent runs. But you are making a private copy each time; that copying shows up as "system" time in the output.

ot 5y ago

> let us begin with a file of a hundred-million totally random integers [...] This is objectively the worst case, containing the greatest possible entropy; but also the best case, hiding no surprises. 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.

ot 5y ago
For example, the radix sort implementation is cheating here: for (auto& v : buckets) v.reserve((end - begin)/128); It's assuming uniform distribution of the buckets, so it can make a very accurate guess and avoid extra allocations. If that line is removed for the general case, I would expect things to get a lot slower. I would be curious to see a comparison with a good implementation of in-place radix sort. For example there is one available in boost.
- dragontamer 5y ago
  The radix sort isn't really the crux of the article. They're trying to just see how fast radix sort is ("unfairly"), and then try to improve a different comparison-sort instead.
  - ncmncm 5y ago
    Exactly. Quicksort, also, isn't the crux of the article. Both are ways to sample how the CPU behaves. That is why the quicksort is also not production-grade. If it were more complicated, it would teach us less.
ncmncm 5y ago
If you are designing a sorting algorithm component for production, it is critical to take into account all the blips and wrinkles that real components will face. 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. [1] https://github.com/ncm/nytm-spelling-bee https://github.com/ncm/nytm-spelling-bee

adrian_b 5y ago

The history of the CMOV instructions mentioned in the article is incorrect. 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.

ncmncm 5y ago
Thank you, I will fix this.

api 5y ago

Branches matter a lot in many cases. In some cases compilers are smart enough to optimize them out and in some cases they aren’t.

ncmncm 5y ago

Author here. I didn't know this was on HN until just now.

the_only_law 5y ago

A couple of dumb questions: 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.

ncmncm 5y ago
All those things are done, mostly at different times by different people. 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.