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

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 更多的数据类型。