3 ms·

Hang on, you can't just quote MB/s numbers for an O(n log(n)) sort. What length were these tests run at? The code size might not end up quite as good (also req

Hang on, you can't just quote MB/s numbers for an O(n log(n)) sort. What length were these tests run at? The code size might not end up quite as good (also requires malloc), but a branchless merge sort is a contender for a fast and lightweight sort. Just published, tiny-sort-rs[0] cites 632 bytes and looks like ~350MB/s at 1e4 elements on Zen 3. In my tests, my own pisort[1] benches a little over twice as fast as LongSort, but it uses sorting networks as the base case so it's like 5KB. It's roughly based on piposort[2] which has more complicated recursion but a simpler base case. 400 MB/s seems a bit slow for a radix sort on that hardware: I'm hitting those numbers on my i5-6200U, which has less than half the clock rate, with my own radix sort. Recommend checking ska_sort_copy from [3] as it has about the same performance. [0] https://github.com/Voultapher/tiny-sort-rs https://github.com/Voultapher/tiny-sort-rs [1] https://github.com/mlochbaum/SingeliSort/blob/master/src/merge.singeli#L136-L152 https://github.com/mlochbaum/SingeliSort/blob/master/src/mer... [2] https://github.com/scandum/piposort https://github.com/scandum/piposort [3] https://github.com/skarupke/ska_sort https://github.com/skarupke/ska_sort

mlochbaum 3y ago
Just realized that obviously you don't need stability if you're using in-place quicksort, so the tiny-sort heapsort is a better recommendation. 304 bytes, although the scaling to large arrays is much worse because of the awful access patterns.
jstanley 3y ago
> What length were these tests run at? The first example is "assembly code they published for sorting an array with three items" - this isn't an entire general-purpose sorting algorithm, it's just the innermost part.
- mlochbaum 3y ago
  Second part of the article, starting at "I thought it'd be useful to share something that's actually portable and executable".
- srcreigh 3y ago
  The alpha dev post claims 1.7% improvement on large sequences (250k+)
  - refulgentis 3y ago
    Yes, and as both posts say, that’s because large sequences are implemented by building up from small sequences :)
Paul-Craft 3y ago
> ...632 bytes... 5KB... How much does code size matter here? As long as the code has a good access pattern that maintains cache locality, is there any fundamental difference between 632 bytes and 5KB? L1 cache sizes are generally somewhere around 16-64 KB these days, so it seems like there wouldn't be a big difference here. Or am I just totally off base?
- foota 3y ago
  I think the benefit is that when you start getting inlined code you can have multiple copies of it, so it can multiply out, and ideally you always want your code to be as small as possible so that you can have fewer instruction cache misses. So it's unlikely to matter if you're calling a single function in a loop whether the code is 632 bytes or 5KB (well, instruction decoding throughput aside I suppose), but when you're looking more broadly it might matter.
- mlochbaum 3y ago
  longsort appears in cosmopolitan libc, and possibly gets embedded in all the output executables? For most applications the requirements are much less restrictive. I'm working on sorting for interpreted programming languages; I see >20KB for each sort now and don't have a problem with that. For small arrays only a fraction of the code will be used. I still make some effort to reduce size, but if you're doing HPC work where sorting matters you can go much bigger with sorting networks for every size of something like that. icache is 32KB/core on every processor I've checked, although it's often reported weird. But it's fine for a hybrid sort targetting large arrays to exceed that because many components like partitioning will spend their time running on lots of data, so the time to load is relatively insignificant.
- jart 3y ago
  > L1 cache sizes are generally somewhere around 16-64 KB these days, so it seems like there wouldn't be a big difference here. Would you want to depend on a C library that claims all 64kb of your L1 cache for itself? Of course not. You'd want to use a library that stays out of the way, so that your code can be the one exploiting system resources.
- 3y ago

mlochbaum 3y ago

Just realized that obviously you don't need stability if you're using in-place quicksort, so the tiny-sort heapsort is a better recommendation. 304 bytes, although the scaling to large arrays is much worse because of the awful access patterns.

jstanley 3y ago

> What length were these tests run at? The first example is "assembly code they published for sorting an array with three items" - this isn't an entire general-purpose sorting algorithm, it's just the innermost part.

mlochbaum 3y ago
Second part of the article, starting at "I thought it'd be useful to share something that's actually portable and executable".
srcreigh 3y ago
The alpha dev post claims 1.7% improvement on large sequences (250k+)
- refulgentis 3y ago
  Yes, and as both posts say, that’s because large sequences are implemented by building up from small sequences :)

Paul-Craft 3y ago

> ...632 bytes... 5KB... How much does code size matter here? As long as the code has a good access pattern that maintains cache locality, is there any fundamental difference between 632 bytes and 5KB? L1 cache sizes are generally somewhere around 16-64 KB these days, so it seems like there wouldn't be a big difference here. Or am I just totally off base?

foota 3y ago
I think the benefit is that when you start getting inlined code you can have multiple copies of it, so it can multiply out, and ideally you always want your code to be as small as possible so that you can have fewer instruction cache misses. So it's unlikely to matter if you're calling a single function in a loop whether the code is 632 bytes or 5KB (well, instruction decoding throughput aside I suppose), but when you're looking more broadly it might matter.
mlochbaum 3y ago
longsort appears in cosmopolitan libc, and possibly gets embedded in all the output executables? For most applications the requirements are much less restrictive. I'm working on sorting for interpreted programming languages; I see >20KB for each sort now and don't have a problem with that. For small arrays only a fraction of the code will be used. I still make some effort to reduce size, but if you're doing HPC work where sorting matters you can go much bigger with sorting networks for every size of something like that. icache is 32KB/core on every processor I've checked, although it's often reported weird. But it's fine for a hybrid sort targetting large arrays to exceed that because many components like partitioning will spend their time running on lots of data, so the time to load is relatively insignificant.
jart 3y ago
> L1 cache sizes are generally somewhere around 16-64 KB these days, so it seems like there wouldn't be a big difference here. Would you want to depend on a C library that claims all 64kb of your L1 cache for itself? Of course not. You'd want to use a library that stays out of the way, so that your code can be the one exploiting system resources.
3y ago