scandum

Blitsort is a hybrid quicksort, see title.

It is slower than it's unstable brother, aptly named crumsort. https://github.com/scandum/crumsort

Quadsort, fluxsort, blitsort, and crumsort all qualify depending on your needs.

skasort_cpy is pretty good on 32 bit integers if you give it n auxiliary memory.

rhsort is very good and likely the best for 31 bit integers, but a bit rough around the edges still, and doesn't work well on arrays above 1M elements. Avoid radix sorts for 64 bit integers, they're ideal for 16 bit.

glidesort is promising, though I haven't seen it benched against the latest fluxsort / blitsort.

Timsort's main problem is that it's slow on shuffled arrays.

pdqsort and other introsorts aren't good on semi-ordered data.

>A nitpick, but my name is Orson Peters

I actually knew that, not sure what went wrong in my brain.

>I don't know, I only use a binary search when splitting up merges, and almost no time is spent in this routine.

You'll still get a definite speed-up, worth benching the difference just in case. I guess there's no easy way to avoid a binary search.

>I didn't do specific research into which effect it is, when I say ILP I also mean the memory effects of that.

They're indeed related. I did some empirical testing and I'm quite sure it's cache related. Thinking about it, one issue I may have had was not benching sorting 100M elements, which might be where a bidirectional partition might benefit on my system.

I'm not that interested as I'd prefer to count each move and prove it that way, but perhaps Peter (orlp) is interested?

Isn't that what Rust is all about?

Hard to answer. I think the main thing is that there are a lot of stumbling blocks, things that most people overlook, yet logical once you have it explained.

Occasionally one is discovered and solved, and it can lead to a brief domino effect, but I have no idea how many are left.

It's possible to implement a 64 item stack so you can call it O(1) and in-place.

But that's such an effort in futility that I refuse to do so. So it's theoretically and practically in-place, but not technically.

Hoi Peter,

>I have a similar conjecture for glidesort but I'll have to do some thinking to see if I can prove it.

It probably is technically O(n (log n)^2) moves, but I suspect that when the rotations are fast enough (trinity / bridge rotations) the cost saving from localization nullify the additional moves.

>I do cite you in the presentation in the section on ping-pong merges

Wikisort does have prior claim to ping-pong merges, and it likely goes further back than that. I did independently implement them in quadsort.

>I do also cite you for what you call parity merges (something I did not use at the time of the presentation

This feels like a tricky claim to me, since I assume your bidirectional merge was fully inspired by my parity merge. If so you weren't the first to implement one, I did so while working on the parity merge, but I figured it was self-evident the 2x gain would apply for a more traditional merge, and I did state the gain was from accessing two memory regions in the quadsort article.

I've since made a quadsort release that uses a galloping 'bidirectional merge', though it still takes advantage of the parity principle, so properly speaking it's a bidirectional galloping parity merge hybrid that sorts 2 blocks of 8 elements at a time, without boundary checks for the 16 merge operations.

>As you could notice, I didn't have a large time slot for my presentation

I did take that into account, I guess it's human nature to get butthurt over stuff like this and I couldn't help myself from whining a little. It is better than bottling it up and I apologize if I caused you unease in turn.

>Hopefully this does show my good intent

It does, and I appreciate it.

>That said, glidesort does not use a branchless binary search.

I assume that's one of the advantages of building upon powersort? The blocky nature of quadsort is both a blessing and a curse in that regard.

>I call my partitioning method bidirectional partitioning.

I meant "parity merge" / "partition". If you think about it quicksort is naturally bidirectional, which is why branchless partitioning works without further work, and undoubtedly why it wasn't self-evident to most. I did try to write a bidirectional partition early on, but it's either my hardware or I messed up somehow.

I agree it's possible to write a bidirectional merge without utilizing the parity principle. One of the trickiest things in programming is properly naming things.

As for instruction-level parallelism, I do think it's actually almost entirely memory-level parallelism. I could be wrong though.

It should be O(n log n) comparisons and technically O(n (log n)^2) moves. The moves are reduced by a relatively large constant however, and blitsort might qualify as O(n log n) moves when given sqrt(n) aux.

In your Youtube presentation you do seem to skip mentioning that many of the performance innovations in glidesort were derived from quadsort and fluxsort. Some credit in your upcoming paper would be much appreciated. Feel free to email me if you have any questions, some things like my first publication of a "branchless" binary search in Aug 2014 may be hard to find, though there might be prior claim.

~4.5 times faster than std::stable_sort for uniform random integers is pretty impressive. Is this primarily from increasing the memory regions from 2 to 4 for parity merges / partitions? I'm benching on somewhat dated hardware and had mixed results (including slowdowns), so I never went further down that rabbit hole.

Main reasons for not benching against pdqsort:

1. stability 2. worse performance on long doubles, and I don't know why 3. A variety of hard to explain performance differences. 4. pdqsort does better on generic data, which can be very important.

So it's tricky to present a fair benchmark when two sorts behave very differently.

As to performance advantages of fluxsort:

1. It has a faster insertion sort. 2. Branchless pseudomedian of 15 gives an advantage. 3. Partial loop unrolling with: while (ptx + 8 < pte) 4. Data movement should be nearly identical, if not better, with the recursive calls through the ptx pointer. In the optimal case the memcpy only triggers when the partition shrinks below 24 elements, and in half of those cases the partition will already be in main memory.

So on random you could expect n / 2 extra data movements on top of ~ n log n moves.

The graph is with //#define cmp(a,b) ((a) > (b)) in quadsort.h uncommented.

Looking forward to your next spin.

You can uncomment

    //#define cmp(a,b) (*(a) > *(b))

in quadsort.h for primitive inline comparisons.

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

As for the ptx pointer's use, I'm not aware of a prior implementation.

As for selective benchmarking, that's a selective accusation.

I updated the README slightly, it's mentioned twice now. :)

As for performance considerations, blitsort's performance on integers is indicative of its performance on strings, while this isn't the case for pdqsort.

I haven't ran a specific benchmark, but I assume that on string data blitsort will beat pdqsort for every metric except random with many equal items.

Correct, if you uncomment

  //#define cmp(a,b) (*(a) > *(b))

in blitsort.h it'll run about 25% faster. Probably still slower than a native C++ implementation since it'll evaluate to (a > b) > 0 rather than (a > b), not sure if the compiler will optimize that.

It is, those numbers are less favorable than they are on my own machine.

The speed of your RAM memory is likely to have an influence on performance. My system is running at 2133MHz.

Hard to say which would be faster, I've made a mental note to benchmark sorting 16 byte long doubles through pointers as well as directly.

I never tried, but it should be possible (and relatively easy) to add custom sizes in the .h file.

Given how fast pdq is there's indeed no reason not to adopt it. Probably the usual 'not invented here' mindset.

Well, blitsort's performance is exceptional in the sense that it's 15% faster than the next fastest stable in-place sort.

As for stability, it's useful when you need to sort a table with an integer index. So it might be of value to database software.

I probably should point out some of the weakness on the README.

Agreed on pdqsort being 3x slower worst case on "killer" input, but it's my understanding that's why it's not being used to replace std::sort.

As for runs of 50, haven't benched those, though I assume gridsort (https://github.com/scandum/gridsort) would handle those rather well.

Blitsort can sort strings, but something like a 12 byte data structure would require an array with pointer references to sort.

As for the degradation against std:stable_sort:

5% slower at 1 million, 10% slower at 10 million, 20% slower at 100 million.

With sqrt n auxiliary you're looking at 2%, 4%, 6% slower.

Against qsort() it remains faster at 10 million, 3% slower at 100 million.

pdqsort isn't stable and still suffers from killer inputs.

Not sure how well this will paste:

      Name |    Items | Type |     Best |  Average |     Loops | Samples |     Distribution
  -------- | -------- | ---- | -------- | -------- | --------- | ------- | ----------------
  blitsort |   100000 |   32 | 0.005962 | 0.006532 |         1 |     100 |     random order
   pdqsort |   100000 |   32 | 0.002665 | 0.002802 |         1 |     100 |     random order
           |          |      |          |          |           |         |
  blitsort |   100000 |   32 | 0.000069 | 0.000078 |         1 |     100 |  ascending order
   pdqsort |   100000 |   32 | 0.000098 | 0.000100 |         1 |     100 |  ascending order
           |          |      |          |          |           |         |
  blitsort |   100000 |   32 | 0.001138 | 0.001196 |         1 |     100 |    ascending saw
   pdqsort |   100000 |   32 | 0.003245 | 0.003317 |         1 |     100 |    ascending saw
           |          |      |          |          |           |         |
  blitsort |   100000 |   32 | 0.003777 | 0.003843 |         1 |     100 |    generic order
   pdqsort |   100000 |   32 | 0.000819 | 0.000851 |         1 |     100 |    generic order
           |          |      |          |          |           |         |
  blitsort |   100000 |   32 | 0.000051 | 0.000060 |         1 |     100 | descending order
   pdqsort |   100000 |   32 | 0.000202 | 0.000207 |         1 |     100 | descending order
           |          |      |          |          |           |         |
  blitsort |   100000 |   32 | 0.000815 | 0.000845 |         1 |     100 |   descending saw
   pdqsort |   100000 |   32 | 0.002307 | 0.002368 |         1 |     100 |   descending saw
           |          |      |          |          |           |         |
  blitsort |   100000 |   32 | 0.001761 | 0.001774 |         1 |     100 |      random tail
   pdqsort |   100000 |   32 | 0.002560 | 0.002572 |         1 |     100 |      random tail
           |          |      |          |          |           |         |
  blitsort |   100000 |   32 | 0.003328 | 0.003374 |         1 |     100 |      random half
   pdqsort |   100000 |   32 | 0.002651 | 0.002854 |         1 |     100 |      random half
           |          |      |          |          |           |         |
  blitsort |   100000 |   32 | 0.000593 | 0.000938 |         1 |     100 |  ascending tiles
   pdqsort |   100000 |   32 | 0.002316 | 0.002482 |         1 |     100 |  ascending tiles

Might be worth noting that it's faster than quicksort, std::stable_sort, and timsort.

It broke my heart, but I got rid of the quirky mars condition.

OneWeb will be worse than fiberoptics while Starlink will be better than fiberoptics.

This suggests OneWeb is pretty much doomed to fail.

How does it perform against googlebtree?

https://www.tommyds.it/doc/benchmark

The incubation time is too long and too random.

The only option is to delay the spread and inject people with a deactivated carona vaccine as soon as possible, which should stop half the population from getting it, and reduced lethality for those who do get it.

Bit of a shameless plug, but yet another alternative is VTON, though it is typeless.

https://github.com/scandum/vton

It's the equivalent of talking to an AI chatbot that pretends to be a dungeon master.

I was amused for about 15 minutes after which I got bored.

It might work if it was used to allow two players to engage in combat.

If I read the article in the worst possible way it suggests the hybrid capacitor stores 260 Wh/kg and produces 300 W/kg.

The Tesla battery stores 272 Wh/kg and produces 207 W/kg.

So this suggests the hybrid capacitor would charge 1.4 times faster.

Next question is the price, the article doesn't give a straight-forward answer other than that it's significantly more expensive. In theory (no hard proof) the hybrid capacitor would last longer.

Regardless, a promising development.