Hacker News Reader

Comment by ridiculous_fish | Hacker News Reader

A lovely way to sort strings, especially strings that may have long shared prefixes, is a 3-way partition quicksort. This allows you to avoid walking the same prefix over and over the way that memcmp does.

Pick your pivot element and partition the strings into <, =, and > based on the first character only. Note this differs from classic quicksort in that we're maintaining three regions, not two. Now recurse for all three regions, except for the = region you look at the second character only. etc.

It's probably a loss for filenames which tend to be short, but for long strings this is a very easy to implement speedup. There's lots more optimizations possible with this technique, e.g. counting-sort style bucketing.

View on HN

That's a cool algorithm.

The improvements in the article look pretty small between different versions because CPU time is dominated by system calls that are out of my control. If you look at userspace CPU only, the speedup between v1 and v5 is 15x. In other words, the final version uses 15 times less CPU time in userspace. It also uses less CPU in the kernel, but the improvement there isn’t as dramatic (just the openat vs open optimization).

If some clever sorting optimization could yield infinite speedup and would optimize away all loop counters and pointer arithmetics, the overall performance of ListDir v5 would only increase by 3%. v5 is basically all kernel code, there is almost nothing left to optimize algorithm-wise.

That's a nice idea. Do you know of any programs that use this?

I know that CPython treats hash tables with string keys as a special case, for performance. I wonder if it might also make sense to treat sorting lists of strings as a special case (or maybe it already does, I will check ...).

Hm yeah it looks like Python's timsort is meant to minimize the number of comparison operations (see Objects/listsort.txt). But it doesn't try to make the comparisons themselves cheaper. That would break the interface to some extent, i.e. it doesn't really fit within the model.

Interesting to think about though!

> There's lots more optimizations possible with this technique, e.g. counting-sort style bucketing.

:) I was going to say that since you are half re-inventing bucket-sort anyway, why not go the whole hog.

Is the code three-part quicksort simpler and easier to understand than a bucket sort?

That's interesting, it's effectively doing a radix sort but in a more scalable way.

Would reversing the strings or writing a custom comparer to compare in reverse be simpler and get to the more significant bits quicker? You could maybe even do the file extension comparison at a later point.

what about symbol trees ?

/a/b/c/d/e => {a,b,c,d,e} symbol table + [a,b,c,d,e]

and you accumulate into a tree/trie

Tries/trees have pointers which can be slow, so I’d measure before using something like this.

Reply on news.ycombinator.com