It's kind of insane that such an obvious optimization can be patented, I have to imagine that it has been invented independently dozens if not hundreds of times.
Nothing in this slop means anything particularly, but this detail is extra-wrong considering the variety of processors that the inventor says he used to create this algorithm.
Second, I have independently invented this (quicksort on strings with prefixes) at my time at CWI, although I didn't end up publishing it, because...
Third, this was already published in the original 1961 Quicksort paper by Hoare: https://www.cs.ox.ac.uk/files/6226/H2006%20-%20Historic%20Qu.... Near the end, the section on "Multi-word keys" describes a quicksort that partitions on just the first word, and only accesses the next word for the equality partition.
So as is usual, this patent never should have been awarded.
> A CPU register is naturally 8 bytes in size, and if Oracle extracts 8 bytes from two strings for comparison, then the comparison requires fewer registers and fewer CPU cycles.
Isn't this just a typical SIMD optimization that tons of projects use?
14 comments
[ 4.7 ms ] story [ 46.2 ms ] threadI think this is inventors blog https://smalldatum.blogspot.com/2026/01/common-prefix-skippi...
Thanks for sharing.
What does naturally even mean here. How is a 64 byte register's (zmm0) size any less natural?
Second, I have independently invented this (quicksort on strings with prefixes) at my time at CWI, although I didn't end up publishing it, because...
Third, this was already published in the original 1961 Quicksort paper by Hoare: https://www.cs.ox.ac.uk/files/6226/H2006%20-%20Historic%20Qu.... Near the end, the section on "Multi-word keys" describes a quicksort that partitions on just the first word, and only accesses the next word for the equality partition.
So as is usual, this patent never should have been awarded.
With one sentence per line.
Most annoying.
For wasting my time.
The only thing someone could learn from this is that CPU registers can be 8 bytes.
Isn't this just a typical SIMD optimization that tons of projects use?