Faster sorting routines discovered and merged into the LLVM C++ library
Faster sorting routines discovered and merged into the LLVM C++ library is graded independently checked on whataifound.org, with the AI's role graded search scaffold.
AlphaDev found shorter branchless routines for sorting small fixed-length inputs; reverse-engineered to C++, they were merged into LLVM's libc++, the first change to those routines in over a decade.
- Verification
- Independently checked
- Autonomy
- Search scaffold
- Lab
- Google DeepMind
- Model
- AlphaDev (AlphaZero-based)
- Field
- Computer science
- Date
- 2023-06-07
What was found
AlphaDev treated the construction of a sorting routine as a single-player game played directly in CPU assembly, rewarding shorter and faster correct programs. For sort-3, sort-4 and sort-5 it removed instructions relative to the human-tuned library code, yielding large speedups on short sequences. The routines were reverse-engineered to C++ and accepted into the LLVM libc++ standard sort, which ships to millions of users. Published in Nature.
Novelty check
The libc++ small-sort routines had been hand-optimised by compiler engineers for years. AlphaDev's shorter instruction sequences were reviewed against the standing implementations and confirmed to be improvements before being merged.
Caveats
The gains are on very short fixed-length inputs; asymptotic sorting complexity is unchanged, and the headline percentage speedups apply only to those small cases. The 'independent' grade rests on LLVM maintainers reviewing and merging the code, not on a formal proof of optimality.
Independent checks
LLVM libc++ maintainers (code review and merge): reviewed and merged into the standard sort library · link ↗
Sources
Community discussion
How this is graded
whataifound.org grades every entry on two axes: verification (how solid the result is, from a machine-checked proof down to refuted) and autonomy (how much the AI did versus its human collaborators). This finding is independently checked and search scaffold. Full definitions are in the methodology.
Cite this entry
whataifound.org (2023). Faster sorting routines discovered and merged into the LLVM C++ library. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2023-06-07-alphadev