5 ms·

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 p

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.

agumonkey 8y ago
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
- saagarjha 8y ago
  Tries/trees have pointers which can be slow, so I’d measure before using something like this.
romka2 8y ago
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.
Robin_Message 8y ago
That's interesting, it's effectively doing a radix sort but in a more scalable way.
adrianratnapala 8y ago
> 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?
chubot 8y ago
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!
flukus 8y ago
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.

agumonkey 8y ago

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

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

romka2 8y ago

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.

Robin_Message 8y ago

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

adrianratnapala 8y ago

> 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?

chubot 8y ago

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!

flukus 8y ago

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.