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

    if (len = 4) { 
        sort4
    }
    elif (len = 3) {
        sort3
    }
    elif (len = 2) {
        sort2
    }

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.