4 ms·

This is BlockQuicksort with stable partitioning, pumped up with selective benchmarks (if I sound irritated about this, it's because I've just called out the aut

This is BlockQuicksort with stable partitioning, pumped up with selective benchmarks (if I sound irritated about this, it's because I've just called out the author[0] on this exact issue). I understand that worse performance should be expected for a stable sort, but what possible reason is there to leave out benchmarks against the most closely related algorithm? Worse, a stable version of BlockQuicksort is pointless, which is to say that it is actually impossible for there to be a practical use case for Fluxsort. The branchless partitioning technique is relevant only if comparison doesn't depend on branching, which means the input array needs to consist machine-native types, and in fact Fluxsort limits itself to integers and long double. On these inputs stability isn't an observable property! The result of Fluxsort will be indistinguishable from that of any other quicksort (okay, I guess it will keep negative and positive zeros in the original order for floats, but an integer-based comparison could also accomplish this). So all you get is a slower sort that uses more memory. There are use cases for stable partitioning, such as sort-by or arg-sort, but as written Fluxsort can't do these. The statistical method to decide whether to use quicksort or Quadsort—checking the ratio of comparisons between adjacent pairs of elements that are smaller versus greater—is really interesting. It applies to the mergesort versus quicksort problem in general. The use of the ptx pointer is definitely not novel and I think it's a stretch to even describe it as a brain-twister. It's the obvious way to do branchless stable partitioning. This is good work! It's well-written and well-explained, and clearly points in the direction of practical applications. However, it's presented in a way that suggests that it's a good drop-in sorting algorithm, when instead it's more of a research effort. Beware! [0] https://news.ycombinator.com/item?id=27793636 https://news.ycombinator.com/item?id=27793636

scandum 5y ago
I get the impression you wrote your response rather hastily. Here's a bench of fluxsort vs pdqsort on strings: | Name | Items | Type | Best | Average | Compares | Samples | Distribution | | --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- | | fluxsort | 100000 | 64 | 0.011804 | 0.012044 | 2003293 | 100 | random string | | pdqsort | 100000 | 64 | 0.012423 | 0.012512 | 1859192 | 100 | random string | If you can sort strings you can sort tables, where stability matters. Here's a graph of relative performance on 100K 32 bit integers. https://media.discordapp.net/attachments/737457171377160203/868645661871046696/unknown.png https://media.discordapp.net/attachments/737457171377160203/... As for the ptx pointer's use, I'm not aware of a prior implementation. As for selective benchmarking, that's a selective accusation.
- mlochbaum 5y ago
  Gah, I did misunderstand some things. The picture is now worse than I realized! EDIT: and yet also better; see https://news.ycombinator.com/item?id=27951017 https://news.ycombinator.com/item?id=27951017 . It's hard to get it working right but this is a really fast algorithm. fluxsort takes a function pointer and has no way to inline it. The fluxsort.c is included from fluxsort.h (this is not standard style by the way; template files should have a .h suffix), so the compiler might choose to inline it, and the benchmarks use noinline on the comparison functions to avoid this. BlockQuicksort makes no sense without inlined comparisons. Yes, pdqsort allows a comparison function in order to be a general-purpose sort, but this isn't the case that it targets. Are these benchmarks run with inline comparisons? Seems pretty hard to get bench.c to inline anything since test_sort takes a comparison function as input (though I'm working on it).
  - acmj 5y ago
    My biggest complaint about all scandum's sorting algorithms is that it doesn't support guaranteed inlined comparisons. Without this feature, the result depends on the compiler behavior, making the results hard to interpret. This point has been raised many times at reddit/hacker news but the dev is strong minded.
  - scandum 5y ago
    You can uncomment //#define cmp(a,b) (*(a) > *(b)) in quadsort.h for primitive inline comparisons.
- mlochbaum 5y ago
  Got the benchmarks working with a hardcoded 4-byte int pdqsort. pdqsort is of course faster, but this doesn't tell us anything about how good fluxsort really is because it doesn't inline the comparison (I've removed __attribute__ ((noinline)) and comparisons++ as bench.c suggests, which improves the speed but doesn't inline it). | Name | Items | Type | Best | Average | Loops | Samples | Distribution | | --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- | | qsort | 100000 | 32 | 0.013530 | 0.013901 | 1 | 10 | random order | | fluxsort | 100000 | 32 | 0.004837 | 0.005009 | 1 | 10 | random order | | pdqsort | 100000 | 32 | 0.003661 | 0.003745 | 1 | 10 | random order | Your graph doesn't show how fast pdqsort orders 4-byte integers. It shows how fast it orders them when required to use a comparison function, which is an arbitrary restriction and not what pdqsort is designed for.
mlochbaum 5y ago
Okay, with scandum's prodding I've looked into this more deeply and need to add much more context. Firstly, I was very much wrong and apologies are in order. What I wrote was based on the assumption that Fluxsort trades speed for stability. It doesn't, apparently: the partitioning seems to be faster and also stable. Possibly more so than the benchmarks show. It's a crude measure, but I ran perf top during benchmarks, and pdqsort spent significantly more time in its partition than Flux did in its own. So the only real drawback is O(n) rather than O(log(n)) memory usage. Memory's cheap, although I guess some users will decide this isn't acceptable. A fast partition that happens to be stable is great to have. The in-place scheme used by pdqsort has one advantage, which that it naturally puts reverse-sorted data in order. Other than that it tends to mangle everything. Stable partitioning doesn't do this, and might even be able to draw out order from interleaved sequences that a merge sort (or insertion sort) could later take advantage of. BlockQuicksort uses a fast index generation method to produce indices for elements that are then swapped. Fluxsort skips all this and moves an element to both possible positions immediately; it then uses the comparison result to increment one partition index allowing the other position to be overwritten. It's the simpler organization of stable partitioning that allows this to be fast. There's also some cleverness in not immediately moving the second partition to put it after the first, but instead partitioning it from where it sits. I've looked into stable partitioning, and I know branchless algorithms well enough that I could have written this. But I didn't!

scandum 5y ago

I get the impression you wrote your response rather hastily. Here's a bench of fluxsort vs pdqsort on strings: | Name | Items | Type | Best | Average | Compares | Samples | Distribution | | --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- | | fluxsort | 100000 | 64 | 0.011804 | 0.012044 | 2003293 | 100 | random string | | pdqsort | 100000 | 64 | 0.012423 | 0.012512 | 1859192 | 100 | random string | If you can sort strings you can sort tables, where stability matters. Here's a graph of relative performance on 100K 32 bit integers. https://media.discordapp.net/attachments/737457171377160203/868645661871046696/unknown.png https://media.discordapp.net/attachments/737457171377160203/... As for the ptx pointer's use, I'm not aware of a prior implementation. As for selective benchmarking, that's a selective accusation.

mlochbaum 5y ago
Gah, I did misunderstand some things. The picture is now worse than I realized! EDIT: and yet also better; see https://news.ycombinator.com/item?id=27951017 https://news.ycombinator.com/item?id=27951017 . It's hard to get it working right but this is a really fast algorithm. fluxsort takes a function pointer and has no way to inline it. The fluxsort.c is included from fluxsort.h (this is not standard style by the way; template files should have a .h suffix), so the compiler might choose to inline it, and the benchmarks use noinline on the comparison functions to avoid this. BlockQuicksort makes no sense without inlined comparisons. Yes, pdqsort allows a comparison function in order to be a general-purpose sort, but this isn't the case that it targets. Are these benchmarks run with inline comparisons? Seems pretty hard to get bench.c to inline anything since test_sort takes a comparison function as input (though I'm working on it).
- acmj 5y ago
  My biggest complaint about all scandum's sorting algorithms is that it doesn't support guaranteed inlined comparisons. Without this feature, the result depends on the compiler behavior, making the results hard to interpret. This point has been raised many times at reddit/hacker news but the dev is strong minded.
- scandum 5y ago
  You can uncomment //#define cmp(a,b) (*(a) > *(b)) in quadsort.h for primitive inline comparisons.
mlochbaum 5y ago
Got the benchmarks working with a hardcoded 4-byte int pdqsort. pdqsort is of course faster, but this doesn't tell us anything about how good fluxsort really is because it doesn't inline the comparison (I've removed __attribute__ ((noinline)) and comparisons++ as bench.c suggests, which improves the speed but doesn't inline it). | Name | Items | Type | Best | Average | Loops | Samples | Distribution | | --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- | | qsort | 100000 | 32 | 0.013530 | 0.013901 | 1 | 10 | random order | | fluxsort | 100000 | 32 | 0.004837 | 0.005009 | 1 | 10 | random order | | pdqsort | 100000 | 32 | 0.003661 | 0.003745 | 1 | 10 | random order | Your graph doesn't show how fast pdqsort orders 4-byte integers. It shows how fast it orders them when required to use a comparison function, which is an arbitrary restriction and not what pdqsort is designed for.

mlochbaum 5y ago

Okay, with scandum's prodding I've looked into this more deeply and need to add much more context. Firstly, I was very much wrong and apologies are in order. What I wrote was based on the assumption that Fluxsort trades speed for stability. It doesn't, apparently: the partitioning seems to be faster and also stable. Possibly more so than the benchmarks show. It's a crude measure, but I ran perf top during benchmarks, and pdqsort spent significantly more time in its partition than Flux did in its own. So the only real drawback is O(n) rather than O(log(n)) memory usage. Memory's cheap, although I guess some users will decide this isn't acceptable. A fast partition that happens to be stable is great to have. The in-place scheme used by pdqsort has one advantage, which that it naturally puts reverse-sorted data in order. Other than that it tends to mangle everything. Stable partitioning doesn't do this, and might even be able to draw out order from interleaved sequences that a merge sort (or insertion sort) could later take advantage of. BlockQuicksort uses a fast index generation method to produce indices for elements that are then swapped. Fluxsort skips all this and moves an element to both possible positions immediately; it then uses the comparison result to increment one partition index allowing the other position to be overwritten. It's the simpler organization of stable partitioning that allows this to be fast. There's also some cleverness in not immediately moving the second partition to put it after the first, but instead partitioning it from where it sits. I've looked into stable partitioning, and I know branchless algorithms well enough that I could have written this. But I didn't!