AlphaDev found faster sorting code that entered a major C++ library

AI-generated sorting routines reached a shared software library. LLVM’s public record documents the reinforcement-learning-generated routines, their benchmarks and the engineering changes made before acceptance.[2]

Sorting means putting items into a chosen order. Imagine a program arranging delivery weights from lightest to heaviest. Its result must contain the same weights in the right sequence. The interesting engineering question is how much work the computer must do to reach that result.

Searching among the processor’s instructions

Google DeepMind’s AlphaDev study, published in June 2023, treated algorithm construction as a game. The agent added low-level processor instructions and received feedback on correctness and efficiency. Working at that level let it search combinations of comparisons and data movements. The researchers then translated useful discoveries into C++. Short routines matter because larger sorting procedures can repeatedly use them as building blocks.[1]

One shortcut used a fact an earlier operation had already established. Once B was known to be no larger than C, finding the smallest of A, B and C required comparing only A and B. The paper explains how that redundancy removed an instruction.[1]

Keeping the familiar programming interface

The C++ specification describes what a sort operation must accomplish: arrange a supplied range according to its comparison rule. It also sets a complexity requirement governing how comparisons grow with the number of items. That leaves library implementers room to improve the machinery underneath a familiar operation. A developer can request the same ordering while a revised implementation does the work differently.[3]

The LLVM review examined processor architectures, data types and comparison functions. The accepted approach used branchless routines in suitable cases: conditional data movements help avoid choosing between separate instruction paths. Reviewers prompted restrictions to simple comparisons and wider tests.[2]

The trade-off is revealing. More comparisons can be worthwhile when they avoid costly changes of execution path. That balance shifts when a user supplies an elaborate comparison function, so the library implementation selected suitable cases.[2]

How a local saving affects a whole task

The benefit to a complete application depends on how much time it spends in the improved operation. Consider an illustrative task taking 100 milliseconds, with 20 milliseconds devoted to sorting. If that entire sorting stage took 10% less time, it would save two milliseconds, reducing the whole task to 98 milliseconds. This is a calculated example, separate from AlphaDev’s measurements.

Such a saving can matter when the operation is repeated often. It also explains why a large improvement in a tiny routine and a modest improvement across a complete program can both be meaningful. The two measurements answer different questions.

A result other researchers could build on

The publication also created a concrete target for further work. In a July 2023 preprint, Cassio Neri presented shorter three-number routines and a C++ implementation that ran faster in his reported tests. His faster implementation compiled to 18 instructions with the compilers he identified, illustrating why counting instructions alone cannot settle performance. Those are follow-up author measurements, with their own hardware and benchmark conditions.[4]

The result became software that maintainers could adapt and researchers could improve. Ordinary programs can execute it after the AI discovery work has finished.[2][4]

Report an error or suggest a correction