【新智元导读】阿尔法宗族新成员AlphaDev近来引发不少重视与评论。一位曾在谷歌作业的研讨人员对这项最新研讨进行了详解。
几天前，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许诺将所有我最喜爱做的任务（如编码）自动化是一种进步。我想要的是可以操控一台机器，这台机器可以完结我自己无法完结的工作，比方发现排序内核。这才是真实的进步。
我以为，咱们可以砍掉的每一条装配线都是朝着这个愿望的积极方向迈出的一步。
参考资料：
justine.lol/sorting/
