Сfor-loop裏面的算術優化

Question

我有兩個for循環函數，看起來非常相似。要處理的數據量非常大，因此我試圖儘可能優化循環。第二個功能的執行時間爲320秒，但第一個功能需要460秒。有人請給我任何建議是什麼使差異和如何優化計算？

int ii, jj; 
    double c1, c2; 

    for (ii = 0; ii < n; ++ii) { 
     a[jj] += b[ii] * c1; 
     a[++jj] += b[ii] * c2; 
    } 

第二個：

int ii, jj; 
    double c1, c2; 

    for (ii = 0; ii < n; ++ii) { 
     b[ii] += a[jj] * c1; 
     b[ii] += a[++jj] * c2; 
    } 

這裏是用於第一循環中的彙編程序的輸出：

movl -104(%rbp), %eax 
    movq -64(%rbp), %rcx 
    cmpl (%rcx), %eax 
    jge LBB0_12 
## BB#10:        ## in Loop: Header=BB0_9 Depth=5 
    movslq -88(%rbp), %rax 
    movq -48(%rbp), %rcx 
    movsd (%rcx,%rax,8), %xmm0 ## xmm0 = mem[0],zero 
    mulsd -184(%rbp), %xmm0 
    movslq -108(%rbp), %rax 
    movq -224(%rbp), %rcx  ## 8-byte Reload 
    addsd (%rcx,%rax,8), %xmm0 
    movsd %xmm0, (%rcx,%rax,8) 
    movslq -88(%rbp), %rax 
    movq -48(%rbp), %rdx 
    movsd (%rdx,%rax,8), %xmm0 ## xmm0 = mem[0],zero 
    mulsd -192(%rbp), %xmm0 
    movl -108(%rbp), %esi 
    addl $1, %esi 
    movl %esi, -108(%rbp) 
    movslq %esi, %rax 
    addsd (%rcx,%rax,8), %xmm0 
    movsd %xmm0, (%rcx,%rax,8) 
    movl -88(%rbp), %esi 
    addl $1, %esi 
    movl %esi, -88(%rbp) 

和用於第二之一：

movl -104(%rbp), %eax 
    movq -64(%rbp), %rcx 
    cmpl (%rcx), %eax 
    jge LBB0_12 
## BB#10:        ## in Loop: Header=BB0_9 Depth=5 
    movslq -108(%rbp), %rax 
    movq -224(%rbp), %rcx  ## 8-byte Reload 
    movsd (%rcx,%rax,8), %xmm0 ## xmm0 = mem[0],zero 
    mulsd -184(%rbp), %xmm0 
    movslq -88(%rbp), %rax 
    movq -48(%rbp), %rdx 
    addsd (%rdx,%rax,8), %xmm0 
    movsd %xmm0, (%rdx,%rax,8) 
    movl -108(%rbp), %esi 
    addl $1, %esi 
    movl %esi, -108(%rbp) 
    movslq %esi, %rax 
    movsd (%rcx,%rax,8), %xmm0 ## xmm0 = mem[0],zero 
    mulsd -192(%rbp), %xmm0 
    movslq -88(%rbp), %rax 
    movq -48(%rbp), %rdx 
    addsd (%rdx,%rax,8), %xmm0 
    movsd %xmm0, (%rdx,%rax,8) 
    movl -88(%rbp), %esi 
    addl $1, %esi 
    movl %esi, -88(%rbp) 

的原來的功能要大得多，所以在這裏我公關只贊成負責這些for-loops的部分。其餘的c代碼及其彙編輸出對於兩個函數都完全相同。

Answer 1

該計算的結構很奇怪，但它可以顯着優化。該代碼的一些問題是

• 在寫入其他未知別名的指針後，從指針重新加載數據。我認爲他們不會別名，因爲如果允許這種算法會更怪，但如果他們真的應該是別名，可以忽略它。通常，將循環體構造爲：首先加載所有內容，進行計算，然後再儲存。不要混合加載和存儲，這會使編譯器更加保守。
• 重新加載之前迭代中存儲的數據。編譯器可以看穿這一點，但它使事情變得複雜。不要這樣做。
• 以不同方式隱含處理第一個和最後一個項目。它看起來像一個很好的同質環，但由於其奇怪的結構，它實際上是第一個也是最後一個東西的特殊結構。

所以我們先來修復第二個循環，這很簡單。這裏唯一的問題是第一家商店b[ii]，它必須真的發生^（tm），因爲它可能與a[jj + 1]混淆。但它可以平凡寫入，使得問題解決：

for (ii = 0; ii < n; ++ii) { 
    b[ii] += a[jj] * c1 + a[jj + 1] * c2; 
    jj++; 
} 

您可以通過彙編輸出編譯器是現在過得快樂告訴，當然基準測試證實了它的速度更快。

Old ASM（只有主循環，而不是額外的克魯夫特）：

.LBB0_14:        # =>This Inner Loop Header: Depth=1 
    vmulpd ymm4, ymm2, ymmword ptr [r8 - 8] 
    vaddpd ymm4, ymm4, ymmword ptr [rax] 
    vmovupd ymmword ptr [rax], ymm4 
    vmulpd ymm5, ymm3, ymmword ptr [r8] 
    vaddpd ymm4, ymm4, ymm5 
    vmovupd ymmword ptr [rax], ymm4 
    add  r8, 32 
    add  rax, 32 
    add  r11, -4 
    jne  .LBB0_14 

新的ASM（只有主迴路）：

.LBB1_20:        # =>This Inner Loop Header: Depth=1 
    vmulpd ymm4, ymm2, ymmword ptr [rax - 104] 
    vmulpd ymm5, ymm2, ymmword ptr [rax - 72] 
    vmulpd ymm6, ymm2, ymmword ptr [rax - 40] 
    vmulpd ymm7, ymm2, ymmword ptr [rax - 8] 
    vmulpd ymm8, ymm3, ymmword ptr [rax - 96] 
    vmulpd ymm9, ymm3, ymmword ptr [rax - 64] 
    vmulpd ymm10, ymm3, ymmword ptr [rax - 32] 
    vmulpd ymm11, ymm3, ymmword ptr [rax] 
    vaddpd ymm4, ymm4, ymm8 
    vaddpd ymm5, ymm5, ymm9 
    vaddpd ymm6, ymm6, ymm10 
    vaddpd ymm7, ymm7, ymm11 
    vaddpd ymm4, ymm4, ymmword ptr [rcx - 96] 
    vaddpd ymm5, ymm5, ymmword ptr [rcx - 64] 
    vaddpd ymm6, ymm6, ymmword ptr [rcx - 32] 
    vaddpd ymm7, ymm7, ymmword ptr [rcx] 
    vmovupd ymmword ptr [rcx - 96], ymm4 
    vmovupd ymmword ptr [rcx - 64], ymm5 
    vmovupd ymmword ptr [rcx - 32], ymm6 
    vmovupd ymmword ptr [rcx], ymm7 
    sub  rax, -128 
    sub  rcx, -128 
    add  rbx, -16 
    jne  .LBB1_20 

這也得到了展開更多（自動），但更重要的區別（不是展開無用，而是減少循環開銷通常不是那麼重要，它主要可以由不忙於向量指令的端口來處理）是商店的減少，這就需要它從2/3的比例（潛在的瓶頸存儲吞吐量的一半商店是無用的）到4/12（瓶頸由真正發生的事情）。

現在對於第一循環，一旦你把第一個和最後的迭代，它只是增加了兩個縮放b的每一個a，然後我們把第一個和最後一個迭代回分別：

a[0] += b[0] * c1; 
for (ii = 1; ii < n; ++ii) { 
    a[ii] += b[ii - 1] * c2 + b[ii] * c1; 
} 
a[n] += b[n - 1] * c2; 

這需要從這個（注意，這甚至不是矢量）：

.LBB0_3:        # =>This Inner Loop Header: Depth=1 
    vmulsd xmm3, xmm0, qword ptr [rsi + 8*rax] 
    vaddsd xmm2, xmm2, xmm3 
    vmovsd qword ptr [rdi + 8*rax], xmm2 
    vmulsd xmm2, xmm1, qword ptr [rsi + 8*rax] 
    vaddsd xmm2, xmm2, qword ptr [rdi + 8*rax + 8] 
    vmovsd qword ptr [rdi + 8*rax + 8], xmm2 
    vmulsd xmm3, xmm0, qword ptr [rsi + 8*rax + 8] 
    vaddsd xmm2, xmm2, xmm3 
    vmovsd qword ptr [rdi + 8*rax + 8], xmm2 
    vmulsd xmm2, xmm1, qword ptr [rsi + 8*rax + 8] 
    vaddsd xmm2, xmm2, qword ptr [rdi + 8*rax + 16] 
    vmovsd qword ptr [rdi + 8*rax + 16], xmm2 
    lea  rax, [rax + 2] 
    cmp  ecx, eax 
    jne  .LBB0_3 

要這樣：

.LBB1_6:        # =>This Inner Loop Header: Depth=1 
    vmulpd ymm4, ymm2, ymmword ptr [rbx - 104] 
    vmulpd ymm5, ymm2, ymmword ptr [rbx - 72] 
    vmulpd ymm6, ymm2, ymmword ptr [rbx - 40] 
    vmulpd ymm7, ymm2, ymmword ptr [rbx - 8] 
    vmulpd ymm8, ymm3, ymmword ptr [rbx - 96] 
    vmulpd ymm9, ymm3, ymmword ptr [rbx - 64] 
    vmulpd ymm10, ymm3, ymmword ptr [rbx - 32] 
    vmulpd ymm11, ymm3, ymmword ptr [rbx] 
    vaddpd ymm4, ymm4, ymm8 
    vaddpd ymm5, ymm5, ymm9 
    vaddpd ymm6, ymm6, ymm10 
    vaddpd ymm7, ymm7, ymm11 
    vaddpd ymm4, ymm4, ymmword ptr [rcx - 96] 
    vaddpd ymm5, ymm5, ymmword ptr [rcx - 64] 
    vaddpd ymm6, ymm6, ymmword ptr [rcx - 32] 
    vaddpd ymm7, ymm7, ymmword ptr [rcx] 
    vmovupd ymmword ptr [rcx - 96], ymm4 
    vmovupd ymmword ptr [rcx - 64], ymm5 
    vmovupd ymmword ptr [rcx - 32], ymm6 
    vmovupd ymmword ptr [rcx], ymm7 
    sub  rbx, -128 
    sub  rcx, -128 
    add  r11, -16 
    jne  .LBB1_6 

這次不錯，並且矢量化了，而且更少的存儲和加載正在進行。

這兩種變化的結合使我的電腦速度提高了兩倍，但當然是YMMV。

我仍然認爲這段代碼很奇怪。注意我們在第一次循環的最後一次迭代中如何修改a[n]，然後在第二次循環的第一次迭代中使用它，而其他的a只是站在旁邊觀看。這很古怪。也許它確實是這樣，但坦率地說，它看起來像一個bug。