[scandum]

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]

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]

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]

I went ahead and updated bench.c for the wolfsort github.

[mlochbaum]

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]

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

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?

[mlochbaum]

Oh, what are you complaining about? I got 1-byte counting sort running at <1ns/element down to 1,000 elements and no one will even rip me off!

I don't particularly feel that contributions from fluxsort and quadsort are being minimized in Orson's writing/speaking. The talk in May and README are both pretty abbreviated and the places you should expect full attribution are the FOSDEM talk and upcoming paper; first looks good. We all tend to think of our own work as more important than it really is. And to overlook differences and assume it's more similar to other work.

I haven't looked into quadsort deeply and still haven't had any time to seriously read glidesort, so I can't comment on the details of merge implementations. The places I see influence are in merging 4 arrays at a time (which I did read about before quadsort in "Patience is a virtue", but I think neither I nor Orson took that paper very seriously) and in the bidirectional idea which is credited in the FOSDEM talk.

[scandum]

It is said that getting ripped off is the highest form of flattery.

The FOSDEM talk indeed addressed my worries.

I actually don't see the ping-pong merge as a personal accomplishment, it's not that novel a concept, at best I popularized it. The actual performance gain from it is minimal, maybe 1%, though that is perhaps the most interesting thing, that data moves are practically free. And I would like to take full credit for that observation!! :-)

[orlp]

> 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/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/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/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/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/56cacab4e378e75ab6feb...

[scandum]

I've just watched your FOSDEM presentation and to put it simply, thank you for addressing all the issues I had.

I felt pretty uneasy about what I perceived as a situation where you could end up taking full credit for innovations I was first to develop and publish. I do realize this could be all in my head. Anyways, I'm at ease now and I hope my assertions didn't create any ill will between us.

As for your arguments, they're pretty sound and I find no reason to doubt you. It was never my intention to appear dismissive towards your work, writing glidesort was no easy matter and the merge routines are a significant improvement upon Timsort/Powersort.