
AI System Devises First Optimizations To Sorting Code In Over a Decade (arstechnica.com) 67
An anonymous reader quotes a report from Ars Technica: Anyone who has taken a basic computer science class has undoubtedly spent time devising a sorting algorithm -- code that will take an unordered list of items and put them in ascending or descending order. It's an interesting challenge because there are so many ways of doing it and because people have spent a lot of time figuring out how to do this sorting as efficiently as possible. Sorting is so basic that algorithms are built into most standard libraries for programming languages. And, in the case of the C++ library used with the LLVM compiler, the code hasn't been touched in over a decade.
But Google's DeepMind AI group has now developed a reinforcement learning tool that can develop extremely optimized algorithms without first being trained on human code examples. The trick was to set it up to treat programming as a game. [...] The AlphaDev system developed x86 assembly algorithms that treated the latency of the code as a score and tried to minimize that score while ensuring that the code ran to completion without errors. Through reinforcement learning, AlphaDev gradually develops the ability to write tight, highly efficient code. [...]
Since AlphaDev did produce more efficient code, the team wanted to get these incorporated back into the LLVM standard C++ library. The problem here is that the code was in assembly rather than C++. So, they had to work backward and figure out the C++ code that would produce the same assembly. Once that was done, the code was incorporated into the LLVM toolchain -- the first time some of the code had been modified in over a decade. As a result, the researchers estimate that AlphaDev's code is now executed trillions of times a day. The research has been published in the journal Nature.
But Google's DeepMind AI group has now developed a reinforcement learning tool that can develop extremely optimized algorithms without first being trained on human code examples. The trick was to set it up to treat programming as a game. [...] The AlphaDev system developed x86 assembly algorithms that treated the latency of the code as a score and tried to minimize that score while ensuring that the code ran to completion without errors. Through reinforcement learning, AlphaDev gradually develops the ability to write tight, highly efficient code. [...]
Since AlphaDev did produce more efficient code, the team wanted to get these incorporated back into the LLVM standard C++ library. The problem here is that the code was in assembly rather than C++. So, they had to work backward and figure out the C++ code that would produce the same assembly. Once that was done, the code was incorporated into the LLVM toolchain -- the first time some of the code had been modified in over a decade. As a result, the researchers estimate that AlphaDev's code is now executed trillions of times a day. The research has been published in the journal Nature.