4 ms·
10x Faster sort than C++ std:sort
- mc4ndr3 4y ago100x faster: Don't sort.
- janwas 4y agoFair :) Sorting is useful in DB joins/group-by, though. (Author here, happy to discuss.)
- hypertele-Xii 4y agoAt first glance seems like a snarky dismissal, but this is actually valid, actionable advice. If you can arrange your data flow in such a way that sorting is unnecessary, you've avoided an expensive optimization problem altogether.
- bradknowles 4y agoNo sorting is faster than no sorting.
- williamkuszmaul 4y agoImpressive! There are already implementations of sample sorting that are much faster than c++ sort (but I don't recall how much faster). I'd be very interested in a comparison to some of those... Also, since we are sorting integers, I'd also be interested to know how well a modern implementation of radix sort can be made.
- janwas 4y ago:) Are you thinking of ips4o (sample sort)? That's about 2-3x std::sort. There's also a pending patch to std::sort that replaces it with BlockQuicksort which would narrow that gap. We integrate vqsort into ips4o, calling it once subarrays fit in L2. That speeds up ips4o by 2.9x (single thread) and 1.6 (parallel - bandwidth limited). More details in the paper. I previously also worked on radix sort: https://arxiv.org/abs/1008.2849 https://arxiv.org/abs/1008.2849 Interestingly, that 12 year old result on dual-socket/8 cores is only about twice as fast as a single AVX-512 core today.
- janwas 4y agoAlso discussed here: https://news.ycombinator.com/item?id=31622548 https://news.ycombinator.com/item?id=31622548