如何比较汇编中的数组中的元素

Question

如何比较汇编语言x86中数组中的所有元素？我必须比较数组中的所有元素并打印出最大的元素

Answer 1

我打算假装这不是一个可怕的小问题，而是实际讨论用汇编语言进行此操作的有趣部分（而不是让一个编译器为你优化它）。

---

在asm中，您可以像使用任何其他语言一样进行操作。但是，如果您正在使用矢量指令编写机器，您可以并且应该使用它们。编译器通常会为你做，但你必须自己做。

由于在ASM编写代码的主要原因是high performance，让我们考虑一些问题：

---

没有向量指令，它可能会或可能不会使用条件，转移到一个好主意做平常的x=max(x, a[i])。 cmov会引入一个循环进行的依赖，这可能会损害性能比偶尔的分支错误预测更多。 （谷歌更多关于此）。

当发现最大值时，分支预测错误可能并不频繁，除非您的值很嘈杂，但平均增加。 （例如，每1到10个元素会出现一个新的最大值，这样会接近最差的情况）。否则，您可能会经常看到新的最大值或者从未看到新的最大值。

---

x86的矢量最小/最大指令在每个元素的基础上像cmp/cmov一样工作。

所以，如果你的阵列由32位有符号整数，你可以通过加载前4个元素为向量寄存器使用开始（比如xmm0），然后用add rsi, 16/PMAXSD xmm0, [rsi]一个循环里面做4包装x=max(x,src)操作。 PMAXSD英文是：Packed（整数）签名的DWord元素的最大值。请参阅x86 wiki中的链接以获取参考指南。 PMAXSD是SSE4.1的一部分，因此它仅在具有该功能位的CPU上受支持。

如果您的数组由uint8_t元素组成，您将使用PMINUB（无符号字节元素的压缩（int）最小值）。 PMIN/MAXUB和PMIN/MAXSW位于SSE2中，因此它们是x86-64的基准（对于需要具有SSE2支持的足够新硬件的操作系统上的x86-32）。

在循环数组后（可能使用PALIGNR或PSRLDQ处理数组的最后一个非16进制数），在累加器向量中将会有4个元素。每一个是每四个元素的最大值，对于四个不同的偏移量。为了得到最大值，你需要水平地找到向量中的最大元素。通过混洗它（例如，将它正确地字节移位，因此高两个元素移动到低两个元素的位置），然后使用PMAXSD与未混排的值进行比较。然后重复这个过程，得到最后两个元素的最大值。

现在您可以将该32位整数存储到内存中，或者使用movd将其直接从xmm0转换为eax作为函数返回值。

---

有一定的提升空间在这里，因为即使pmaxsd有一个周期（英特尔Haswell的为例）的延迟，它有一个吞吐量的2％的周期。所以理想情况下，我们可以保持每个时钟两个PMAX的吞吐量，并带有内存操作数。 （由于Intel SnB和以后有两个加载端口，L1缓存可以跟上这一点。）我们需要使用多个累加器来允许并行操作。 （然后在完成水平操作之前将所有累加器一起PMAX）。

;;; probably buggy, use at your own risk. edits welcome 
global max_array 
max_array: 
    ; function args: int *rsi, uint64_t rdi 
    ; requirements: src is aligned on a 16B boundary, size is a multiple of 32bytes (8 elements), and >=8 on entry 
    ; TODO: support unaligned with some startup code, and a partial final iteration with some cleanup 

    lea rdx, [rsi + 4*rdi] ; end pointer 

    movdqa xmm0, [rsi]  ; two accumulators 
    movdqa xmm1, [rsi + 16] 

    add rsi, 32 
    cmp rsi, rdx 
    jae .out  ; early exit if we shouldn't run the loop even once. unsigned compare for addresses 

.loop: 
    pmaxsd xmm0, [rsi] 
    pmaxsd xmm1, [rsi+16] 
    add  rsi, 32 
    cmp  rsi, rdx ;; loop is 4 uops on Intel, since this cmp/branch macro-fuses 
    jb .loop 

.out: 
    ;; TODO: cleanup code to handle any non-multiple-of-8 iterations. 

    pmaxsd xmm0, xmm1 
    movhlps xmm1, xmm0 ; xmm0 = { d, c, b, a}. xmm1 = { d, c, d, c } 
    pmaxsd xmm0, xmm1 ; xmm0 = { d, c, max(d,b), max(c, a) } 
          ; if we were using AVX 3-operand instructions, we'd use PSRLDQ and another pmax because it's easy. 

    ; do the final stage of horizontal MAX in integer registers, just for fun. 
    ; pshufd/pmax to do the last level would be faster than this shld/cmp/cmov. 

    movq rax, xmm0  ; rax = { max(d,b), max(c,a) } 
      ; two-reg shift to unpack rax into edx:eax (with garbage in the high half of both) 
    shld rdx, rax, 32 ; rax = unchanged (eax=max(c,a)), edx = max(d,b). 
    cmp  edx, eax 
    cmovg eax, edx  ; eax = max(max(c,a), max(d,b)) 
    ret 

从理论上讲，这个运行在Intel SnB系列微架构的每个时钟的一次迭代中。每个时钟4个熔融域uops使管道饱和，但展开更多（并使用更多的累加器）只是使得这个非玩具版本的清理代码更加令人头疼。