如何比較彙編中的數組中的元素

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使管道飽和，但展開更多（並使用更多的累加器）只是使得這個非玩具版本的清理代碼更加令人頭疼。