Several ubiquitous programming functions are faster than ever after Google DeepMind researchers used gamification to teach an artificial intelligence (AI) engine to write code that is faster and more computationally efficient than anything created by humans.
When writing applications in languages like C++, software developers tap premade sorting and other functions stored in standard libraries of functions such as libc++.
Those functions – which are estimated to be used trillions of times every day – had been developed and optimized by humans over time.
“Billions of people use [sorting] algorithms every day without realizing it”, DeepMind staff research scientist Daniel J. Mankowitz explained as the team’s research debuted as a publication in Nature.
Sorting algorithms “underpin everything from ranking online search results and social posts to how data is processed on computers and phones”, he continued.
“Generating better algorithms using AI will transform how we program computers and impact all aspects of our increasingly digital society”.
Yet the existing sorting routines hadn’t been changed in over a decade – with researchers believing humans had squeezed as much inefficiency out of them that, Mankowitz said, “making further improvements is a major challenge, akin to trying to find a new way to save electricity or a more efficient mathematical approach”.
That kept expectations low as the DeepMind research team trained AlphaDev – which is based on the AlphaZero AI platform that also taught itself to beat human players as the game engine AlphaGo – to write software algorithms as though it was playing a game.
Their approach, which grew out of a practice known as deep reinforcement learning (DRL), was to design a single-player ‘game’ called AssemblyGame in which the player chooses a series of low-level assembly language instructions – the code that tells a computer’s central processing unit (CPU) what to do – and then evaluates its ability to sort data.
AlphaDev was tasked with playing AssemblyGame over and over again, testing each combination of instructions against the results of existing sorting algorithms and throwing out combinations that were either less efficient, or failed to work at all.
Small gains mean big improvements
The number of possible combinations is comparable to that of chess (10120 possible games) and go (10700 possible games), with successful combinations scored based on their speed and efficiency.
AlphaDev won if it produced a new algorithm that worked faster than the existing routines – and it eventually did, producing novel algorithms that could sort data with fewer steps while consuming fewer CPU resources.
The new algorithms could sort lists of up to five elements up to 70 per cent faster than existing approaches, while even large lists – those with more than 250,000 elements – can be sorted around 1.7 per cent faster.
The results were so strong that the new algorithms have been tested and officially embedded into libc++, meaning that millions of application developers are now using AlphaDev’s algorithm without even realising it.
Such improvements are possible because human developers normally write in high-level languages like C++, which are compiled into assembly language that is difficult for humans to read and work with.
Yet because AlphaDev is comfortable writing assembly language, it can attack problems in a way that humans simply cannot.
“Computer storage and operations are more flexible at this level, which means there are significantly more potential improvements that could have a larger impact on speed and energy usage”, Mankowitz explained.
“We believe many improvements exist at this lower level that may be difficult to discover in a higher-level coding language”.
The approach is transferrable to myriad other algorithms, promising further tweaks to the programming libraries used by every application running today – something the DeepMind team confirmed after AlphaDev developed a data hashing algorithm that runs 30 per cent faster than existing functions.
That algorithm has been integrated into the open-source Abseil development library “and we estimate that it’s now being used trillions of times a day,” Mankowitz said.
The novel algorithms “not only show that [AI] can improve algorithms but also find new solutions”, he continued. “We see AlphaDev as a step towards developing general-purpose AI tools that could help optimize the entire computing ecosystem”.
