The unreasonable effectiveness of modern sort algorithms

Post by Sesse__ » Mon, Sep 15, 2025, 5:28 PM UTC

throwaway81523 wrote: post #35

lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

I spent many years as a programmer somehow avoiding ever doing much with databases, since most problems that seemed to want databases could instead be solved using sorting batch-collected data.

Post by Voultapher » Mon, Sep 15, 2025, 5:46 PM UTC

Sesse__ wrote: post #24

akoboldfrying wrote: post #21

Your "Branchless" approach could indeed be implemented very efficiently in a CPU with AVX2 (256-bit-wide vectors). With the current element in rax, the 4 valid values in ymm2, and the 4 running totals in ymm3 (initially zero), the inner loop would be just: VPBROADCASTQ rax,ymm1 VPCMPEQQ ymm1,ymm2,ymm1 VPADDQ ymm1,ymm3,ymm3 VPBROADCASTQ copies rax into each of the 4 lanes in ymm1. The VPCMPEQQ sets each qword there to…

“Memory movement”? None of the instructions you list involve memory. I find the perfect hash implementation a bit weird; it seems to obfuscate that you simply look at the lowest two bits (since they differ between the four values). You can do the x + 3 and 3 - expr at the very end, once, instead of for every element.

Post by Voultapher » Mon, Sep 15, 2025, 7:07 PM UTC

Epa095 wrote: post #5

Double jaw-drop. First when the (dynamic) match was slower than the hash map, second when sort_unstable was faster than the hash map! Cool article. It's clear that all my theoretical algorithm-knowledge comes short when faced with real CPUs.

Post by ekelsen » Mon, Sep 15, 2025, 10:16 PM UTC

Voultapher wrote: post #52

ekelsen wrote: post #28

Wouldn't it make sense to test radix sort? You could do it in one pass with 2 bits and it would degrade gracefully as the number of bits increased. A MSB bucketing followed by LSB passes would take care of the 5% random data case with good efficiency.

radsort a radix sort is present in the comparison results.

Post by Voultapher » Tue, Sep 16, 2025, 6:55 AM UTC

ekelsen wrote: post #57

Voultapher wrote: post #52

Earlier quoted context omitted.

radsort a radix sort is present in the comparison results.

hmmm, the performance suggests it's not a particularly good implementation of one. (performance at sizes that fit in the cache being lower than performance that exceed it...) Also the statement in the text is just false ("Radsort is a radix sort and as such unable to adapt to patterns in the data") MSB absolutely can adjust quite easily. Even LSB can pay some attention. And hybrid like I suggested (use MSB to bucket…