AlphaDev 将排序算法提速 70%，C 语言库作者一文详解 DeepMind 最新 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）操作。

为了解释为什么他们的代码很重要，让我们考虑一下这个算法在高层次上是如何工作的。当我第一次尝试自己解决 sort3 () 问题时，我想到了这个：

然后我查看了 libcxx，发现它们也在做同样的事情。上述代码的问题是，编译器并不善于优化它。

如果你尝试编译上面的代码，就会注意到你的编译器插入了大量的分支指令。这就是 DeepMind 试图通过 LLVM 贡献来改进的地方。

然而，这些技术往往不太容易理解。

我实际上喜欢天真无邪的代码，因为如果我们眯起眼睛，可以看到一种模式，与 DeepMind 最先进的汇编代码有相同的基本想法。

这个想法是这个问题本质上归结为 3 个比较和交换操作：

上面的代码是之前排序网络的最先进技术。现在，这就是 DeepMind 的新发现发挥作用的地方。他们发现有时上面的 mov 指令是不必要的。

如果你试着运行上面的代码，你会发现不管有没有被删除的行，它都是 100% 正确的。

这行代码看起来像是在做什么，但实际上什么也没做。所以我并不惊讶这样的事情会被计算机科学忽视几十年。

现在也应该更清楚 AlphaDev 是如何工作的。

DeepMind 基本上构建了一个人工智能，它可以摆弄汇编代码，随机删除一些东西，看看它是否损坏。

我这么说并不是要否定 AlphaDev 的智能，因为如果我说我没有做同样的事情，那就是在撒谎。

上面的代码中还有两个 mov 指令，我们有可能将其删除。通过使用 ARM64 指令集来做到这一点，它可以为类似的问题提供更小的代码。

在这里，我们不需要任何指令来创建临时变量：

Arm 公司最近风头正劲，我想上面的例子可以作为他们赢得名声的证据。

Arm 也是目前开源领域最好的公司之一。比如，他们的 MbedTLS 库是我迄今为止见过的最被低估的瑰宝之一。

当我开始使用它时，我原本有这样的计划，即修改 Arm 的代码，使之在 x86 硬件上更好地工作。

我编写了所有这些精心设计的汇编优化，使其与 x86 上的 OpenSSL 达到相同的性能。

MbedTLS 是简单、可移植、可破解的 C 代码，因此对于任何想要一个不是 Perl 生成的汇编的加密库的人来说，是个好消息。

我告诉了 Arm 公司的人我在做什么，他们并没有觉得这是颠覆性的。

我希望有一天能找到时间做 DeepMind 做的事情，并在上游进行修改。Arm 公司的优化程序库也是多产的，它在质量上与双转换无懈可击。

它对 C 库对此特别感兴趣，因为几十年来，开源社区一直依靠 Sun Microsystems 在 90 年代初编写的数学函数来维持生计。

Arm 找到了一种改进其中几个函数的方法，例如 pow (x,y) 。考虑到这是数学中最基本的运算之一，这是一件非常有影响力的事情。

比如，如果你在纯软件中使用 Arm 的解决方案在 x86 机器上实现 pow (x,y) ，那么它将比英特尔的原生 x87 指令快 5 倍。

很幸运，DeepMind 也加入了这个游戏，所以我冒昧地把他们的 libcxx diff 翻译成可读的 C 代码。

这是我希望在论文和博客文章中看到的另一件事，因为在这段代码中，你会发现专家们用来让编译器生成无分支 MOVcc 指令的规范技巧。

当我看到 Sort5 () 函数，我觉得自己对 DeepMind 研究的动机有了更好的理解。

如果你在 ARM64 上编译 Sort5 () 函数，那么编译器将产生一个处理 11 个寄存器的函数。如果你在推理一个数学方程，那么你能一次在你的工作记忆中保存 11 个变量吗？

可能不会。这就是为什么有一个像 PartialSort3 这样优秀的内核函数如此有用的原因。

值得一提的是，Sort3 () 和 Sort5 () 本身就是内核，因为它们旨在成为传统排序功能的构建块。

博客文章涵盖了这个主题，但我认为分享一些实际上可移植和可执行的东西会很有用。

The above algorithm shows what the new and improved libcxx is doing. It's basically quicksort except it switches to the sorting kernels and insertion sort when recursing into smaller slices. With libcxx I think they even took the added step of schlepping in heapsort, which is kind of slow, but prevents adversaries from smashing your stack.上面的算法显示了新的和改进的 libcxx 正在做什么。它基本上是快速排序，除了在递归到更小的切片时切换到排序内核和插入排序。对于 libcxx，我认为他们甚至采取了在堆排序中移动的额外步骤，这有点慢，但可以防止对手破坏您的堆栈。

The main thing you may be wondering at this point is, can I use this? Do these sorting network kernels actually make sorting go faster? I would say yes and no. When all you want is to sort ascending longs, the code above will go 2x faster than the standard qsort () function provided by your C library. Except you don't need the kernels to do that. What I've determined so far is that, on my personal computer (which has an Intel Core i9-12900KS) the above function sorts longs at 255 megabytes per second. However if I comment out the sorting kernels: 在这一点上，你可能想知道的主要事情是，我可以使用这个吗？这些排序网络内核真的能让排序变得更快吗？我会说是和不是。当你只想对升序长进行排序时，上面的代码将比你的 C 库提供的标准 qsort () 函数快 2 倍。只是你不需要内核来做到这一点。到目前为止，我已经确定，在我的个人电脑上（它有一个英特尔酷睿 i9-12900KS），上面的函数以每秒 255 兆字节的速度排序。但是如果我注释掉排序内核：

然后我的 longsort () 函数以每秒 275 兆字节的速度运行，通过简化算法实现了 7% 的性能提升。

long 的好处是它足够长，可以存储 int 键值对，能够快速对地图条目进行排序是一个有用的技巧。

上面的函数编译后只有 181 字节的 x86-64 机器代码。

由于 DeepMind 的 sort3 () 只有 42 字节，我希望可以交换一些大小以获得性能优势。

因为到目前为止，我发现的下一个最佳算法是改用基数排序，速度为 400 MB/s，但除了依赖于 malloc () 之外，还需要高达 763 字节的二进制占用空间。因此，如果能看到这些内核做得更好就好了。

这并不是说 DeepMind 的想法没有价值。

我认为值得注意的是，DeepMind 非常慷慨，去年给了我们他们的矢量化快速排序库（当时他们被称为 Google Brain），并通过这样做实现了永远无法挑战的排序优势。

Vqsor 在我的电脑上以 1155 MB/s的速度对长时间进行排序。

它甚至略微优于 djbsor，后者是开源社区中最受欢迎的库之一，尽管它从未推广到比 int 更多的数据类型。

这两种实现实现的方式都是通过矢量化排序网络。我认为这就是排序网络技术真正闪耀的地方。

我想，如果就智能实体而言，AlphaDev 不是一个蹒跚学步的孩子，它就会这样做。

当你从基本原则开始时，仅基线指令集就非常难以支持。如果我们等待，那么我认为我们可以期待在未来看到 AlphaDev 的伟大成就，因为它正在努力应对更强大的挑战。

我也很喜欢 DeepMind 让算法变得更小的事实，因为这是我不常看到的。

大小编码是我最喜欢的爱好之一。在这个博客上，我发布了一个 383 字节的 lambda 演算虚拟机和一个 436 字节的带有垃圾回收机制的 lisp 机。

我还在博客上介绍了我在 cosmpolitan c 库中使用的大小优化技巧。

我也喜欢 DeepMind 的母公司，因为几周前 Google 给我颁发了开源同行奖金，很高兴看到他们分享我使软件变小的热情。

很高兴看到他们用它来改进矢量化快速排序。

最后，我喜欢人工智能公司用机器语言编写代码的机器的想法。他们为什么不呢？机器的本质就是机器。

作为一个建设者，我发现这比 OpenAI 正在创造的未来要少得多。

他们已经建立了一个巨大的家长式机器，在零和经济中与地球上的每个建设者竞争，然后诱使世界上的寻租者通过政府监管来控制这台机器。

我不认为 OpenAI 承诺将所有我最喜欢做的任务（如编码）自动化是一种进步。我想要的是能够控制一台机器，这台机器能够完成我自己无法完成的事情，比如发现排序内核。这才是真正的进步。

我认为，我们能够砍掉的每一条装配线都是朝着这个梦想的积极方向迈出的一步。

参考资料：

• https://justine.lol/sorting/

本文来自微信公众号：新智元 （ID：AI_era）

广告声明：文内含有的对外跳转链接（包括不限于超链接、二维码、口令等形式），用于传递更多信息，节省甄选时间，结果仅供参考，IT之家所有文章均包含本声明。