AlphaDev将排序算法提速70%！C语言库作者一文详解DeepMind最新AI _AlphaDev

文章插图
图片来源：由无界 AI‌ 生成
几天前，DeepMind推出了AlphaDev，直接把排序算法提速70% 。
这一全新AI系统，便是基于下棋高手AlphaGo打造。

文章插图
而这项研究恰恰激起了前谷歌研究人员Justine Tunney的兴趣。
她表示，作为一名C语言库的作者，我一直在寻找机会来策划最好的东西。

文章插图
一起看看Justine如何详解DeepMind排序算法。
DeepMind排序算法
DeepMind的这一发现赢得了当之无愧的关注，但不幸的是，他们本可以更好地解释AlphaDev 。
接下来，从DeepMind发布的汇编代码开始，该代码将一个有三个项目的数组进行排序，从伪汇编翻译成汇编：

文章插图
我将这个函数命名为 move37，是因为DeepMind的博客文章，将其与AlphaGo下的令人震惊的「第37步」进行了比较。
在2016那场人机大战中，AlphaGo下了一颗违反人类直觉的棋，一个简单的肩冲，击败了传奇围棋选手李世石。

文章插图
所以如果运行DeepMind代码：
但是，在我看来这是一个错误。
我们给它的数组是{3,1,2}，但 move37 将其排序为{2,1,3} 。
DeepMind一定在欺骗我们，因为我不相信2在1之前。再来看看他们对LLVM libcxx所做的开源贡献，这有望澄清一些事情：

文章插图
所以 move37 实际上不是一个排序函数，而是一个排序内核，旨在用作 sort3 函数的构建块。
如果论文和博客文章能提到这一点就好了，因为它让我在最短的时间内感到非常困惑。下面是更好的代码版本，其中包括缺失的交换（swap）操作。

文章插图
【AlphaDev将排序算法提速70%！C语言库作者一文详解DeepMind最新AI】为了解释为什么他们的代码很重要，让我们考虑一下这个算法在高层次上是如何工作的。当我第一次尝试自己解决 sort3 问题时，我想到了这个：
然后我查看了libcxx，发现它们也在做同样的事情。上述代码的问题是，编译器并不善于优化它。
如果你尝试编译上面的代码，就会注意到你的编译器插入了大量的分支指令。这就是DeepMind试图通过LLVM贡献来改进的地方。
然而，这些技术往往不太容易理解。
我实际上喜欢天真无邪的代码，因为如果我们眯起眼睛，可以看到一种模式，与DeepMind最先进的汇编代码有相同的基本想法。
这个想法是这个问题本质上归结为3个比较和交换操作：
上面的代码是之前排序网络的最先进技术。现在，这就是DeepMind的新发现发挥作用的地方。他们发现有时上面的 mov 指令是不必要的。

文章插图
如果你试着运行上面的代码，你会发现不管有没有被删除的行，它都是100%正确的。
这行代码看起来像是在做什么，但实际上什么也没做。所以我并不惊讶这样的事情会被计算机科学忽视几十年。
现在也应该更清楚AlphaDev是如何工作的。
DeepMind基本上构建了一个人工智能，它可以摆弄汇编代码，随机删除一些东西，看看它是否损坏。
我这么说并不是要否定AlphaDev的智能，因为如果我说我没有做同样的事情，那就是在撒谎。

文章插图
上面的代码中还有两个 mov 指令，我们有可能将其删除。通过使用ARM64指令集来做到这一点，它可以为类似的问题提供更小的代码。
在这里，我们不需要任何指令来创建临时变量：

文章插图
Arm公司最近风头正劲，我想上面的例子可以作为他们赢得名声的证据。
Arm也是目前开源领域最好的公司之一。比如，他们的MbedTLS库是我迄今为止见过的最被低估的瑰宝之一。
当我开始使用它时，我原本有这样的计划，即修改Arm的代码，使之在x86硬件上更好地工作。
我编写了所有这些精心设计的汇编优化，使其与x86上的OpenSSL达到相同的性能。