... well not quite. There have been similar headlines elsewhere, but the truth is more subtle and we certainly don't have a rival to "Quicksort".

One of the problems with the impressive success of AI is that news of it has to be increasingly impressive-sounding. The latest report from Google DeepMind is impressive but not as impressive as you might think if you misunderstand it, even slightly.

What they have done is to take AlphaZero, their neural network that learns by reinforcement learning RL and applied it to the problem of improving the speed of sort algorithms. Of course, you know how important sorting speed is and you know that there are fundamental algorithms like Quicksort and merge sort and practical algorithms like Timsort and Powersort. If not all of them are explained elsewhere on this site, see the list of Related Articles.

Finding faster sorting algorithms is very fundamental and what could be better than to turn AlphaZero loose on the problem and see if it can do better than generations of creative programmers.

To get reinforcement learning into the procedure, the task of finding a faster sorting algorithm was turned into a game. Then AlphaDev, the customized RL agent, was trained while playing the game and it worked:

"AlphaDev discovered small sorting algorithms from scratch that outperformed previously known human benchmarks. These algorithms have been integrated into the LLVM standard C++ sort library."

Now, if you are anything like me, or like a lot of programmers out there, you will want to know what this amazing algorithm is. After all, it has been a long time since Quicksort was invented and that was a truly mind-boggling algorithm - this could be fun.

However when you start to read the small print beyond the Abstract of the paper, things don't look quite so exciting. It isn't so much that AlphaDev discovered a new algorithm, more that it found an optimization of the machine code implementing the original algorithm.

Basically AlphaDev was presented with the assembly language that implemented a small sort - sorting 3 items into order say. Then it varies the code and it is tested and AlphaDev gets a reward that is based on the correctness and the speed of the new code.  The speed of the code was taken to be an average speed across 100 different machines.

AlphaDev found an optimization of the code that involved deleting a mov instruction that wasn't doing anything. The fact that it isn't doing anything isn't easy to see and as such it is a worthwhile improvement to the code. It's an improvment' but not to the sorting algorithm in use. After finding the C++ code that makes LLVM produces the same assembly language the team had the code incorporated into the standard library.

A second improvement was to a sort 4 algorithm - usually this is just done by testing how many items are to be sorted and using the optimum sort for that number. AlphaDev came up with a more interesting decomposition of the problem. If there are 2 things then perform an optimal sort 2. If there are 3 or more perform a sort 3 and if there are 4 perform a sort 4 using the fact that the first three elements are sorted. However, on closer inspection the advantage of the new algorithm is that it results in a better assembly language implementation.

As I have said, optimizing assembler isn't as creative as inventing a new algorithm to challenge Quicksort, say, but it is interesting. It is in the same spirit as using simpler machine learning and statistics to optimize code and this has been going on for a long time. In fact, whenever I look at optimized machine code that has been derived from say a few lines of simple C I am often impressed by how "clever" the compiler is. So much so that I almost feel challenged by its efforts. Of course, I don't feel so impressed when the same compiler removes some vital bit of code because it has decided that it is undefined behavior. I guess all programmers have a love hate relationship with their compilers.

Perhaps in the not too distant future the role of AI in code will mean that the relationship can blossom into something deeper, more meaningful and more productive... I'm joking...

More Information

Faster sorting algorithms discovered using deep reinforcement learning

Related Articles

Python Now Uses Powersort

Magic of Merging

QuickSort exposed

Sorting Algorithms as Dances      

Sorting Algorithms As A Video

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info