Sorting algorithms are an essential part of computer science
BEST BACKGROUNDS/Shutterstock
An algorithm used billions of times a day by computers around the world could be adapted to run up to 70 percent faster thanks to artificial intelligence from British company DeepMind. It found an improved way of sorting objects that human programmers had overlooked for decades.
“We honestly didn’t expect to do anything better: it’s a very short program, these types of programs have been studied for decades,” says Daniel Mankowitz of DeepMind.
Sorting algorithms are one of the workhorses of computing and are used to organize data by sorting words alphabetically or sorting numbers from smallest to largest. There are many different sorting algorithms, but innovations are limited as they have been heavily optimized over the decades.
Now, DeepMind has developed an AI model called AlphaDev, which aims to discover new algorithms for completing a specific task, hoping to outperform human efforts. Instead of optimizing existing algorithms, AlphaDev starts from scratch.
It works in assembly code, the computer’s intermediate language that sits between human-written source code and the 0’s and 1’s encoded sequences of binary instructions. Assembly code can be difficult for humans to read and understand, but most software is written in a high-level programming language that is more intuitive before being translated or “compiled” into assembly code. According to DeepMind, the AlphaDev sub-language offers more scope for optimizing algorithms to make them more efficient.
The AI is instructed to build an algorithm, instruction by instruction, and test its output against a known-correct solution to ensure an effective method is created. It is also instructed to create the shortest possible algorithm. According to DeepMind, the larger the problem, the harder the task, because the number of possible combinations of instructions can quickly approach the number of particles in the universe.
When asked to develop a sorting algorithm, AlphaDev proposed one that was 70 percent faster than the prior art for lists of five data items and 1.7 percent faster for lists of over 250,000 items.
“We initially thought it was a bug or there was a bug or something, but when we analyzed the program we found that AlphaDev had actually discovered something faster,” says Mankowitz.
As sorting algorithms are used in a variety of popular software, this improvement could have a significant cumulative impact worldwide. Such algorithms are so important that instead of writing your own, they are written in code libraries that anyone can use. DeepMind has made its new algorithms open source and included in the widely used Libc++ library, so users can start using them today. According to DeepMind, this is the first change to this part of the sorting algorithm library in over a decade.
Mankowitz says that Moore’s Law — the idea that a single chip’s processing power doubles at regular intervals — is coming to an end because miniaturization is hitting immutable physical limits, but AlphaDev may be able to remedy the problems by shrinking the size of the chip to solve instead of increasing the size of the chips.
“Today these algorithms are being withdrawn [run in software] We estimate that it is used trillions of times every day and can be used by millions of developers and companies around the world,” says Mankowitz. “Optimizing the code of basic functions that are called trillions of times a day will hopefully have great benefits to encourage people to run even more of these functions and see this as a way to remove this bottleneck.” [of Moore’s law slowing].”
Mark Lee from the University of Birmingham, UK, says AlphaDev is interesting and even a 1.7 percent speed increase makes sense. But he says even if similar efficiencies are found in other popular algorithms, he’s skeptical that this will make up for the violation of Moore’s Law, since it can’t be applied to more esoteric software in the same way.
“I think the gains in hardware will always be bigger,” he says. “I think they can do that with things like sorting algorithms and standard calculator algorithms. But it is not applied to complex pieces of code.”
Subjects:
