Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The unreasonable effectiveness of modern sort algorithms

github.com

Post reply on HN
Print view View original

21–30 of 62 posts

Re: The unreasonable effectiveness of modern sort algorithms

#21

Post by akoboldfrying »

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 all-0 ( = 0) or all-1 ( = -1) depending on the comparison result, so the VPADDQ will accumulate 4 running negative totals into ymm3, which can be negated afterwards.

I would still expect the perfect hash function approach to be faster, though -- a similar number of operations, but 25% of the memory movement.

Re: The unreasonable effectiveness of modern sort algorithms

#22

Post by rcxdude »

kwertyoowiyop wrote: post #17
creata wrote: post #11

Earlier quoted context omitted.

"The Unreasonable Effectiveness of Mathematics in the Natural Sciences" is one of those titles that gets imitated a lot for some reason. Maybe even more than "Goto Considered Harmful".

Coming next: “What we talk about when we talk about modern sort algorithms”

or "we need to talk about what we talk about when we talk about the unreasonable effectiveness of title memes are all you need considered harmful"

Re: The unreasonable effectiveness of modern sort algorithms

#23

Post by bob1029 »

akoboldfrying wrote: post #19
bob1029 wrote: post #8

I find in practice that if the sorting process is too slow, you should begin thinking about different ways to attack the problem. Maintaining a total global order of things tends to only get more expensive over time as the scope of your idea/product/business expands. The computational complexity of the sort algorithm is irrelevant once we get into memory utilization. This is why we have things like tournament selecti…

I don't yet see how tournament selection could work here, could you explain? Sometimes when you think you need to maintain a sorted array under item insertion, it turns out that you only ever need to continually read the next-smallest (or next-largest) item -- and in that case, it suffices to maintain a heap , which is much cheaper.

An example would be an evolutionary algorithm that relies on a large population to maintain diversity. As you get into 6-7 figure population size, ranking the whole set starts to take a really long time (relatively speaking) each iteration. This also requires a serialized phase of processing that halts all workers for the duration.

With tournament selection, you can randomly pick indexes from the population to build tournaments, which is effectively instant. There is no more requirement for a serialized processing phase. All processors can build their own random tournaments and perform updates of scores. There will be occasional conflict on score updates but the idea is that with enough samples/iterations it becomes very accurate.

Another example: https://danluu.com/2choices-eviction/

Re: The unreasonable effectiveness of modern sort algorithms

#24

Post by Sesse__ »

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.

Re: The unreasonable effectiveness of modern sort algorithms

#25

Post by fpoling »

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.

Chromium recommends to use flat_map, a map-like interface based on a sorted array, for data structures facing GUI or similar when the number of items in the map is naturally bounded. It is faster and more compact compared with hash maps.

Re: The unreasonable effectiveness of modern sort algorithms

#26

Post by natmaka »

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…

... and it many cases comes at a very low cost as quite often an index enabling to satisfy the usual "quickly find something" standard need exists, and most of them let us immediately obtain a sorted list.

Re: The unreasonable effectiveness of modern sort algorithms

#27

Post by mbroncano »

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…

On a side note, some languages still refer to computers as ‘sorting machines’ or just ‘sorters’

Re: The unreasonable effectiveness of modern sort algorithms

#29

Post by allturtles »

The scenario presented seems very odd. Why would you want to sort 10^7 items that are known to contain only four distinct values? It seems much more likely you would be counting the number of times each value appears, or selecting all of the elements of value X.

Re: The unreasonable effectiveness of modern sort algorithms

#30

Post by danielmarkbruce »

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…

Also, "shove it in a dictionary" works frequently too.... basically "organize the data in some way" is often the answer.
Post reply on HN