7
$\begingroup$

On the 7th of June 2023, Google DeepMind released an article about AlphaDev. AlphaDev is an evolution of AlphaZero (used to beat world champions at Go, Chess and Shogi), and it can produce assembly code for a task if said task is represented as a game. All of this information can be found here.

Now, they tested AlphaDev on sorting algorithms and it discovered new algorithms as well as improved already existing ones. Here are the improvements made compared to the original code in assembly pseudo-code. The two algorithms improved are for sorting sequences of 3 and 4.

Can someone explain (or link to resources explaining) what concretely is different and why the specific modification in assembly code in the figure is an improvement to the sorting algorithm?

Improve this question
$\endgroup$
1

6 Answers 6

Reset to default
6
$\begingroup$

The improvement in the figure consists of the removal of one instruction. In a branch-less assembly program, this usually leads to a performance improvement. How much of a practical improvement it would be depends on how the subroutine is used.

Of course, the program should still be correct after this modification. The figure alone doesn't make this very clear, but this fragment describes only the final part of the implementation of a sorting network for 3 elements (the part inside the red ellipse). The first part guarantees that $B\leq C$, as noted in the paper. So, in the second part, instead of computing $\min(\min(A,C),B) = \min(A,B,C)$ for $P$ as in the program on the left, the program on the right computes $\min (A,B) = \min(A,B,C)$ (since $B\leq C$). This saves one assignment of $\min(A,C)$ to $P$ (initially, $P=A$), which is the instruction that is removed.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ An answer on Trying to understand the new sorting algorithm from AlphaDev: why does my assembly code not work as expected? points out that as well as being confusingly presented, their code for the final 2 steps isn't even correct in the image they show. They need to use cmovge not cmovg, for the compare that got optimized, since they're comparing a different element than they're selecting on (to reduce critical path latency I think, as well as saving an instruction on x86 but not AArch64.) $\endgroup$
    – Peter Cordes
    Commented Jun 29, 2023 at 17:52
  • $\begingroup$ With cmovg as shown, it can duplicate one of the input elements, e.g. sorting 2,1,1 to 2,1,2 instead of 1,1,2. (But apparently the change they committed to libc++ doesn't have this problem.) $\endgroup$
    – Peter Cordes
    Commented Jun 29, 2023 at 17:53
23
$\begingroup$

This is not a new sorting algorithm. It's much more interesting than that. AlphaDev appears to have produced a new technique for superoptimisation.

You can think of the superoptimisation problem as trying to take a code fragment, and finding the optimal sequence of instructions that does the same thing. The idea goes back at least to the 1970s; tools like BONSAI would start with a description of machine code expressed as some kind of formal logic, and then use heuristic search to find optimal code sequences.

The term "superoptimisation" was introduced by Henry Massalin in 1987. His was the first system to use exhaustive search, but it was made practical by using a limited subset of machine instructions. For many years, GCC was tuned using superoptimisations discovered by GNU superopt.

Superoptimisation is useful for discovering instruction selection templates and peephole optimisations, but the huge search space makes full optimisation prohibitive. Modern algorithms tend to use stochastic search and goal-directed search to allow for more instructions and longer instruction sequences.

What the AlphaDev appears to have achieved is the start of a new way to get even longer instruction sequences: use deep learning techniques to propose sequences, which would then presumably be automatically verified using a theorem prover like Z3.

This is a very interesting approach. Forget sort algorithms, it could revolutionise the way we construct compiler back-ends. It won't be feasible to run an ANN plus theorem prover on every compilation any time soon, but compiler developers could take larger patterns found in real code and generate special-purpose optimisations for them.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Granted. Constructing new improved algorithms, sorting or otherwise, from scratch is a deep CS challenge. Claiming progress in this area detracts from genuine contributions such as the one you sketch (more reminiscent of EDA advances aided by AI). Recent AI accomplishments are convincing in their own right. I am uneasy at over-claims (not only in this context) in trusted venues. The original question regards the contribution made and your comment points out where the core contribution lies, so happy to upvote. $\endgroup$
    – ExpressionCoder
    Commented Jun 28, 2023 at 19:23
  • 3
    $\begingroup$ One abstraction I’ve found very helpful in explaining this to people who are not CS experts is explaining superoptimization as a specialized case of code golf. Re-framed in those terms, I’ve found that a lot of people quickly understand what’s going on here, because they can easily see code golf as a ‘game’ (and from there, the use of AlphaZero as a base often immediately clicks, and they tend to quickly understand how this all works). $\endgroup$
    – Austin Hemmelgarn
    Commented Jun 28, 2023 at 22:24
  • 2
    $\begingroup$ EDA is a very good analogy, actually. It has a lot in common with compilers. $\endgroup$
    – Pseudonym ♦
    Commented Jun 28, 2023 at 23:39
  • 2
    $\begingroup$ This kinds of optimisations could be run offline, for widely used code (as they have done for a little part of sorting inside LLVM libc++; perhaps (de)compressors, encryption, ...). Starting from the optimiser code. :-D $\endgroup$
    – Pablo H
    Commented Jun 29, 2023 at 19:19
12
$\begingroup$

Check out Grady Booch's tweet on the matter:

there is no "new sorting algorithm" here.

Coming up with assembly level tricks is not the same as finding a new sorting algorithm. That would be my two cents on it.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Yeah, the 3-element sort is purely a micro-optimization of the implementation of a sorting network. Perhaps improving critical-path latency, though, as well as saving an instruction on some ISAs such as x86 but not AArch64. The 1-to-4-element optimization with a (maybe partial) sort before branching is arguably a new algorithm for that very specific sub-problem. It's certainly nothing like what I expected from their phrasing of "new algorithm", though, nothing like an alternative to QuickSort or whatever. $\endgroup$
    – Peter Cordes
    Commented Jun 29, 2023 at 17:47
  • 1
    $\begingroup$ I mean, there's just no other way to phrase it though... It is "new", but not in the foundational sense like the theory of relativity when that was new. It is an extremely nuanced "new" that is applicable to very specific cases, and it most likely isn't even understood by CS undergrads. $\endgroup$
    – Nelson
    Commented Jun 30, 2023 at 0:59
  • 1
    $\begingroup$ @Nelson: A more accurate phrasing would be "AlphaDev found some micro-optimizations in sorting networks for 3 and 4 element sub-problems which save an instruction on x86". (And shorten critical-path latency I think on all ISAs that have a conditional-move.) The 1-to-4 element sort with a branch is arguably algorithmically new, and interesting that AlphaDev could find it. $\endgroup$
    – Peter Cordes
    Commented Jul 1, 2023 at 16:08
6
$\begingroup$

The article says it. They focused on short sequences of $3$ to $5$ elements using the sorting network technique. They say they achieved $70\%$ speedup on these cases. But when you look closely to the detailed benchmarks, you see that $70\%$ is a unique extreme case, and speedups are more commonly like $+30\%$, $0\%$ and even down to $-35\%$.

Even more interesting is the fact that the speedup is of $+1.7\%$ on sequences of more than $250000$ elements (also best case ?). Last but not least, this "performance" is only available for sorting integers, a pretty ad-hoc case.

IMO, much fuss about nothing as regards the improvement of sorting algorithms, and even assembly optimization in general.

Improve this answer
$\endgroup$
2
$\begingroup$

As written in other answers, the contributions of AlphaDev are:

  • A branch-less implementation of sort for short vectors (from which most of the speedup over std::sort comes)
  • A reduction in the number of instructions to be executed.

In the meantime, others have provided even shorter/faster instruction sequences than AlphaDev, either developed by hand, or using a combination of human work and machine-based tools. See:

https://export.arxiv.org/abs/2307.14503v1

https://www.mimicry.ai/faster-sorting-beyond-deepminds-alphadev

Disclaimer: I was involved with the work on the side of mimicry, so take that with a grain of salt.

The key achievement of AlphaDev is that it achieved its improvement largely without human input (depending on how you consider the needed setup of AlphaDev to solve this particular problem). It remains to be seen how quickly AI alone can beat humans in coming up with great code.

Improve this answer
$\endgroup$
1
  • $\begingroup$ (Quite as real intelligence, great code begs a definition.) $\endgroup$
    – greybeard
    Commented Sep 30, 2023 at 8:40
1
$\begingroup$

I can’t properly explain what the concrete differences are here or why they work. I’ll leave that to someone who is an expert on sorting algorithms. The comments in the pseudo-code though do explain somewhat tersely what each instruction is doing in high-level terms, so looking through those (and possibly experimenting in some language where you can step through the individual operations and watch the states of the variables) is probably a solid starting point for understanding how they work.

I can, however, rather succinctly explain why they are an improvement in just two words: fewer instructions.

The updated code uses fewer instructions than the original code does, and it does not use any different instructions than the original. This means, barring questionable speculative execution or caching behavior, that the new code will run faster on identical hardware when compared to the old code. The big thing that makes this a certainty is that the changes only remove operations instead of replacing them with different operations. IOW, timings for every other part of the code will remain (theoretically) unchanged, so the algorithm as a whole will run faster.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ There is no rocket science in sorting $3$ to $5$ elements. $\endgroup$
    – user16034
    Commented Jun 29, 2023 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.