尝试了解 AlphaDev 的新排序算法：为什么我的汇编代码不能按预期工作？
mpb*_*den 9 sorting x86 assembly nasm
nature.com 最近发表了一篇文章《使用深度强化学习发现更快的排序算法》，其中谈到了 AlphaDev 发现了一种更快的排序算法。这引起了我的兴趣，我一直在努力理解这一发现。
关于该主题的其他文章有：
这是原始 sort3 算法与 AlphaDev 发现的改进算法的伪代码。
原始伪代码
Memory [0] = A
Memory [1] = B
Memory [2] = C
mov Memory[0] P // P = A
mov Memory[1] Q // Q = B
mov Memory[2] R // R = C
mov R S
cmp P R
cmovg P R // R = max(A, C)
cmovl P S // S = min(A, C)
mov S P // P = min(A, C)
cmp S Q
cmovg Q P // P = min(A, B, C)
cmovg S Q // Q = max(min(A, C), B)
mov P Memory[0] // = min(A, B, C)
mov Q Memory[1] // = max(min(A, C), B)
mov R Memory[2] // = max(A, C)
AlphaDev 伪代码
Memory [0] = A
Memory [1] = B
Memory [2] = C
mov Memory[0] P // P = A
mov Memory[1] Q // Q = B
mov Memory[2] R // R = C
mov R S
cmp P R
cmovg P R // R = max(A, C)
cmovl P S // S = min(A, C)
cmp S Q
cmovg Q P // P = min(A, B)
cmovg S Q // Q = max(min(A, C), B)
mov P Memory[0] // = min(A, B)
mov Q Memory[1] // = max(min(A, C), B)
mov R Memory[2] // = max(A, C)
改进的重点是省略单个移动命令mov S P。为了帮助理解，我编写了以下汇编代码。但是，我的测试表明排序算法在A=3、B=2 和 C=1时不起作用，但在A=3、B=1 和 C=2时起作用。
这是在 Ubuntu 20.04 桌面上编写、编译和运行的。
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 20.04.6 LTS
Release: 20.04
Codename: focal
$ nasm -v
NASM version 2.14.02
$ ld -v
GNU ld (GNU Binutils for Ubuntu) 2.34
我的汇编代码测试...
; -----------------------------------------------------------------
;
; sort_test.asm
;
; Test for AlphaDev sorting algorithm
;
; My findings are that AlphaDev's removal of 'mov S P' doesn't work when:
; a = 3, b = 2, c = 1
; But it does work with:
; a = 3, b = 1, c = 2
;
; Output: The sorted values of a, b & c printed to stdout with spaces
;
; Compile & run with:
;
; nasm -f elf32 sort_test.asm && ld -m elf_i386 sort_test.o -o sort_test && ./sort_test
;
; -----------------------------------------------------------------
global _start
section .data
a equ 3
b equ 2
c equ 1
section .bss
buffer resb 5
section .text
_start:
; ------------------- ; AlphaDev pseudo-code
mov eax, a ; P = A
mov ecx, b ; Q = B
mov edx, c ; R = C
mov ebx, edx ; mov R S
cmp eax, edx ; cmp P R
cmovg edx, eax ; cmovg P R // R = max(A, C)
cmovl ebx, eax ; cmovl P S // S = min(A, C)
; The following line was in original sorting algorithm,
; but AlphaDev determined it wasn't necessary
; mov eax, ebx ; mov S P // p = min(A, C)
cmp ebx, ecx ; cmp S Q
cmovg eax, ecx ; cmovg Q P // P = min(A, B)
cmovg ecx, ebx ; cmovg S Q // Q = max(min(A, C), B)
; add values to buffer with spaces
add eax, 30h
mov [buffer], eax
mov [buffer+1], byte 0x20
add ecx, 30h
mov [buffer+2], ecx
mov [buffer+3], byte 0x20
add edx, 30h
mov [buffer+4], edx
; write buffer to stdout
mov eax, 4 ; sys_write system call
mov ebx, 1 ; stdout file descriptor
mov ecx, buffer ; buffer to write
mov edx, 5 ; number of bytes to write
int 0x80
mov eax, 1 ; sys_exit system call
mov ebx, 0 ; exit status 0
int 0x80
我已在命令行上运行此测试以打印排序结果，但我也曾经gdb逐行执行此可执行文件。在此调试过程中，我清楚地看到“A”（又名“P”）、“eax”的寄存器在A=3、B=2 和 C=1时永远不会更新，但在A=3、B时更新=1，且C=2。
完全披露...我不是汇编程序员。我也不精通任何其他特定语言，但我尝试过使用 C、C++、Javascript、PHP 和 HTML 来完成小型项目。基本上，我所知道的都是自学的。为了达到编写这个测试的目的，我必须学习很多东西。因此，我肯定会犯错误或不理解问题。
无论如何，请帮助我理解为什么我要观察我自己。
- 我是否误解了这个问题？
- 我是否误解了伪代码？
- 我将伪代码转换为汇编代码是否犯了错误？
- 我的汇编代码有错误吗？
- 伪代码有错吗？
Pet*_*des 11
TL:DR：令人困惑的是，它们仅显示 3 元素排序网络中 3 个比较器中的最后 2 个，而不是完整的 3 元素排序。这是非常具有误导性的，包括在他们论文的图表中。
\n\n
我使用了 AT&T 语法（就像cmovg %ecx, %eax在用 GCC 组装的文件中一样.s），因此操作数顺序可以与伪代码匹配，目标在右侧。
你是对的，我看过这篇文章，当是 最小元素时，三元素伪代码无法正确排序C。我知道 x86-64 asm 向后可以向前，我的意思不仅仅是 Intel 与 AT&T 语法 :P 即使查看真正的代码，而不仅仅是注释，最小的元素也无法结束如果memory[0] = P它开始于R = memory[2] = C.
我在真正阅读您的问题所问的内容之前就打开了这篇文章，并在浏览文章直到到达有关实际改进的部分后自己注意到了这个问题，所以我没有看到您尝试复制它。但我并没有任何偏见去看待其中的问题，我只是想自己理解它。没有任何指令写入P读取可能包含起始值的值R，因此它无法获取该值。
\n
这篇文章间接链接了他们在 Nature 上发表的论文（ Daniel J. Mankowitz 等人使用深度强化学习发现的更快的排序算法）全文位于 Nature 链接中。
\n他们在实际论文中使用相同的代码图像，但带有一些关于三元素排序网络的解释性文本和图表。
\n\n\n\n
图 3a 展示了三个元素的最佳排序网络（有关排序网络的概述，请参阅方法）。我们将解释 AlphaDev 如何改进圈出的网络段。在对各种规模的网络进行排序时，可以发现这种结构的许多变体，并且相同的论点适用于每种情况。
\n网络的圆圈部分（最后两个比较器）可以看作是一个指令序列，它采用输入序列 \xe2\x9f\xa8A,\xe2\x80\x89B,\xe2\x80\x89C\xe2\x9f\xa9并对每个输入进行转换，如表 2a（左）所示。但是，导线 B 和 C 上的比较器位于该运算符之前，因此保证输入序列 B\xe2\x80\x89\xe2\x89\xa4\xe2\x80\x89C。这意味着计算 min(A,\xe2\x80\x89B) 作为第一个输出就足够了，而不是 min(A,\xe2\x80\x89B,\xe2\x80\x89C)，如表 2a 所示（右） ）。图 3b、c 之间的伪代码差异演示了 AlphaDev 交换移动如何在每次应用时保存一条指令。
\n
因此，该伪代码仅适用于排序网络的圆圈部分，即 3 个比较和交换步骤中的最后 2 个步骤。 在他们的博客文章中，甚至在论文的其他部分（例如表 2）中，他们听起来好像这是整个排序，而不仅仅是最后 2 个步骤。伪代码甚至令人困惑地从内存中的值开始，而在有条件交换 B 和 C 以确保 B <= C 后就不会出现这种情况。
\n\n
mov此外，在三元素排序中， 仅仅一条指令不太可能带来巨大的加速。x86的MOV真的可以“免费”吗？为什么我根本无法重现这个？- 它从来都不是免费的（它会消耗前端带宽），但它在除 Ice Lake 之外的大多数最新微架构上具有零延迟。我猜想这并不是他们获得 70% 加速的情况！
\n
使用 AVX SIMD 指令（例如vpminsd dst, src1, src2（https://www.felixcloutier.com/x86/pminsd:pminsq）/来执行具有非破坏性单独目标的带符号双字（32 位）vpmaxsd元素的最小值和最大值，则无需除关键路径延迟外的节省。 min(B, prev_result)仍然只是一条指令，不需要单独的寄存器复制（vmovdqa xmm0, xmm1），就像如果您正在执行排序网络一样，只需 SSE4.1。但是，当用 shuffle 和 SIMD 最小/最大比较器构建排序网络时，延迟可能会很严重，我最后听说的是 x86-64 上大整数或 FP 数组的整数排序的最先进技术，而不仅仅是节省mov时间标量cmov代码！
但许多程序在编译时并未假设 AVX 可用，因为不幸的是，它并未得到普遍支持，在过去几年的一些低功耗 x86 CPU 上以及 Ice Lake 之前的 Pentium / Celeron CPU 上都缺少它（所以对于低预算桌面 CPU 来说，最近可能会在 2018 年左右。）
\n他们在 Nature 上的论文提到了 SIMD 排序网络，但指出 libc++std::sort没有利用它，即使输入是floator数组int，而不是class带有重载 es 的情况也是如此operator <。
\n
这个三元素调整是一种微观优化，而不是“新的排序算法”。它可能仍然可以节省 AArch64 上的延迟，但仅限于 x86 上的指令
\nmin(A,C)人工智能能够找到这些微观优化是件好事，但如果呈现为在选择或选择之间进行选择，它们就不会那么令人惊讶，min(B,C)因为后者才是B当时的实际情况。
通过仔细选择更高级别的源来避免寄存器复制指令是人类可以做的事情，例如，_mm_movehl_ps在我 2016 年关于执行水平 SSE 向量和（或其他减少）的最快方法的回答中选择合并目标（第一个源操作数） - 请参阅对编译器生成的 asm 的注释# note the reuse of shuf, avoiding a movaps。
自动化微优化方面的先前工作包括STOKE，这是一种随机超级优化器，它随机尝试指令序列，希望找到与您提供的测试函数的输出相匹配的廉价序列。搜索空间太大，当需要超过 3 或 4 条指令时，它往往会错过可能的序列（STOKE 自己的页面说它还没有准备好生产，只是一个研究原型）。所以人工智能很有帮助。手动查看汇编以查找可能错过的优化需要大量工作，而这些优化可以通过调整源代码来修复。
\n但至少对于这个三元素子问题来说，它只是一个微观优化，并不是真正的新算法。它仍然只是一个 3 比较器排序网络。对于 x86-64 来说编译成本更低，这很好。但在某些 3 操作数 ISA 上，它们的等效项有单独的目标cmov，例如AArch64 的csel dst, src1, src2, flag_condition条件选择，则无需mov保存。不过，它仍然可以节省关键路径上的延迟。
他们在《自然》杂志上的论文还展示了对可变数量的元素进行排序的算法差异，其中 >= 3 个案例都从对前 3 个进行排序开始。也许这有助于分支预测，因为当最终分支正在解决时，该工作可能会正在进行len > 3中看看他们是否需要进行简化的 4 元素排序，假设前 3 个元素已排序。他们说：“正是例程的这一部分导致了显着的延迟节省。” （他们也称其为“全新”算法，我认为这对于在短的未知长度输入上使用排序网络的问题是正确的。）
小智 5
Deepmind 的 Nature 文章中的 AlphaDev Sort3 算法的伪代码存在一个错误，当第一个数字大于其他两个相等的数字时，该错误会影响三个数字的排序。即A>B=C（满足前提条件B<=C）。例如，输入为(2,1,1)，则输出为(2,1,2)；没有排序并且实际上已损坏。
\nbug在第12行：cmovg QP，应该是cmovge QP，以确保在这种情况下P被覆盖。重新引入原始 mov SP 指令也可以解决该问题，但会违背更改的目的。\n类似的错误和修复适用于本文图 3 d、e、f 中的 Sort8 片段的伪代码（cmovl RT 应为 cmovle RT)。
\nAlphaDev\xe2\x80\x99s Github 上的 Sort3 代码和 Nature 文章的 Supplement G 中没有这个问题，想必 LLVM libc++ 库中的代码也没有这个问题。
\n\n
一步步：
\n# before first shown step (after the B,C comparator)\nP = 2\nQ = 1\nR = 1\n\n# after first step\n # P=2 still unmodified by this step, still just A\n # Q=1 still still just B\nR = 2 # max(A,C) = max(A, max(B, C)) since B<=C\nS = 1 # min(A,C) = min(A, max(B, C))\n\n cmp S, Q(B) is cmp 1, 1 # the Greater condition is false\n# after final step\nP = 2 unchanged by cmovg Q(1), P(2) !!!! Bug here\nQ = 1 unchanged by cmovg S(1), Q(1)\n# R = 2 still\ncmovge Q, P会复制1而不是保留2. 对于升序排序，我们希望 PQR = 1,1,2