Reproduce the magic touch of AlphaGo back then! DeepMind's new AI discovered a 70% speed-up sorting algorithm, and the C++ library that hasn't been updated in ten years has been updated

DeepMind has once again appeared in Nature with blockbuster results!

This time, they have strengthened learning AI again and made new breakthroughs in the two most basic algorithms in the computer field:

One is the sorting algorithm, which has found the highest speed improvement 70% new implementation;

The other is the hashing algorithm, which also found a new way to increase the speed by 30%.

Not only that, the method used by the AI ​​is called "recreating the magic touch of AlphaGo", which seems to be illegal, but actually defeats it in one fell swoop. That time with the human master Lee Sedol.

As soon as the news came out, it immediately detonated the academic circle. Some netizens called out:

I didn’t expect that such an ancient and basic algorithm could be further improved.

It is precisely because of this latest achievement that the LLVM standard C library, which has not been updated for ten years, has been updated, and dozens of Billions of people will benefit.

Because, whether it is sorting or hashing, their application scenarios can be used in various scenarios from online shopping, cloud computing to supply chain management, etc., and they are called hundreds of millions of times every day!

However, as DeepMind said:

Don’t get too excited, the power of AI has just begun to be used to improve code efficiency.

The "upstart" of the Alpha family discovers a faster sorting algorithm

This AI is called AlphaDev, and it belongs to the "upstart" of the Alpha family. And it is built based on AlphaZero (the chess AI that defeated the world champion in 2017).

Its discovery is not based on existing algorithms, but starts from the lowest level assembly instructions.

DeepMind researchers designed a single-player "assembly" game for it:

As long as you can search and select the appropriate instructions (process A in the figure below), it is correct and fast You can get rewards by arranging the data (process B in the figure below).

But the challenge of this game is not only the size of the search space (the number of combinable instructions is equivalent to the number of particles in the universe), but also It lies in the nature of the reward function, because one wrong instruction may cause the entire algorithm to fail.

AlphaDev has two core components: learning algorithm and representation function.

Among them, the learning algorithm is mainly expanded on the powerful AlphaZero, which can combine DRL and random search optimization algorithms to conduct a huge amount of instruction searches; the main representation function is based on Transformer, which can capture assembly The underlying structure of a program and expressed as a special sequence.

As AlphaDev continues to fight monsters and upgrade, researchers will also limit the number of steps it can perform and the length of the sequence to be sorted.

In the end, AlphaDev discovered a new sorting algorithm:

If the sequence is short, it can increase the speed by 70% compared to the human baseline sorting algorithm; if the sequence length exceeds 25,000 elements, the increase is 1.7%.

Short sequence sorting is widely used in practice, especially as an important component of larger sorting functions and is called many times. As long as short sequences are improved, the sorting speed of all sequences can be improved. )

Specifically, the innovation of this algorithm mainly lies in two instruction sequences:

(1) AlphaDev Swap Move (exchange move)
(2) AlphaDev Copy Move (copy move) )

As shown in the figure below, the left side is the original sort3 implementation using min(A,B,C), and the right side is the implementation of "AlphaDev Swap Move", which only requires min(A,B). It can be found that one step of instructions can be omitted, and only the minimum values ​​of A and B need to be calculated.

The author said that this novel method is reminiscent of AlphaGo's "Move 37" - a counterintuitive move that directly defeated the legendary Go player Lee Sedol, shocking the audience.

Similarly, AlphaDev skips a step by swapping and copying moves, achieving the goal in a way that seems wrong but is actually a shortcut.

As shown in the figure below, in the algorithm for sorting 8 elements, AlphaDev also uses "AlphaDev Copy Move" to replace the changes in the original implementation with max (B, min (A, C)) It is a complex max (B, min (A, C, D)) instruction, and the total number of instructions of the entire algorithm is also reduced by one step.

After discovering a faster sorting algorithm, the author also tried the hash algorithm with AlphaDev to prove its versatility.

The results did not disappoint, AlphaDev also achieved a 30% speed increase in the length range of 9-16 bytes.

Like the sorting algorithm, they have integrated the new method into the Abseil library, which is now available to millions of developers around the world.

Finally, the author stated that the implementation of two new algorithms shows that AlphaDev has a strong ability to discover original solutions, and will make us further think about how to improve basic algorithms in the computer field.

However, due to the limitations of the assembly language used in this study, they next plan to try AlphaDev's ability to optimize algorithms in high-level languages ​​(such as C).

Netizen: Not counting the discovery of a new sorting algorithm

Many people expressed great excitement about this achievement.

As this netizen said:

After AlphaGo amazed the world, what else can reinforcement learning do? Can anything of practical significance be done? This is the answer.

But this time, many people pointed out that DeepMind seemed to be suspected of exaggerating the title.

It calculates algorithm delay, not time complexity in the traditional sense. If you really calculate the time complexity, the data may not look good.

Its improvement is not in the sorting algorithm itself, but in new sorting optimization for modern CPUs (especially for short sequences). This approach is actually very common. For example, libraries such as FFTW and ATLAS have adopted this method.

Agreed, they just found a faster machine optimization for a specific CPU, not a new sorting algorithm , the method itself is cool, but not yet groundbreaking research.

What do you think?

Paper address: https://www.php.cn/link/a3fefe83288ecb0e40ebe40b2bde29fe
Official blog: https://www.php.cn/link/f5b2aa928f940f3f09a0d14f45a27875

Reference link:
[1]https://www.php.cn/link/5383c7318a3158b9bc261d0b6996f7c2
[2]https:// www.php.cn/link/ecf9902e0f61677c8de25ae60b654669
[3]https://www.php.cn/link/0383314bf626052313b8275638fcccce

The above is the detailed content of Reproduce the magic touch of AlphaGo back then! DeepMind's new AI discovered a 70% speed-up sorting algorithm, and the C++ library that hasn't been updated in ten years has been updated. For more information, please follow other related articles on the PHP Chinese website!