5 ms·

I recently upgraded fluxsort, you might want to give v1.1.5.4 a spin. I also updated the benchmark to use actual natural runs and be less favorable to rhsort, s

I recently upgraded fluxsort, you might want to give v1.1.5.4 a spin. I also updated the benchmark to use actual natural runs and be less favorable to rhsort, sorry. ;-) I'm not surprised fluxsort is slightly faster, it's heavily optimized for gcc -O3. Since the primary techniques that give glidesort it's speed were copied from fluxsort and quadsort I'm expecting very similar performance, and possibly significantly worse performance on strings due to accessing 4 memory regions. Have you gotten it working with the wolfsort benchmark?

mlochbaum 4y ago
I did actually test out 1.1.5.4 in advance of this. I just used saved results instead of the new version for comparison because performance appears very similar on random inputs. I do see a lot of improvement in quadsort and most of the special-case benchmarks. I was planning to update my repository to grab the appropriate files from the fluxsort repository but if you'd update the wolfsort repo I wouldn't have to. Although maybe I should switch over to cloning fluxsort instead.
- scandum 4y ago
  I'm planning to update wolfsort soon-ish. I did some work on a dropsort hybrid, like rhsort, though it's slower overall because I'm not quite brave enough to match the level of insanity (I mean this in a good way) that rhsort engages in. The latest fluxsort is probably identical on random, the new analyzer might perform slightly better on modern hardware. Probably safer to stick with wolfsort as I do tend to make sure that works with rhsort when I update.
- scandum 4y ago
  I went ahead and updated bench.c for the wolfsort github.
  - mlochbaum 4y ago
    I get an error about goto small_range_test jumping over a lot of declarations. If I remove that goto/label, it all works very nicely, just have to link rhsort and modify sorts. Thanks!
    - scandum 4y ago
      That code was indeed a bit unorganized, I updated bench.c in wolfsort's github, hopefully that'll fix it. Would you mind giving your 2 cents on this topic? https://news.ycombinator.com/item?id=34650406 https://news.ycombinator.com/item?id=34650406 You are probably more familiar with this topic than most. It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts. Similarly, orlp suggests there is no relationship between his branchless merge and quadsort's branchless merge. On his github he mentions timsort 2 times, and powersort 5 times. So he has no problem giving prior credit, but at least to me, it appears he tries to take prior or co-inventor claim for quadsort's branchless merge techniques and suggests a minimal influence from fluxsort. There is also no mention of the massive performance gain by utilizing the unguarded aspect of quadsort's parity merge for small array sorting. This is at least 20% of glidesort's performance gain. Perhaps I'm being overly sensitive?
      - orlp 4y ago
        > It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts. So what is the relationship then, in your eyes? I implemented my own branchless partition operator that switches between overwriting / cmov'ing depending on data size (https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/stable_quicksort.rs#L157 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb...), my own bidirectional partitioning scheme, my own pivot selection scheme, my own low-cardinality scheme based on my prior work. As I wrote before "fluxsort's out-of-place stable partitioning. From this I got reminded that not only is out-of-place stable partitioning a thing, it's highly competitive". This is also what I credit on my page: "credit to Igor van den Hoven's fluxsort for demonstrating that stable quicksort can be efficient in practice". And glidesort isn't a quicksort, it is truly a hybrid. > Similarly, orlp suggests there is no relationship between his branchless merge and quadsort's branchless merge. I implemented it from scratch (10+ different versions), myself: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/branchless_merge.rs#L176 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... You can still see artifacts of all the things I've tried there as well as in the select function: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/util.rs#L16 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... I was confident branchless merging could work efficiently. You could say quadsort contributed to the confidence it would work. But I did not use your branchless merge, period. > So he has no problem giving prior credit, but at least to me, it appears he tries to take prior or co-inventor claim for quadsort's branchless merge techniques and suggests a minimal influence from fluxsort. I will edit the readme to explicitly mention that glidesort's bidirectional merging is inspired by and an extension of quadsort's parity merge. But you didn't invent the branchless merge, and neither did I. We both came up with our own versions, both after the "Branch Mispredictions Don't Affect Mergesort" paper. > There is also no mention of the massive performance gain by utilizing the unguarded aspect of quadsort's parity merge for small array sorting. This is at least 20% of glidesort's performance gain. It's not 20%, at least on my machine. This optimization is precisely what the `--features unstable` flag enables, because this optimization is not sound to do for non-Copy types (and thus needs specialization in Rust). So it's easy to test, for me it's a 11% speedup over the branchless guarded merge: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/branchless_merge.rs#L201 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... Yes, I also made the guarded merge branchless. I don't believe quadsort does that, because it doesn't have to deal with elements that may not be copied. You can see the different selection of code based on specialization here: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/small_sort.rs#L193 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb...

mlochbaum 4y ago

I did actually test out 1.1.5.4 in advance of this. I just used saved results instead of the new version for comparison because performance appears very similar on random inputs. I do see a lot of improvement in quadsort and most of the special-case benchmarks. I was planning to update my repository to grab the appropriate files from the fluxsort repository but if you'd update the wolfsort repo I wouldn't have to. Although maybe I should switch over to cloning fluxsort instead.

scandum 4y ago
I'm planning to update wolfsort soon-ish. I did some work on a dropsort hybrid, like rhsort, though it's slower overall because I'm not quite brave enough to match the level of insanity (I mean this in a good way) that rhsort engages in. The latest fluxsort is probably identical on random, the new analyzer might perform slightly better on modern hardware. Probably safer to stick with wolfsort as I do tend to make sure that works with rhsort when I update.
scandum 4y ago
I went ahead and updated bench.c for the wolfsort github.
- mlochbaum 4y ago
  I get an error about goto small_range_test jumping over a lot of declarations. If I remove that goto/label, it all works very nicely, just have to link rhsort and modify sorts. Thanks!
  - scandum 4y ago
    That code was indeed a bit unorganized, I updated bench.c in wolfsort's github, hopefully that'll fix it. Would you mind giving your 2 cents on this topic? https://news.ycombinator.com/item?id=34650406 https://news.ycombinator.com/item?id=34650406 You are probably more familiar with this topic than most. It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts. Similarly, orlp suggests there is no relationship between his branchless merge and quadsort's branchless merge. On his github he mentions timsort 2 times, and powersort 5 times. So he has no problem giving prior credit, but at least to me, it appears he tries to take prior or co-inventor claim for quadsort's branchless merge techniques and suggests a minimal influence from fluxsort. There is also no mention of the massive performance gain by utilizing the unguarded aspect of quadsort's parity merge for small array sorting. This is at least 20% of glidesort's performance gain. Perhaps I'm being overly sensitive?
    - orlp 4y ago
      > It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts. So what is the relationship then, in your eyes? I implemented my own branchless partition operator that switches between overwriting / cmov'ing depending on data size (https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/stable_quicksort.rs#L157 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb...), my own bidirectional partitioning scheme, my own pivot selection scheme, my own low-cardinality scheme based on my prior work. As I wrote before "fluxsort's out-of-place stable partitioning. From this I got reminded that not only is out-of-place stable partitioning a thing, it's highly competitive". This is also what I credit on my page: "credit to Igor van den Hoven's fluxsort for demonstrating that stable quicksort can be efficient in practice". And glidesort isn't a quicksort, it is truly a hybrid. > Similarly, orlp suggests there is no relationship between his branchless merge and quadsort's branchless merge. I implemented it from scratch (10+ different versions), myself: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/branchless_merge.rs#L176 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... You can still see artifacts of all the things I've tried there as well as in the select function: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/util.rs#L16 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... I was confident branchless merging could work efficiently. You could say quadsort contributed to the confidence it would work. But I did not use your branchless merge, period. > So he has no problem giving prior credit, but at least to me, it appears he tries to take prior or co-inventor claim for quadsort's branchless merge techniques and suggests a minimal influence from fluxsort. I will edit the readme to explicitly mention that glidesort's bidirectional merging is inspired by and an extension of quadsort's parity merge. But you didn't invent the branchless merge, and neither did I. We both came up with our own versions, both after the "Branch Mispredictions Don't Affect Mergesort" paper. > There is also no mention of the massive performance gain by utilizing the unguarded aspect of quadsort's parity merge for small array sorting. This is at least 20% of glidesort's performance gain. It's not 20%, at least on my machine. This optimization is precisely what the `--features unstable` flag enables, because this optimization is not sound to do for non-Copy types (and thus needs specialization in Rust). So it's easy to test, for me it's a 11% speedup over the branchless guarded merge: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/branchless_merge.rs#L201 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... Yes, I also made the guarded merge branchless. I don't believe quadsort does that, because it doesn't have to deal with elements that may not be copied. You can see the different selection of code based on specialization here: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb01d0f9bfba5c8e365e9/src/small_sort.rs#L193 https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb...