Faster sorting routines discovered and merged into the LLVM C++ library
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.
- Model
- AlphaDev (AlphaZero-based)
- Field
- Computer science
- Date
- 2023-06-07
Sources
Original work
Announcement
Independent commentary
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.
Video explainers
Nothing loads from YouTube until you press play.
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 and known objections
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 ↗
Disagree with these grades?
Bring a citation: a grade moves on evidence, not on argument.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Independently checked and Search scaffold.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Community discussion
Graded independently checked for verification and search scaffold for autonomy. What these mean.
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-alphadevBibTeX
@misc{whataifound-googledeepmind-2023-alphadev,
title = {Faster sorting routines discovered and merged into the LLVM C++ library},
author = {{whataifound.org}},
year = {2023},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Google DeepMind. Verification: Independently checked. Autonomy: Search scaffold.},
url = {https://whataifound.org/finding/2023-06-07-alphadev}
}