Updating fluxsort/quadsort?

[mlochbaum]

In my benchmarks for Robin Hood Sort, I used the wolfsort benchmark as a baseline, not realizing that the versions of quadsort and fluxsort here are now very out of date. So my chart has some misleading comparisons. And with current versions it's hard to build everything at once because wolfsort relies on the older fluxsort interface.

Would you mind updating this repository, or do you have advice on another way to run my benchmarks? If you won't have time in the next few days, let me know and I'll find some hack to get them updated. I can also probably PR code updates, I just can't redo the graphs.

[mlochbaum]

Another comment, you can see on the graph at the bottom that wolfsort's cutoff of 1024 looks much too high. I think this comes from testing on the same data repeatedly: fluxsort gets an unrealistic advantage because (I assume) its branches on various subarray sizes are predicted much better. In my average benchmarks I advance the start position by 1 each time, which removes a dip in fluxsort under ~3e3 resulting in that gap at the cutoff.

And nice work on quadsort by the way!

[mlochbaum]

Here's my line graph with updated quad/flux (wolfsort still using old versions), and the cutoff removed. ska_sort_copy has its own cutoff problem, which obviously I didn't touch.

[scandum]

Nice work. I'll try to have the wolfsort benchmark fully updated in about 6 hours. I'll also take a look at the cut-off.

[scandum]

I've updated the source code. Couple of new things:

blitsort: updated from a rotate mergesort to a rotate quick/merge sort
crumsort: new in-place unstable branchless quicksort using a novel unstable partitioning scheme
fluxsort: updated to use faster pivot selection and benefits from quadsort improvements to small array sorting
gridsort: benefits from quadsort changes and does well on very large arrays
quadsort: updated to use branchless parity merges
wolfsort: now uses fluxsort as the fallback and quadsort for small array sorting

I'll put up some graphs in a little bit.

[mlochbaum]

Thanks, I've updated my benchmarks to match. Will be investigating crumsort, although it looks like it's not different enough from flux to add yet another bar to the RH chart (and the stable sort makes more sense for comparison anyway). Exciting though! I've been thinking I can make LSD radix sort in-place (well, constant 1KB or something) as a base case for ranges under 2^16, by collapsing the elements to 2-byte, radix sorting back and forth in the freed half, and expanding again. I'll probably end up using crumsort as the outer part for that experiment.

[scandum]

As far as I can tell crumsort pulls ahead of fluxsort at 1M+ elements, undoubtedly due to being in-place.

I'll definitely be taking a closer look at RH, the performance looks spectacular. Wolfsort seems to be running about 33% faster on my machine than yours for 100K elements.

Using the trie approach on a radix sort definitely sounds interesting.

[mlochbaum]

That makes sense about crumsort on larger arrays. So a crumsort → fluxsort pathway to cut down memory use to a small fraction of the input array would be sensible. And it looks like fulcrum partition doesn't obliterate patterns in the way pdqsort does, is that right?

I think my biggest conclusion from working with RH was actually that radix sort is a lot better that I realized (most implementations out there are awful). The adaptiveness of RH is nice, but that comes with a lot of inconsistency. I've just tested what I think is the worst case of a single huge element, and small random numbers otherwise. It degrades to 70-90ns/v on medium-length arrays. Although all but 30ns or so is from my terrible merge, and using quadsort (without even skipping up to the block size) brings it to more like 45-65ns. I think I can do better by trying to skip blocks within merges as well.

Radix sort is actually better than it looks on the bar chart in my opinion. The bad cases are from cache associativity as I analyzed here, and completely disappear for small arrays. And a 2-byte sort is more than twice as fast.

Counting sort is way faster than either: that's what RH uses on the Random%100 test. Admittedly a best case due to the very small range, but with the right implementation (tricky) it stays near that performance even for ranges a little above the length. This is what I did when implementing Dyalog APL's sorting algorithm, although I think I can improve it with a threshold strategy slightly similar to RH: only keep the count mod 16, appending the value to an overflow list whenever that rolls over. Then sort the overflow list, and write the mod 16 part branchlessly, and any overflow using branching.

[scandum]

I haven't checked for pattern obliteration, I think fulcrum will leave large sorted ranges mostly intact.

As for memory use, blitsort is very good when provided with 4 * sqrt(n) of aux. It's slightly faster than flux at 10M elements with 32768 aux.

I'm very impressed with RH, admittedly Wolfsort is mostly a hack job, an experiment with a radix / comparison hybrid with the radix part being very primitive. I may go back to the drawing board sometime and see if I can come up with something better.

I've been thinking about using fluxsort to partition down to 10K elements to deal with 1M+ sized arrays. So far I've had little luck getting counting sort to run fast on 64 bit integers.

[scandum]

I checked out your link and have some suggestions.

I did quite a bit of research on binary searching. I developed the monobound binary search which is up to 4 times faster than the standard binary search you discuss. I also wrote a monobound_bsearch() routine for complex data. I did some work on interpolation and adaptive binary searches as well.

I'm not sure if binary searches can be considered branchless like you seem to indicate.

Tree sorts seem to be missing, possibly because you don't consider them performant, but gridsort is showing some promise. I personally tend to make a distinction between bottom up and top down sorts, and I categorize tree sorts as a bottom up quick / partition sort. As gridsort shows adaptive partitioning is possible from the bottom up, though performance is a challenge.

Rotations are interesting as a form of in-place partitioning. I did some work on that as well, with rotations becoming relevant once you make them fast enough.

All in all a pretty useful article.

[mlochbaum]

Did you read the linked pvk article? As far as I can tell monobound_binary_search in binary_search.c performs the same arithmetic (e.g. &base[half] corresponds to bot + mid). It's branchless if the conditional assignment of base/bot is performed with a cmov, and it's usually not hard to arrange things so the compiler does that. There's a branch for the loop of course, but it's perfectly predictable as the length is constant.

[scandum]

I had not read the pvk article, the code is indeed functionally identical.

[mlochbaum]

Added proper quadsort integration (description), and I get the following worst case, fairly reasonable.

Also figured out that it's trivial to use RH as the first pass of a merge sort, which with quad merging is faster than fluxsort on random numbers up to 1e7. Fluxsort as the outer part should be better of course.

[mlochbaum]

I did the packed 2-byte radix thing (or trie strategy), and put the code in this repository. Performance is very good: around 6ns/v for ranges below 2^16 and lengths from ~100 to 2^16, plus the standard <1ns/v for each partition to get there. With only 2KB for the counts. Competitive with ska_sort_copy on large arrays for ranges below about 2^18. Lots of other distribution sorts to be added if swap space is available, but that was the only in-place one that seemed promising.

[scandum]

The worst case looks manageable. I've been labeling sorts as adaptive if random or bit-reversal is the worst case, and as semi-adaptive if there are exceptions.

As for tail_merge not working out, it's not so great for small ranges, quadsort should be fairly optimal if you have a bucket size of 32 elements.

I wrote up my own little blurb about the optimal range for radix sort:

https://github.com/scandum/wolfsort#setting-the-bucket-size

I should probably have written L2 instead of L1 cache, though I assume it's actually both that play a role, and might explain the square root access time you make mention of? In all honesty, I'm just making guesses since I don't have a full understanding of the subject. Fluxsort seems pretty much cache oblivious in your graph.

Counting sort definitely has my attention now, I assume 64 bit processors have turned it from a relatively useless 1/2 byte sort into a much more relevant 4 byte sort?

I have some code written to get the min and max in the analyzer with fairly minimal performance loss. I might do some thinkering with crumsort to improve generic data detection. I do have working run detection in my local fluxsort that significantly improves ascending tiles and might have a small benefit for generic as well.

size_t FUNC(flow_analyze)(VAR *array, size_t nmemb, VAR *min, VAR *max, CMPFUNC *cmp)
{
        char loop, dist;
        size_t cnt, balance = 0, streaks = 0;
        VAR *pta, *ptb, swap;

        pta = array;

        *min = *max = pta[nmemb - 1];

        for (cnt = nmemb ; cnt > 16 ; cnt -= 16)
        {
                for (dist = 0, loop = 16 ; loop ; loop--)
                {
                        if (cmp(min, pta) > 0) *min = *pta; else if (cmp(pta, max) > 0) *max = *pta;

                        dist += cmp(pta, pta + 1) > 0; pta++;
                }
                streaks += (dist == 0) | (dist == 16);
                balance += dist;
        }

        while (--cnt)
        {
                if (cmp(min, pta) > 0) *min = *pta; else if (cmp(pta, max) > 0) *max = *pta;

                balance += cmp(pta, pta + 1) > 0;
                pta++;
        }

        if (balance == 0)
        {
                return 1;
        }