The unreasonable effectiveness of modern sort algorithms

Post by Eddy_Viscosity2 » Wed, Sep 17, 2025, 12:08 PM UTC

Imnimo wrote: post #31

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…

Just be careful you aren't doing the classic, "my linear regression works way better when I independently sort the inputs and targets"!

But this one weird trick is crazy effective, if you value chart aesthetics over meaningfulness, which I do. My charts look great.

Post by akoboldfrying » Fri, Sep 19, 2025, 9:53 AM 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.

You're right about memory movement, not sure what I was thinking.

Re: The unreasonable effectiveness of modern sort algorithms

Re: The unreasonable effectiveness of modern sort algorithms