Some very cool improvements found in already highly optimized algorithms.
They found that in a sorting network handling 3 inputs, the AI found a way to save an instruction by reducing a "min(A, B, C)" operation to just "min(A, B)" by taking advantage of the fact that previous operations guaranteed that B <= C. They also found that in a sorting network handling 4 inputs, when it is part of a "sort 8" network, there are similar guarantees (D >= min(A, C) in this case) that can be taken advantage of to remove an instruction as well. The compiler may not be able to compete with hand-written assembly, but it seems an AI can hand-write assembly code that's even better in some cases.
Another improvement is also very cool. They discuss VarSort4, which takes a list that may be 2, 3, or 4 elements long, and sorts it. The existing algorithm is
The AI found an algorithm that looks totally different:
if (len = 2) {
sort2
}
else {
sort3
if (len = 4) {
sortspecial
}
}
It's pretty wild! It immediately runs Sort3 on something that may be either 3 elements or 4 elements long, and only afterwards does it check to see how long it really is. If it's 3 elements long, we're done; otherwise, run Sort4 - but because (having already run Sort3) you know the first three elements are sorted, you can use a special and much simpler algorithm to simply put the 4th element in the right spot.
Very cool. Improving on core LLVM sorting algorithms that have already been heavily hand-optimized by the best in the world is definitely a "it's 1997 and Deep Blue defeats the World Champion in chess" kind of feeling.
Interesting that it took AI to pull this off. I think mutagen testing would have discovered the first (by virtue of checking which code isn’t necessary globally) though likely not the second (which needs a new branch, unless that branch was already there?).
As I understand it it kind of _did that_, just in an extremely guided kind of way, which is why it produced results in some reasonable amount of time (probably)
I'm surprised they only report results up to sort5.
It seems at that level, you could just iterate through all possible programs.
AI generated code seems more interested once you get to 10+ values, where classical methods break down.
I believe that's because above 5 elements, fixed sorting networks are no longer used. Introsort takes over and dispatches to insertion sort, quicksort, or heap sort as appropriate.
Divide and conquer strategies are used for larger sorts, and the smaller arrays could include the fixed lengths 3, 4, 5.
“ The compiler may not be able to compete with hand-written assembly, but it seems an AI can hand-write assembly code that's even better in some cases.”
This made me think “imagine if AI was the compiler”, that is to say you went from C or whatever to assembly via AI directly so it was “hand writing” the equivalent assembly for your instructions instead of using generic compilation.
Well it's not hard to imagine a "quick compile" option that uses a traditional compiler and an optimised compilation option that you use when shipping a production build or something while AI catches up in terms of speed.
They found that in a sorting network handling 3 inputs, the AI found a way to save an instruction by reducing a "min(A, B, C)" operation to just "min(A, B)" by taking advantage of the fact that previous operations guaranteed that B <= C. They also found that in a sorting network handling 4 inputs, when it is part of a "sort 8" network, there are similar guarantees (D >= min(A, C) in this case) that can be taken advantage of to remove an instruction as well. The compiler may not be able to compete with hand-written assembly, but it seems an AI can hand-write assembly code that's even better in some cases.
Another improvement is also very cool. They discuss VarSort4, which takes a list that may be 2, 3, or 4 elements long, and sorts it. The existing algorithm is
The AI found an algorithm that looks totally different: It's pretty wild! It immediately runs Sort3 on something that may be either 3 elements or 4 elements long, and only afterwards does it check to see how long it really is. If it's 3 elements long, we're done; otherwise, run Sort4 - but because (having already run Sort3) you know the first three elements are sorted, you can use a special and much simpler algorithm to simply put the 4th element in the right spot.Very cool. Improving on core LLVM sorting algorithms that have already been heavily hand-optimized by the best in the world is definitely a "it's 1997 and Deep Blue defeats the World Champion in chess" kind of feeling.