最近在www.example.com上发表了一篇文章nature.com，Faster sorting algorithms discovered using deep reinforcement learning，其中谈到AlphaDev发现了一种更快的排序算法。这引起了我的兴趣，我一直试图理解这个发现。
关于这个主题的其他文章是：

• AlphaDev discovers faster sorting algorithms
• Understanding DeepMind's AlphaDev Breakthrough in Optimizing Sorting Algorithms

下面是原始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 Desktop上编写、编译和运行的。

$ 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来完成小项目。基本上，我自学了我所知道的。为了达到编写这个测试的目的，我必须学习相当多的东西。因此，我肯定会犯错误或不理解问题。

无论如何，请帮助我理解为什么我在观察我是什么。

• 我误解了问题吗？
• 我是不是误解了伪代码？
• 将伪代码转换为汇编是不是犯了一个错误？
• 我的汇编代码有错误吗？
• 伪代码是错的吗？
• 还有别的吗