Skylinesort | Hacker News Reader

Skylinesort

skylinesort.com

62 pointsdaniel-cussen27 comments

Skylinesort is a novel sorting algorithm that sorts integer keys. It outperforms current sorting algorithms when keys are clustered (not uniformly randomly distributed). I showed it to some profs at Stanford, and might publish it formally.

It sorts in time O(ku-ulog(u)+n), where k is the number of bits in each key, u is the number of unique elements, and n is the total number of elements.

How does that compare with Radix sort? Isn't Radix O(kn)? I guess Skyline would be better if the number of unique elements are low?

Skylinesort appears to beat radix sort when the data is clustered, as it caches better, which is especially true when the number of unique elements is low.

The other thing about it that's better is that Skylinesort is the only sorting algorithm that is downward-concave, i.e. it takes less time to sort a list of size a (keeping clustering constant) than it takes to sort two lists of size a/2. In other words, it shows economies of scale. It has been a long-remarked paradox that sorting algorithms take longer per element when there's more elements.

I haven’t read this in detail, but a few things stand out. In the write up, you say it compares better than bitwise radix sort. You need to compare against an optimized byte-wise radix sort which is by far the fastest sort for decent sized arrays of integers. The second claim that skyline sort somehow sorts an array of size a faster than two arrays of size n does not make sense. That implies that the time per element goes to zero as the size goes to infinity. That would be faster than O(n), which is what radix sort is, i.e. constant time per element for larger arrays.

It sounds like this is just a variation of counting sort or bucket sort optimized for a small number of unique values.

I know I need to compare it head to head against bytewise radix sort. I might do that and get back with the results. In the meantime, let me clarify. EDIT: Blas Mena and I did test it against radix sort, you can find it https://github.com/daniel-cussen/skylinesort/blob/master/src..., it tests with 4-bit radix sort and radix sort comes out 3% slower.

When I say that it can sort an array of size 2n faster than two arrays of size n it is because if you plot the asymptotic time, you find it's second derivative is negative (concave-up). This is because of the subtraction in the asymptotic time, O(k u - u log u + n). A Stanford professor was reluctant to accept an asymptotic time with a subtraction in it, but I explained it was really the logarithm of a division, ku-ulogu was actually u log(K/u) where K is 2^k, the total number of elements in the empty auxiliary array. log(K / u) is the same as log K - log u and log(K)=k, so you end up with k u - u log u, which has a negative second derivative when k is fixed.

When log u = k, skylinesort does indeed run in linear time, but it runs slower that linear time before that, and log u is never greater than k, by definition.

Daniel also addressed this some, but I want to highlight that sorting one array of size 2n faster than two arrays of size n does not imply per element time decreasing to zero. E.g. if the runtime were n-2^(-n) you would have that property even though the per element runtime tends toward 1.

<rant> That kind of phenomenon (reading too far into an infinite process) is ubiquitous once you start noticing it. Infinitely many universes don't imply the existence of every possible universe (if you subscribe to such theories), pie having infinitely many digits doesn't imply that it encodes every possible message somewhere in those digits (most real numbers have that property, but iirc it's still an open question for pi), and so on. </rant>

I am fairly certain this is the fastest method available https://sorting.cr.yp.to/index.html

That algo is fast as hell, that much is true.

I have not made SIMD optimizations, which djbsort includes, and skylinesort does not require pre-computing the merging network, or padding the array to that size. This works great for crypto where array sizes are known ahead of time and generally always the same, but not all use cases are like this.

You seem to require the auxiliary array to be initialized to zero. This costs O(2^k).

Second, consider this line.

> Otherwise we keep traveling to the left until we are able to make another leap.

Wouldn't sorting an array with the two elements 2^n and 2^(n+1)-1 require ~2^n repeats of this step? That's a second 2^k cost.

Overall this is just counting sort with skips, but for that I'd imagine it's cheaper to just use a bit array to track set elements, which also makes zeroing much faster.

Yes, the original auxiliary array has to start out being zero, but it is returned in that same state, so this algo can be run over and over again without ever having to reinitialize the entire array in O(2^k).

When there's 2^n and 2^(n+1)-1, it takes n-2 steps to reach the former from the latter, not 2^n.

OK, I got it after reading the code. It's a neat trick, but you never actually explain how it works (even the comment says ‘this part I'm confused about’ lol).

I think I know what you mean. There is a step in the logic that, in a staircase metaphor, is uneven, it's a larger gap than the other steps, and also like a real staircase, you either make that step or you don't. I have yet to find a way to explain it. Personally, I can't always understand it, and don't know how I know it, and can't put my finger on what the leap is.

Why make a website and a domain name before getting peer review to check for mistakes?

Since when has being a mistake prevented people from making a website and a domain name (and acquiring funding)?

I did a fair amount of that, but there was a lack of interest because it's just a sorting algorithm. Sorting is considered dead as a field, it's basically solved.

So I don't really understand this after reading the explanations.

1. You claim to have explained the height of the sticks "later". Maybe you had it explained in one of the paragraphs, but I just don't see it.

2. In the diagram that is supposed to illustrate the left sweeping part, it has fancy windows and doors but doesn't have anything to explain why the lines are drawn that way. The home page animation also didn't give me any insight on how that part is supposed to work.

Stack height just visualises the repeated transition function for "next spot to jump to". You don't have to compute the stick heights and do searches, just execute p <- (p | (p + 1)) & MASK for a "right horizontal line". This transition is more simply explained as "set the least significant 0 bit". The important thing is that each successive jump is at least double the size of the previous one, which intuitively gives you the log2 in the worst case complexity. There is a paragraph on right skipping, but not left skipping.

For left skipping AKA "gather", what you're trying to do is log-skip across contiguous zeroes in the auxiliary array. So you skip bigger and bigger regions until you hit a nonzero spot. I'd have to think a bit more to prove that you do actually hit the next number, but the visualisation of the transitions should get you in the ballpark: the tall sticks tend to get numbers written under them by the lesser sticks to their left, and when you are skipping from the right, you tend to hit the tall sticks.

The explanation doesn't mention it, but the left-skips are defined as p <- (((p+1) & p) - 1) & MASK. This is also simply explained: "clear any contiguous 1s pinned to the least significant end, then subtract 1 to create more 1s" e.g.:

    1100 1100 (      =204)
    1100 1011 (-1,   =203)
    1100 0111 (-4,   =199)
    1011 1111 (-8,   =191)
    0111 1111 (-64,  =127)
    1111 1111 (-128, =255, wrapped)

So the "buildings" get wider as you go, until you hit another nonzero spot, and you start drawing thin buildings again because you start from the element to its left, whose binary representation ends with 11*0.

The bitwise ops are the key to understanding why you can draw the sticks at those heights: for each index i, simply draw to height = 1 + the # of trailing 1s in i. Many trailing ones makes for bigger jumps in either direction. So the wide buildings are also tall.

Thanks so much for this great, novel explanation.

You have my permission to use it if you like!

Thanks for sharing this. Often sorting algorithms in practice end up being glommed into a Swiss Army knife style sort function to avoid pathological cases. E.g for smaller inputs just use insertion sort, but swap to a different sort of you know the size, etc. it’s pretty common in standard libraries (I think). So I am curious: are any pathological cases for skyline sort?

Well, it requires a ton of (virtual) memory for [0, 1e9], so much you can't do it on 32-bit machines. If you can figure out that a particular quicksort/etc subproblem has a pretty small abs(max-min), then cool, go for it, but try to reuse the allocations for other subproblems.

With this memory issue, it's not a general purpose sort, nor does it have subproblems that you can defer to other sorts, so you wouldn't be able to use it as a default in those "glomsorts" anyway. So plugging pathological gaps is a bit irrelevant.

It definitely requires a ton of virtual memory, and yes, you can't do 32-bit word sorting on 32-bit machines. There's actually a use case involving 24-bit words where the number of occurrences of each word doesn't matter, and where they necessarily start to cluster after each iteration. So there is a use case (I might add it's tailor-made for this use-case). But you can still e.g. sort database keys which might only have a 26-bit maximum, and it'll take advantage of any clustering that exists in the data, like if in a log you get some customers appearing more often than others, or more frequently in streaks. It also works great when your data is in ranges and you don't want to manually account for this: this will skip that entire empty range in logarithmic time. (Example, all your keys are between 1000-1100 and 5000-6000. The empty range 1100-4999 will be traversed in like 12 steps.)

The pathological case for skylinesort is the optimal case for quicksort: uniformly randomly distributed data. In this case skylinesort is 3-4x slower than quicksort. It's still not like the pathological case of quicksort, which takes quadratic time: it's an effectively log-linear worst case.

My advice is to use skylinesort when you have or can have tons of empty memory and have clustered data. Clustered means there's repetition of data points or they are in some ranges more than others. But in practice whenever your data isn't uniformly randomly distributed, skylinesort is better.

Is this cache friendly on a modern cpu? On the face of it, it seems to be quite cache unfriendly.

I was surprised to find that it is, especially if the data is clustered. What ends up happening is the elements near the top of the bracket get cached so they can usually be accessed quickly.

Note that if your data is uniformly randomly distributed the caching will hurt and it will be slower than quicksort, as this is quicksort's optimal use case.

How does this differ from a pigeonhole sort?

It is a type of pigeonhole sort. The benefit is you can use a much greater number of pigeonholes because you don't have to check them all when collecting your entries.

That's the benefit of skylinesort: you can skip huge ranges of empty pigeonholes.

Reply on news.ycombinator.com