(出于测试目的)我写了一个简单的方法来计算 nxn 矩阵的转置

void transpose(const size_t _n, double* _A) {
    for(uint i=0; i < _n; ++i) {
        for(uint j=i+1; j < _n; ++j) {
            double tmp  = _A[i*_n+j];
            _A[i*_n+j] = _A[j*_n+i];
            _A[j*_n+i] = tmp;
        }
    }
}

当使用优化级别 O3 或 Ofast 时，我希望编译器展开一些循环，这将导致更高的性能，尤其是当矩阵大小是 2 的倍数时(即，每次迭代都可以执行双循环体)或类似情况。相反，我测量的结果恰恰相反。 2 的幂实际上显示了执行时间的显着峰值。

这些尖峰也以 64 为固定间隔，以 128 为间隔更明显，依此类推。每个尖峰都延伸到相邻的矩阵大小，如下表所示

size n  time(us)
1020    2649
1021    2815
1022    3100
1023    5428
1024    15791
1025    6778
1026    3106
1027    2847
1028    2660
1029    3038
1030    2613

我使用 gcc 版本 4.8.2 编译，但同样的事情发生在 clang 3.5 上，所以这可能是一些通用的事情？

So my question basically is: Why is there this periodic increase in execution time? Is it some generic thing coming with any of the optimization options (as it happens with clang and gcc alike)? If so which optimization option is causing this?

And how can this be so significant that even the O0 version of the program outperforms the 03 version at multiples of 512?

编辑:注意此(对数)图中尖峰的幅度。转置带优化的 1024x1024 矩阵实际上与转置 1300x1300 矩阵没有优化所花费的时间一样多。如果这是一个缓存错误/页面错误问题，那么有人需要向我解释为什么程序的优化版本的内存布局如此显着不同，以至于它失败了 2 次方，只是为了恢复高性能稍大的矩阵。缓存错误不应该创建更多类似步骤的模式吗？为什么执行时间再次下降？ (为什么优化应该创建以前不存在的缓存错误？)

编辑:以下应该是 gcc 生成的汇编代码

没有优化(O0):

_Z9transposemRPd:
.LFB0:
    .cfi_startproc
    push    rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    mov rbp, rsp
    .cfi_def_cfa_register 6
    mov QWORD PTR [rbp-24], rdi
    mov QWORD PTR [rbp-32], rsi
    mov DWORD PTR [rbp-4], 0
    jmp .L2
.L5:
    mov eax, DWORD PTR [rbp-4]
    add eax, 1
    mov DWORD PTR [rbp-8], eax
    jmp .L3
.L4:
    mov rax, QWORD PTR [rbp-32]
    mov rdx, QWORD PTR [rax]
    mov eax, DWORD PTR [rbp-4]
    imul    rax, QWORD PTR [rbp-24]
    mov rcx, rax
    mov eax, DWORD PTR [rbp-8]
    add rax, rcx
    sal rax, 3
    add rax, rdx
    mov rax, QWORD PTR [rax]
    mov QWORD PTR [rbp-16], rax
    mov rax, QWORD PTR [rbp-32]
    mov rdx, QWORD PTR [rax]
    mov eax, DWORD PTR [rbp-4]
    imul    rax, QWORD PTR [rbp-24]
    mov rcx, rax
    mov eax, DWORD PTR [rbp-8]
    add rax, rcx
    sal rax, 3
    add rdx, rax
    mov rax, QWORD PTR [rbp-32]
    mov rcx, QWORD PTR [rax]
    mov eax, DWORD PTR [rbp-8]
    imul    rax, QWORD PTR [rbp-24]
    mov rsi, rax
    mov eax, DWORD PTR [rbp-4]
    add rax, rsi
    sal rax, 3
    add rax, rcx
    mov rax, QWORD PTR [rax]
    mov QWORD PTR [rdx], rax
    mov rax, QWORD PTR [rbp-32]
    mov rdx, QWORD PTR [rax]
    mov eax, DWORD PTR [rbp-8]
    imul    rax, QWORD PTR [rbp-24]
    mov rcx, rax
    mov eax, DWORD PTR [rbp-4]
    add rax, rcx
    sal rax, 3
    add rdx, rax
    mov rax, QWORD PTR [rbp-16]
    mov QWORD PTR [rdx], rax
    add DWORD PTR [rbp-8], 1
.L3:
    mov eax, DWORD PTR [rbp-8]
    cmp rax, QWORD PTR [rbp-24]
    jb  .L4
    add DWORD PTR [rbp-4], 1
.L2:
    mov eax, DWORD PTR [rbp-4]
    cmp rax, QWORD PTR [rbp-24]
    jb  .L5
    pop rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   _Z9transposemRPd, .-_Z9transposemRPd
    .ident  "GCC: (Debian 4.8.2-15) 4.8.2"
    .section    .note.GNU-stack,"",@progbits

优化 (O3)

_Z9transposemRPd:
.LFB0:
    .cfi_startproc
    push    rbx
    .cfi_def_cfa_offset 16
    .cfi_offset 3, -16
    xor r11d, r11d
    xor ebx, ebx
.L2:
    cmp r11, rdi
    mov r9, r11
    jae .L10
    .p2align 4,,10
    .p2align 3
.L7:
    add ebx, 1
    mov r11d, ebx
    cmp rdi, r11
    mov rax, r11
    jbe .L2
    mov r10, r9
    mov r8, QWORD PTR [rsi]
    mov edx, ebx
    imul    r10, rdi
    .p2align 4,,10
    .p2align 3
.L6:
    lea rcx, [rax+r10]
    add edx, 1
    imul    rax, rdi
    lea rcx, [r8+rcx*8]
    movsd   xmm0, QWORD PTR [rcx]
    add rax, r9
    lea rax, [r8+rax*8]
    movsd   xmm1, QWORD PTR [rax]
    movsd   QWORD PTR [rcx], xmm1
    movsd   QWORD PTR [rax], xmm0
    mov eax, edx
    cmp rdi, rax
    ja  .L6
    cmp r11, rdi
    mov r9, r11
    jb  .L7
.L10:
    pop rbx
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc
.LFE0:
    .size   _Z9transposemRPd, .-_Z9transposemRPd
    .ident  "GCC: (Debian 4.8.2-15) 4.8.2"
    .section    .note.GNU-stack,"",@progbits

最佳答案

执行时间的周期性增加一定是由于缓存只是 N 路关联而不是完全关联。您正在目睹与缓存行选择算法相关的哈希冲突。

最快的 L1 缓存具有比下一级 L2 更少的缓存行数。在每个级别中，每个缓存行只能从一组有限的来源中填充。

高速缓存行选择算法的典型硬件实现将只使用内存地址中的几个位来确定数据应写入哪个高速缓存槽——在硬件中位移位是免费的。

这会导致内存范围之间的竞争，例如地址 0x300010 和 0x341010 之间。 在完全顺序算法中，这无关紧要——N 对于几乎所有形式的算法来说足够大:

 for (i=0;i<1000;i++) a[i] += b[i] * c[i] + d[i];

但是当输入(或输出)的数量变大时(在优化算法时内部发生这种情况)，缓存中的一个输入会迫使另一个输入从缓存中移出。

 // one possible method of optimization with 2 outputs and 6 inputs
 // with two unrelated execution paths -- should be faster, but maybe it isn't
 for (i=0;i<500;i++) { 
       a[i]     += b[i]     * c[i]     + d[i];
       a[i+500] += b[i+500] * c[i+500] + d[i+500];
 }

Example 5: Cache Associativity 中的图表说明矩阵行之间的 512 字节偏移是特定系统的全局最坏情况维度。当知道这一点时，一个有效的缓解方法是将矩阵水平过度分配到其他维度 char matrix[512][512 + 64]。

关于c++ - gcc -O0 在矩阵大小为 2 的幂(矩阵转置)上优于 -O3，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21842402/