5 ms·
The unreasonable effectiveness of modern sort algorithms
- deleted 1y ago[deleted]
- bob1029 1y agoI 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 selection. Randomly sampling from the population and running tournaments is way more scalable than scanning and ordering a global list each iteration. You can maintain things like an ELO score with very narrow views into memory. Nothing needs a global view yet you get global effects.
- spiffytech 1y agoCould you give an example of reframing a problem from totally ordered complete data to a sampled tournament? I can imagine cases amenable to sampling, but since sampled data is smaller I'm not sure why I wouldn't just sort it.
- loa_in_ 1y agoSorting doesn't yield an ELO score for each item. Though tournament is a form of sorting. It's like instrumented sorting.
- akoboldfrying 1y agoI 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.
- bob1029 1y agoAn 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/ https://danluu.com/2choices-eviction/
- codegladiator 1y agoGood read. Reminds me of the 1 billion row aggregation challenge, especially the perfect hashing part, all the top entries all used it. https://github.com/gunnarmorling/1brc https://github.com/gunnarmorling/1brc
- lukaslalinsky 1y agoThere 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 problem, but it's often a fairly good one. So I'm really enjoying how good sorting algorithms are getting and how despite the O complexity remains mostly the same, the real computing efficiency is improving significantly.
- natmaka 1y ago... 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.
- mbroncano 1y agoOn a side note, some languages still refer to computers as ‘sorting machines’ or just ‘sorters’
- danielmarkbruce 1y agoAlso, "shove it in a dictionary" works frequently too.... basically "organize the data in some way" is often the answer.
- Imnimo 1y agoJust be careful you aren't doing the classic, "my linear regression works way better when I independently sort the inputs and targets"!
- Eddy_Viscosity2 1y agoBut this one weird trick is crazy effective, if you value chart aesthetics over meaningfulness, which I do. My charts look great.
- wizardforhire 1y ago
- akoboldfrying 1y agoYour "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.
- Sesse__ 1y ago“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.
- Voultapher 1y agoDoing the phf as shown is an and + neg instruction and just doing % 4 is just the and. I tested it on a Apple M1 machine and saw no difference in performance at all. It's possible to go much faster with vectorization 3x on the Zen 3 machine.
- Sesse__ 1y agoI didn't say it was slower, just that it was more obfuscated.
- akoboldfrying 1y agoYou're right about memory movement, not sure what I was thinking.
- ekelsen 1y agoWouldn'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.
- Voultapher 1y agoradsort a radix sort is present in the comparison results.
- ekelsen 1y agohmmm, 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 based on high bits and then LSB) absolutely can...
- Voultapher 1y agoYou are right, a better wording be a "is a pure radix sort".
- allturtles 1y agoThe 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.
- forsalebypwner 1y agoI believe the purpose of choosing such an odd scenario is to show that, while you might think that you can beat the generic sort algos with a more domain-specific implementation, you might be wrong, or you might not gain enough performance to make it worth the other pitfalls of using such algos
- Animats 1y agoNeat. Adaptive radix sorts exist, where the keyspace is divided into roughly equal sized buckets based on the distribution of the data. The setup is slow enough that this is usually used only for very large sorts that have to go out to disk, or, originally, tape. It's the first patented algorithm, SyncSort.
- TinkersW 1y agoIs there a C++ port of ipnsort?
- throwaway984393 1y ago[dead]
- conradludgate 1y agoThe efforts of developing better sorting algorithms like driftsort/ipnsort and better hash functions like foldhash make my life as developer so much simpler. No matter how clever I try to be, most often just using foldhash hashmap or a sort_unstable is the fastest option
- DennisL123 1y agoEfficiency, not effectiveness. They are all effective in the sense that they produce sorted results. Even the non-modern sort algorithms are effective in the sense that the results are correct. This should be about the efficiency with which they do it, right?
- creata 1y ago"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".
- kwertyoowiyop 1y agoComing next: “What we talk about when we talk about modern sort algorithms”
- rcxdude 1y agoor "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"
- chuckadams 1y ago"Optimize your sorts with this one weird trick." "What they don't want you to know about sorting."
- j_not_j 1y agoAscending is all you need.
- JSR_FDED 1y agoFrom TFA: The title is an homage to Eugene Wigner's 1960 paper "The Unreasonable Effectiveness of Mathematics in the Natural Sciences".
- aabhay 1y agoAgreed. Effectiveness would imply that some algorithms are more likely to sort the list correctly than others, or they sort a higher percentage of elements. Efficiency is about factors external to the correctness
- Epa095 1y agoDouble 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.
- fpoling 1y agoChromium 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.
- Voultapher 1y agoA looong time ago I wrote my first blog post - on a now defunct website - about a VecMap where I did exactly that. Sort when needed and full flat array. That said flat_map as coined by Google is an acronym for swiss tables. See [1]. I.e. exactly what Rust's standard library `HashMap` is, also the one being tested here. [1] https://github.com/abseil/abseil-cpp/blob/23b9b75217721040f5a2d073b8ef3014486ef5b7/absl/container/flat_hash_map.h#L19 https://github.com/abseil/abseil-cpp/blob/23b9b75217721040f5...
- Voultapher 1y agoYour comment made my day, thank you.
- dvh 1y agoIsn't this just another case of premature optimization? Shouldn't you be adjusting sorting algorithms only when customer complains?
- codegladiator 1y agoThis is pushing the limits to identify the boundaries
- dvh 1y agoAlso known as premature optimization. You had to literally invent new dataset just to show there is a difference. You are inventing problems, stop doing that!
- dspillett 1y ago> You are inventing problems Sometimes that is how useful jumps are made. Maybe someone will come along with a problem and the data they have just happens to have similar properties. Rather than premature optimisation this sort of thing is pre-emptive research - better to do it now than when you hit a performance problem and need the solution PDQ. Many useful things have come out of what started as “I wonder what if …?” playing.
- gpvos 1y agoThis is research, not production code. Premature optimization is irrelevant.
- grues-dinner 1y agoI think the article basically had this conclusion. Think twice before optimising here because you may be able to squeeze something out for a very limited scenario but it can have ugly failure modes and it end up being slower in some cases. Plus it takes time and effort. And modern standard sorts are "unreasonably" fast anyway for many practical purposes. Then again only thinking of fixing things when a customer complains is a way to end up with a leaning tower of hacks which eventually ossify and also the customer (or rather the users, who may not be the customer especially in business software) may be putting up with dozens of niggles and annoyances before they bother to actually report one bug because they can't work around it.