Understanding DeepMind's sorting algorithm
justine.lol
justine.lol
The code size might not end up quite as good (also requires malloc), but a branchless merge sort is a contender for a fast and lightweight sort. Just published, tiny-sort-rs[0] cites 632 bytes and looks like ~350MB/s at 1e4 elements on Zen 3. In my tests, my own pisort[1] benches a little over twice as fast as LongSort, but it uses sorting networks as the base case so it's like 5KB. It's roughly based on piposort[2] which has more complicated recursion but a simpler base case.
400 MB/s seems a bit slow for a radix sort on that hardware: I'm hitting those numbers on my i5-6200U, which has less than half the clock rate, with my own radix sort. Recommend checking ska_sort_copy from [3] as it has about the same performance.
[0] https://github.com/Voultapher/tiny-sort-rs
[1] https://github.com/mlochbaum/SingeliSort/blob/master/src/mer...
The first example is "assembly code they published for sorting an array with three items" - this isn't an entire general-purpose sorting algorithm, it's just the innermost part.
How much does code size matter here? As long as the code has a good access pattern that maintains cache locality, is there any fundamental difference between 632 bytes and 5KB? L1 cache sizes are generally somewhere around 16-64 KB these days, so it seems like there wouldn't be a big difference here. Or am I just totally off base?
Would you want to depend on a C library that claims all 64kb of your L1 cache for itself? Of course not. You'd want to use a library that stays out of the way, so that your code can be the one exploiting system resources.
Sometimes it's better to choose a slower routine with a smaller footprint. Nowadays memory bandwidth is arguably the biggest performance limiting factor.
When it's not done by "artificial intelligence," we just call this "mutation testing": https://en.wikipedia.org/wiki/Mutation_testing
> The above algorithm shows what the new and improved libcxx is doing. It's basically quicksort except it switches to the sorting kernels and insertion sort when recursing into smaller slices.
This is a pretty standard technique, isn't it? You can eliminate hella recursive calls just by cutting off the bottom level of the call tree. For instance, take the following (Emacs lisp) functions:
(defun fib1 (n)
(if (or (= n 1) (= n 0))
1
(+ (fib1 (- n 1)) (fib1 (- n 2)))))
(defun fib2 (n)
(if (or (= n 1) (= n 0))
1
(if (= n 2)
2
(+ (fib2 (- n 1)) (fib2 (- n 2))))))
With libcxx I think they even took the added step of schlepping in heapsort, which is kind of slow, but prevents adversaries from smashing your stack.
How does heapsort protect against a stack attack?
Sure, theoretically, it does what you say, but you know what they say, right? In theory, theory and practice are the same. In practice, not so much. And, these are real differences, too: theory idealizes real computers as general Turing machines, when, in fact, they're really only linear bounded automata: https://en.wikipedia.org/wiki/Linear_bounded_automaton
See also the commentary following the code:
> This might be slightly slower than the first one, but it will never fail because it always performs the smaller partition first. Hence, the only way it could run into the limit is if the to-be-sorted array was at least 2MAX_LEVELS elements in size. Since 2300 is greater than 1090, and there are only about 1080 fundamental particles in this universe from which a human-made computer can be built, no larger limit will ever be needed.
> (Note: Someone reminded me that a typically 64-bit index variable can index only 264 items, not 2300. That’s true, but if you’re using a 64-bit computer, you’re probably not going to have an array of more than 264 elements anyway, even if each element was only one byte.)
The bit I meant to comment on was the "kind of slow" part. It is true that heapsort tends to be slower than a well-implemented quicksort, but you don't use heapsort when you need the absolute best speed. The (IMO) best thing about heapsort is that its best case and worst case are the same order of magnitude, so sorting n things will take a fairly consistent amount of time, no matter what.
jart doesn't provide detail about length of sequences used in testing, and AlphaDev basically says that between 6 and 249,999 elements the optimizations are slower (they only claim improvement for very small and 250k+ element sequences).
The AlphaDev numbers are so curious as well. AFAICT there's extra branching when you splice the tiny-sequence optimized versions (slower), but better sorting for the tiny sequences (faster).
Is it, like, branch prediction gets an edge when the leaf nodes of the recursion are all sorting tiny sequences? In jart's code, it's DFS, which I can only guess would trample a bit on branch prediction. I wonder if a BFS search could be better
No idea what would cause this though, curious if anyone has other ideas, I really don't know.
mov %rdx,%rcx
Answer: renaming can fail if the operands aren't ready and it isn't zero cost, just less.
Meanwhile I can just make sort 10 times faster with vectorization.
[1]: https://en.wikipedia.org/wiki/Sorting_network#Optimal_sortin...
I think its far better to sort the items incrementally as and when you receive them, so the act of sorting them is no longer on the critical path. Then the sorting takes virtually no time at all afterward, no matter how many items you need to sort.
The major bottleneck to computer systems is almost always the network and not the computing of algorithms. You can interleave the compute steps into the time spent waiting for the network.
1. That sounds like a you problem. Automating coding would be fantastic if it could be done; programs could rewrite themselves at runtime to do whatever the user needs. You could add features by asking for them. It would fundamentally revolutionize how we interact with computers.
2. Deepmind's algorithm discovery is just a different approach to automating coding. It's less learning from preexisting code and more searching the space of possible code - you get more original solutions but at a higher compute cost.
* It changed the file format
* For some people it was slower that the original version particularly on low end computers
However, the current version does use a similar approach to that which was proposed: https://github.com/ggerganov/llama.cpp/commit/f963b63afa0e05...
Also, there were insights into how to minimize which models needed adjustment. The ideas and code were worked on by at least 2 people, and I'm an outsider on that project, but I didn't see anything untoward like "stealing credit". The magic change wasn't a perfect move, but is the kind of thing I do locally when I don't know the project/binary format well yet, so not exactly the megalomaniacal move it was painted as. Better that only the version number changed, but she's independent and doing good work, so you'd kind of hope she has a self-promotion streak! Changing the magic would be on the very very low end of letting that side go a bit too far, assuming that was the impetus.
https://twitter.com/DimitrisPapail/status/166684395282416846...