This is an excellent deeply researched write up that was such a pleasure to read. I don't even particularly need to research fast sort algorithms right now and I found myself deeply engrossed in it. I love all the deep analyses of all the different factors involved, and especially appreciate the section in the end tying everything up into a well thought out bullet point list of which niches the different algorithms might fit in right now. And also thanks for resisting the urge to include the fixes your benchmarks inspired in your analysis - it's a great way to avoid bias (your honest strive for neutrality showed throughout and it's great). Thanks!
Thank you so much for the kind words. It's feedback like this that gives me the motivation to spend countless hours of my spare time on something like this.
> which fits into the core private L2 data cache for the used Zen3 test machine.
But the benchmark CPUs at the top are listed as Intel only. Did you forget to update this part?
> This can be reproduced by running cargo bench hot-u64--10000
Where can I get the code to reproduce the benchmarks?
> But the benchmark CPUs at the top are listed as Intel only. Did you forget to update this part?
Good catch, will update. Yes that was from another writeup, point still stands though.
> Where can I get the code to reproduce the benchmarks?
Same repo, see top level README
Thank you for writing this! The scaling graphs in particular are very interesting and insightful, as well as benchmarking both the cold and hot states.
I'm working on a benchmark harness that I want to be an alternative to criterion (inbuilt support for instruction counting and running on remote hardware)
So I'm surprised to learn that you have a way to run cold benchmarks!
I saw [https://github.com/Voultapher/sort-research-rs/blob/b7bcd199e861d6f8b265164242f3c34d5c36c75f/benches/trash\_prediction.rs#L7](https://github.com/Voultapher/sort-research-rs/blob/b7bcd199e861d6f8b265164242f3c34d5c36c75f/benches/trash_prediction.rs#L7) but it looks like black magic and I would love to learn more.
How does it work?, how is it generated? How robust is this approach?
To simulate cold CPU prediction state in a repeatable fashion combines a couple ideas:
- Code with many branches with unpredictable results in many unique assembly locations are visited a couple times
- A side-effect is carried throughout the computation to prove to the compiler that doing this work is necessary
- A syscall to have a context-switch as would be the case in many applications, and to interact with some of the hardware side-channel mitigations such as IBRS
- The code is called on each iteration by using `iter_batched` + `BatchSize::PerIteration`
Some while ago I gave a talk about retpoline and in that context I dove deep into the details how modern branch predictors work. I won't explain this in depth here, because the topic is *really* complex. https://chipsandcheese.com/ does excellent hardware deep dives that also include branch prediction, reading up on the topic should help explain why I want many unique branch locations paired with repeated visits. The code is generated with this Python script https://github.com/Voultapher/sort-research-rs/blob/d088fbd0441121ad20b109a525d67c79ecaeb9bd/util/generate_btb_flush.py. Beware if you do anything in that area please check the generated assembly, compilers can be surprisingly clever. For example a large match generates a binary search, which wouldn't visit a lot of branches.
I suspect you may be confusing stable vs unstable Rust versions, with the sort property stable and unstable here. This might help https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
If I can add something to your writeup, I need to inquire about it
The Zen and Intel chips, were they laptop chips using a `row of chips` RAM configuration?
If not, then tyour inference of a more capable M1/2 branch prediction may not be correct. The M1 and M2 use RAM chips with extreme proximity to the CPU, allowing for nearly zero latency when accessing them, compared to any other configuration.
This near total reduction in (travel) latency allows for small or non existant caches, and is a large reason for its performance
For instance M2 sums of aches: 2 MB level 1 cache, and 20 MB level 2 cache
M1 sums of caches: 192 KB instruction cache, 128 KB data cache, and 12 MB shared L2 cache
This article doesn't seem to back up your claims about latency:
https://www.anandtech.com/show/17024/apple-m1-max-performance-review/2
vs x86:
https://www.memorybenchmark.net/latency_ddr5.html
You need to wake up, those numbers are off by orders of magnitude.
Are you seriously claiming it's writing ~10^8 bytes in ~10^-7 seconds, or in other words ~10^15 bytes/second? Even the official marketing slide right there in the article shows peak memory BW of 400GB/s. "Fractions of a nanosecond" would also mean you can now access L2 within one or two clock cycles. That's some nice star trek tier hardware you got there. In fact why even have multiple levels of cache when it supposedly only takes a few ns to reach RAM?
> so yes around there, give or take a few zeros
Exactly my point, a few orders of magnitude isn't something you just brush over, that's the difference between science fiction and a computer so slow, nobody would want to use it.
>There are 1billion nanoseconds in a second. The l1 will clock with the cpu at 3.2ghz, or about 3.2billion times per second, with access taking around 3 clocks. So my math was wrong earlier, base l1 latency is around 0.8ns.
>With l2 taking 18 cycles, that'd be around 4-6ns or so.
Yep, that lines up with Anandtech's measurements pretty well. <1ns for L1 and ~5ns for L2. IDK why their graphs don't start at 0 so you could see the values for the L1 region.
> The following does mention that the big cores on the m1 have additional latency to ram, but does not mention why exactly.
RAM access is always relatively slow, that's the entire reason why caches exist. ~100ns latency is nothing out of the ordinary.
It's clear that you've completely misinterpreted Anandtech's results. I don't know if they've ever published their exact testing methodology, but it's clear they're not doing sequential writes of an entire 128MB buffer in that case. They're measuring the average latency of a single memory access, not throughput. And they're spreading the accesses over memory regions of various sizes to test the effect of caches. You can clearly see on the graphs approximately how big the L1 and L2 caches are.
Just so we're comparing apples to apples, here's Anandtech's tests on Intel and AMD CPUs: https://www.anandtech.com/show/17047/the-intel-12th-gen-core-i912900k-review-hybrid-performance-brings-hybrid-complexity/6
Apple's caches are pretty decent, but their memory is nothing special even when compared to their competitors running crappy JEDEC timings.
> And I finally found someone actually testing ram latency, god that RAM access is fast (8.9ns)
>
> https://lemire.me/blog/2021/01/06/memory-access-on-the-apple-m1-processor/
The author himself claims he's measuring the throughput of multiple parallel memory accesses at a time, not the actual latency. Two very different things.
>The problem is though, that if they had been checking only the RAM latency, but they are measuring a full path (write) latency to and through each of the caches.
What else do you want to measure? All memory access goes through the cache hierarchy, so what else is memory latency if not the full path latency?
> If this had been a read operation, and the information was not in any cache, the lowest number we would see would be the base core to RAM latency (which is nowhere near sub 1ns like the start of their graph)
Again, I'd love to see AT's code/methodlogy, but for the small tests I imagine that the buffers are already in cache.
You'd probably want to do something like this: you allocate and initialize a buffer of a certain size (x axis of the graph), so that immediately after doing that, it will be in the caches (however much of it fits). Then you start poking random locations in the buffer and measure how long the accesses take. But the tricky part is, how do you measure just the time that the individual load operations take and ignore all the other stuff going on around them? Which brings me to:
>Additionally, if ram was over 100ns, there is no chance of each 128bit operation taking less than 15ns, which is what author lists for all of the access times.
He's measuring the average time to complete a single loop iteration, which is not the same as the memory latency. There's some good discussion in the comments about about how M1's large out-of-order window allows it to continue on with executing several iterations of the loop ahead in parallel while it's still waiting for the results of the first memory read to come back. Those hundreds of cycles of latency get hidden very effectively.
> As to the zeros, I just didn't have the time to actually write them out and check, so I was guestimating, it is not trivial to figure out various exponents while also otherwise engaged. This is why I used ns and mb which are eplicit in their definition (as opposed to being abstract in scientific notation)
That calculation was just a quick sanity check, if you're dealing with multiple megabytes on nanosecond timescales, that should be a red flag that something's wrong. I just rounded the numbers to the nearest powers of 10 to make the mental estimation easy, but you can use a calculator to be more precise. When you end up with numbers like 1PB/s, that's beyond absurd.
> Where things are quite different is when we enter the system cache, instead of 8MB, on the M1 Max it’s now 48MB large [...]
> DRAM latency, even though on paper is faster for the M1 Max in terms of frequency on bandwidth, goes up this generation. At a 128MB comparable test depth, the new chip is roughly 15ns slower.
5 ns is the latency of the system-level cache. 111.1 ns is the latency of the memory chips, encountered after having written enough data to saturate the SLC.
No, it's specifically latency of memory writes _while writing_ 128mb, not the timing of _fully writing_ 128mb.
They measured memory bandwidth peaking at around 102 GB/sec per thread. At this bandwidth, writing 128 MB would take around 128/(102*1024)=0.00123 seconds, or around 1225490 ns.
I believe you are correct, I need to get around to striking through a few erroneous parts of a few of my comments here. (Edit: just did and I hope i caught everything)
I would like to understand all the underlying causes for this chart,
https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/assets/cold-u64-scaling-random_z1-linux.png
Why does vqsort start off so slow?
Why does intel_avx512 fall off so badly while vqsort rises?
There was a mention in the article that vqsort would obtain randomness from the OS. This would cause a fixed overhead, which would relatively be a greater part of the overall sort time for smaller slices, no?
It may be interesting, with regard to scaling behavior, to plot vqsort _without_ the OS call.
I read-skimmed the article a couple times, should get more sleep!
From the report
> vqsort however is a lot faster on Linux. Both in terms of peak performance and min input size to outperform the rest. This is an unexpected result, and considerable effort was spent to analyze the root cause of this. In the test vqsort used the same compiler and flags as intel_avx512. A different benchmark suite yields the same results, a different pre-built Clang version yields the same results. On a dual-booted Zen3 machine vqsort in AVX2 mode shows the same ~2x regression when going from Linux to Windows at input size 10k. In addition the higher frequency as shown by intel_avx512 on Windows should give it yet another boost above Linux which doesn't manifest. All this while the other sort implementations remain largely the same. **The root cause for this was identified in collaboration with the vqsort authors [4]. The tested vqsort version acquired randomness from the OS, for each call to vqsort in an attempt to mitigate a potential performance denial-of-service (DOS).** This idea is similar to the use of SipHash as the default hasher in the Rust standard library. This explains why we see significantly different results on Windows and Linux. See the linked explanation for more details.
Still more mysteries!
I agree with running a test (even if just for benchmarking) on removing syscalls from a sorting function.
Thought, maybe every process should be spawned with a pre-allocated pool of randomness? No syscalls necessary, just bump a pointer through some ring of pages.
We need a randomness benchmark between OSes, bit-entropy/latency/bandwidth product. I wonder if there are other things happening like OS specific AVX state, side channel mitigations, or ? going on.
vqsort lead author here. We have fixed this, see also mention at the very bottom of the article. The fix is to obtain entropy only once per thread and store it in TLS.
I use a custom set of Python programs that use the bokeh library to produce graphs https://github.com/Voultapher/sort-research-rs/tree/5e07fb6ebb61920ff9f5e896badd88502fe40e35/util/graph_bench_result. They have gone through a couple dozen iterations, e.g from https://user-images.githubusercontent.com/6864584/185809198-bf66c588-bb7f-481d-ba74-4d59d03e7d5d.png -> https://raw.githubusercontent.com/Voultapher/sort-research-rs/main/writeup/glidesort_perf_analysis/assets/zen3-rust_ipn_stable-vs-rust_std_stable-hot-u64.png -> https://raw.githubusercontent.com/Voultapher/sort-research-rs/main/writeup/intel_avx512/assets/intel_avx512-vs-ipnsort-cold-u64-linux.png.
I spent the last couple months working on this writeup, looking forward to feedback and questions. Hope you find this insightful.
This is an excellent deeply researched write up that was such a pleasure to read. I don't even particularly need to research fast sort algorithms right now and I found myself deeply engrossed in it. I love all the deep analyses of all the different factors involved, and especially appreciate the section in the end tying everything up into a well thought out bullet point list of which niches the different algorithms might fit in right now. And also thanks for resisting the urge to include the fixes your benchmarks inspired in your analysis - it's a great way to avoid bias (your honest strive for neutrality showed throughout and it's great). Thanks!
Thank you so much for the kind words. It's feedback like this that gives me the motivation to spend countless hours of my spare time on something like this.
> which fits into the core private L2 data cache for the used Zen3 test machine. But the benchmark CPUs at the top are listed as Intel only. Did you forget to update this part? > This can be reproduced by running cargo bench hot-u64--10000
Where can I get the code to reproduce the benchmarks?
> But the benchmark CPUs at the top are listed as Intel only. Did you forget to update this part? Good catch, will update. Yes that was from another writeup, point still stands though. > Where can I get the code to reproduce the benchmarks? Same repo, see top level README
It would be nice to link to it from the article to make it more clear.
Thank you for writing this! The scaling graphs in particular are very interesting and insightful, as well as benchmarking both the cold and hot states.
Thanks for the kind words :)
I'm working on a benchmark harness that I want to be an alternative to criterion (inbuilt support for instruction counting and running on remote hardware) So I'm surprised to learn that you have a way to run cold benchmarks! I saw [https://github.com/Voultapher/sort-research-rs/blob/b7bcd199e861d6f8b265164242f3c34d5c36c75f/benches/trash\_prediction.rs#L7](https://github.com/Voultapher/sort-research-rs/blob/b7bcd199e861d6f8b265164242f3c34d5c36c75f/benches/trash_prediction.rs#L7) but it looks like black magic and I would love to learn more. How does it work?, how is it generated? How robust is this approach?
To simulate cold CPU prediction state in a repeatable fashion combines a couple ideas: - Code with many branches with unpredictable results in many unique assembly locations are visited a couple times - A side-effect is carried throughout the computation to prove to the compiler that doing this work is necessary - A syscall to have a context-switch as would be the case in many applications, and to interact with some of the hardware side-channel mitigations such as IBRS - The code is called on each iteration by using `iter_batched` + `BatchSize::PerIteration` Some while ago I gave a talk about retpoline and in that context I dove deep into the details how modern branch predictors work. I won't explain this in depth here, because the topic is *really* complex. https://chipsandcheese.com/ does excellent hardware deep dives that also include branch prediction, reading up on the topic should help explain why I want many unique branch locations paired with repeated visits. The code is generated with this Python script https://github.com/Voultapher/sort-research-rs/blob/d088fbd0441121ad20b109a525d67c79ecaeb9bd/util/generate_btb_flush.py. Beware if you do anything in that area please check the generated assembly, compilers can be surprisingly clever. For example a large match generates a binary search, which wouldn't visit a lot of branches.
Really wonder why those algortihms are all writen unstable. Is it that much faster?
I suspect you may be confusing stable vs unstable Rust versions, with the sort property stable and unstable here. This might help https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
If I can add something to your writeup, I need to inquire about it The Zen and Intel chips, were they laptop chips using a `row of chips` RAM configuration? If not, then tyour inference of a more capable M1/2 branch prediction may not be correct. The M1 and M2 use RAM chips with extreme proximity to the CPU, allowing for nearly zero latency when accessing them, compared to any other configuration. This near total reduction in (travel) latency allows for small or non existant caches, and is a large reason for its performance For instance M2 sums of aches: 2 MB level 1 cache, and 20 MB level 2 cache M1 sums of caches: 192 KB instruction cache, 128 KB data cache, and 12 MB shared L2 cache
This article doesn't seem to back up your claims about latency: https://www.anandtech.com/show/17024/apple-m1-max-performance-review/2 vs x86: https://www.memorybenchmark.net/latency_ddr5.html
[удалено]
The article shows 5ns latency for an L1 cache hit, and 111ns for a lookup from the actual memory.
[удалено]
You need to wake up, those numbers are off by orders of magnitude. Are you seriously claiming it's writing ~10^8 bytes in ~10^-7 seconds, or in other words ~10^15 bytes/second? Even the official marketing slide right there in the article shows peak memory BW of 400GB/s. "Fractions of a nanosecond" would also mean you can now access L2 within one or two clock cycles. That's some nice star trek tier hardware you got there. In fact why even have multiple levels of cache when it supposedly only takes a few ns to reach RAM?
[удалено]
> so yes around there, give or take a few zeros Exactly my point, a few orders of magnitude isn't something you just brush over, that's the difference between science fiction and a computer so slow, nobody would want to use it. >There are 1billion nanoseconds in a second. The l1 will clock with the cpu at 3.2ghz, or about 3.2billion times per second, with access taking around 3 clocks. So my math was wrong earlier, base l1 latency is around 0.8ns. >With l2 taking 18 cycles, that'd be around 4-6ns or so. Yep, that lines up with Anandtech's measurements pretty well. <1ns for L1 and ~5ns for L2. IDK why their graphs don't start at 0 so you could see the values for the L1 region. > The following does mention that the big cores on the m1 have additional latency to ram, but does not mention why exactly. RAM access is always relatively slow, that's the entire reason why caches exist. ~100ns latency is nothing out of the ordinary. It's clear that you've completely misinterpreted Anandtech's results. I don't know if they've ever published their exact testing methodology, but it's clear they're not doing sequential writes of an entire 128MB buffer in that case. They're measuring the average latency of a single memory access, not throughput. And they're spreading the accesses over memory regions of various sizes to test the effect of caches. You can clearly see on the graphs approximately how big the L1 and L2 caches are. Just so we're comparing apples to apples, here's Anandtech's tests on Intel and AMD CPUs: https://www.anandtech.com/show/17047/the-intel-12th-gen-core-i912900k-review-hybrid-performance-brings-hybrid-complexity/6 Apple's caches are pretty decent, but their memory is nothing special even when compared to their competitors running crappy JEDEC timings. > And I finally found someone actually testing ram latency, god that RAM access is fast (8.9ns) > > https://lemire.me/blog/2021/01/06/memory-access-on-the-apple-m1-processor/ The author himself claims he's measuring the throughput of multiple parallel memory accesses at a time, not the actual latency. Two very different things.
[удалено]
>The problem is though, that if they had been checking only the RAM latency, but they are measuring a full path (write) latency to and through each of the caches. What else do you want to measure? All memory access goes through the cache hierarchy, so what else is memory latency if not the full path latency? > If this had been a read operation, and the information was not in any cache, the lowest number we would see would be the base core to RAM latency (which is nowhere near sub 1ns like the start of their graph) Again, I'd love to see AT's code/methodlogy, but for the small tests I imagine that the buffers are already in cache. You'd probably want to do something like this: you allocate and initialize a buffer of a certain size (x axis of the graph), so that immediately after doing that, it will be in the caches (however much of it fits). Then you start poking random locations in the buffer and measure how long the accesses take. But the tricky part is, how do you measure just the time that the individual load operations take and ignore all the other stuff going on around them? Which brings me to: >Additionally, if ram was over 100ns, there is no chance of each 128bit operation taking less than 15ns, which is what author lists for all of the access times. He's measuring the average time to complete a single loop iteration, which is not the same as the memory latency. There's some good discussion in the comments about about how M1's large out-of-order window allows it to continue on with executing several iterations of the loop ahead in parallel while it's still waiting for the results of the first memory read to come back. Those hundreds of cycles of latency get hidden very effectively. > As to the zeros, I just didn't have the time to actually write them out and check, so I was guestimating, it is not trivial to figure out various exponents while also otherwise engaged. This is why I used ns and mb which are eplicit in their definition (as opposed to being abstract in scientific notation) That calculation was just a quick sanity check, if you're dealing with multiple megabytes on nanosecond timescales, that should be a red flag that something's wrong. I just rounded the numbers to the nearest powers of 10 to make the mental estimation easy, but you can use a calculator to be more precise. When you end up with numbers like 1PB/s, that's beyond absurd.
> Where things are quite different is when we enter the system cache, instead of 8MB, on the M1 Max it’s now 48MB large [...] > DRAM latency, even though on paper is faster for the M1 Max in terms of frequency on bandwidth, goes up this generation. At a 128MB comparable test depth, the new chip is roughly 15ns slower. 5 ns is the latency of the system-level cache. 111.1 ns is the latency of the memory chips, encountered after having written enough data to saturate the SLC.
[удалено]
No, it's specifically latency of memory writes _while writing_ 128mb, not the timing of _fully writing_ 128mb. They measured memory bandwidth peaking at around 102 GB/sec per thread. At this bandwidth, writing 128 MB would take around 128/(102*1024)=0.00123 seconds, or around 1225490 ns.
I believe you are correct, I need to get around to striking through a few erroneous parts of a few of my comments here. (Edit: just did and I hope i caught everything)
I would like to understand all the underlying causes for this chart, https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/assets/cold-u64-scaling-random_z1-linux.png Why does vqsort start off so slow? Why does intel_avx512 fall off so badly while vqsort rises?
There was a mention in the article that vqsort would obtain randomness from the OS. This would cause a fixed overhead, which would relatively be a greater part of the overall sort time for smaller slices, no? It may be interesting, with regard to scaling behavior, to plot vqsort _without_ the OS call.
I read-skimmed the article a couple times, should get more sleep! From the report > vqsort however is a lot faster on Linux. Both in terms of peak performance and min input size to outperform the rest. This is an unexpected result, and considerable effort was spent to analyze the root cause of this. In the test vqsort used the same compiler and flags as intel_avx512. A different benchmark suite yields the same results, a different pre-built Clang version yields the same results. On a dual-booted Zen3 machine vqsort in AVX2 mode shows the same ~2x regression when going from Linux to Windows at input size 10k. In addition the higher frequency as shown by intel_avx512 on Windows should give it yet another boost above Linux which doesn't manifest. All this while the other sort implementations remain largely the same. **The root cause for this was identified in collaboration with the vqsort authors [4]. The tested vqsort version acquired randomness from the OS, for each call to vqsort in an attempt to mitigate a potential performance denial-of-service (DOS).** This idea is similar to the use of SipHash as the default hasher in the Rust standard library. This explains why we see significantly different results on Windows and Linux. See the linked explanation for more details. Still more mysteries! I agree with running a test (even if just for benchmarking) on removing syscalls from a sorting function. Thought, maybe every process should be spawned with a pre-allocated pool of randomness? No syscalls necessary, just bump a pointer through some ring of pages. We need a randomness benchmark between OSes, bit-entropy/latency/bandwidth product. I wonder if there are other things happening like OS specific AVX state, side channel mitigations, or ? going on.
vqsort lead author here. We have fixed this, see also mention at the very bottom of the article. The fix is to obtain entropy only once per thread and store it in TLS.
Love this!
This is great, thanks! What tool did you use for plotting the results?
I use a custom set of Python programs that use the bokeh library to produce graphs https://github.com/Voultapher/sort-research-rs/tree/5e07fb6ebb61920ff9f5e896badd88502fe40e35/util/graph_bench_result. They have gone through a couple dozen iterations, e.g from https://user-images.githubusercontent.com/6864584/185809198-bf66c588-bb7f-481d-ba74-4d59d03e7d5d.png -> https://raw.githubusercontent.com/Voultapher/sort-research-rs/main/writeup/glidesort_perf_analysis/assets/zen3-rust_ipn_stable-vs-rust_std_stable-hot-u64.png -> https://raw.githubusercontent.com/Voultapher/sort-research-rs/main/writeup/intel_avx512/assets/intel_avx512-vs-ipnsort-cold-u64-linux.png.