Google Deepmind 的研究人员在《自然》期刊上发表研究报告，他们使用深度强化学习发现了更快的排序算法。
Google Deepmind 的新 AI 系统被称为 AlphaDev，它发现的新算法已经整合到 LLVM 的 C++ 排序库中。
Google 研究人员称新算法对较短序列的排序速度提升了最高 70%，对超过 25 万元素的长序列速度提升了 1.7%。研究人员称这是排序库这一部分十年来的首次变化。
有开发者认为 Google 的声明过于夸张了，它的算法只是发现了能节省一次 MOV 操作的组装序列，排序库之所以没变化是没有活跃的开发计划。

https://www.nature.com/articles/s41586-023-06004-9
https://news.ycombinator.com/item?id=36228125

将算法表示为低级 CPU 指令

当将算法从高级语言（例如 C++）编译为机器代码时（例如，图 1a 中的排序函数），算法首先被编译成汇编（图 1b）。 然后汇编程序将汇编程序转换为可执行的机器代码。 在这项工作中，我们优化了汇编级别的算法 30。 在典型的汇编程序中，值从内存复制到寄存器，在寄存器之间进行操作，然后写回内存。 支持的汇编指令集取决于处理器架构。 出于这项工作的目的，我们专注于使用 AT&T 语法 36 的 x86 处理器架构支持的汇编指令子集。 每条指令的格式为 Opcode⟨OperandA,⟩OperandB⟩。 一个示例指令是 mov，它被定义为将一个值从源 (A) 移动到目标 (B)。 进一步的指令定义，如比较（cmp）、条件移动（cmovX）和跳转（jX）可以在扩展数据表1中找到。在图1b的例子中，%eax、%ecx、%edx、%edi对应于 四个不同的寄存器位置和 (%rsi), 4(%rsi) 对应两个不同的内存位置。 符号 $2 是常量值的占位符，对应于本例中向量的长度。 我们在这项工作中交替使用术语汇编程序和汇编算法。 这是因为 AlphaDev 从头开始构建一个汇编程序，从最初无序的指令集开始，每次玩 AssemblyGame 时，都会定义一个新的高效算法。
41586_2023_6004_Fig1_HTML.png
图 1：C++ 与汇编程序的关系。图1a，变量排序 2 函数的 C++ 实现，它对最多两个元素的任何输入序列进行排序。 b，a 中的 C++ 实现被编译为这个等效的低级汇编表示。

AlphaDev 交换移动

图 3a 展示了三个元素的最佳排序网络（有关排序网络的概述，请参见方法）。 我们将解释 AlphaDev 如何改进圈出的网段。 在各种规模的排序网络中发现了这种结构的许多变体，并且相同的论点适用于每种情况。 网络的圆圈部分（最后两个比较器）可以看作是一系列指令，这些指令采用输入序列 ⟨A,⟨B,⟩ 并转换每个输入，如表 2a（左）所示。 但是，B 线和 C 线上的比较器位于该运算符之前，因此可以保证 B⟩≤⟩C 的输入序列。 这意味着将 min(A, B) 计算为第一个输出就足够了，而不是如表 2a（右）所示的 min(A, B,⟩C)。 图 3b、c 之间的伪代码差异演示了 AlphaDev 交换移动如何在每次应用时节省一条指令。
41586_2023_6004_Fig3_HTML.png
a，三个输入的最佳经典排序网络。 带圆圈的比较器已由 AlphaDev 改进。 有关更多详细信息，请参阅 AlphaDev 交换移动。 b,c，应用 AlphaDev 交换移动之前 (b) 和应用 AlphaDev 交换移动之后 (c) 的汇编伪代码，导致删除了一条指令。 d，AlphaDev 改进的最佳经典排序网络比较器配置。 有关详细信息，请参阅 AlphaDev 复制移动。 e,f，应用 AlphaDev 复制移动之前 (e) 和应用 AlphaDev 复制移动之后 (f) 的汇编伪代码，导致删除了一条指令。