3 ms·
It would be interesting to see it benchmarked against the highway qsort[1] Google published last year. [1] https://github.com/google/highway/tree/master/hwy/co
by posnet 4y ago
It would be interesting to see it benchmarked against the highway qsort[1] Google published last year.
[1] https://github.com/google/highway/tree/master/hwy/contrib/sort https://github.com/google/highway/tree/master/hwy/contrib/so...
- janwas 4y agosagarm has posted one result in another thread. I'll also look into adding their code to our benchmark :) It's great to see more vector code, but caveat for anyone using this: the pivot sampling is quite basic, just median of 16 evenly spaced samples. This is will perform poorly on skewed distributions including all-equal and very few unique values. Yes, in the worst case it can resort to std::sort but that's a >10x speed hit and until recently also potentially O(N^2)!. We have drawn larger samples (nine vectors, not one), and subsequently extended the vqsort algorithm beyond what is described in our paper, e.g. special handling for 1..3 unique keys, see https://github.com/google/highway/blob/master/hwy/contrib/sort/vqsort-inl.h#L1311 https://github.com/google/highway/blob/master/hwy/contrib/so....
- janwas 4y agoI've posted bench_sort results in another thread. vqsort is about 1.8 times as fast for uniform random 32/64-bit.