gcc -O0在2的幂(矩阵换位)矩阵大小上表现优于-O3

Question

(出于测试目的)我编写了一个简单的方法来计算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上,所以这可能是一些通用的东西？

所以我的问题基本上是:为什么执行时间周期性增加？是否有一些通用的东西与任何优化选项一起出现(就像clang和gcc一样)？如果是这样的优化选项导致了这个？

这怎么可能如此重要,即使O0版本的程序在512的倍数时优于03版本？

---

编辑:注意此(对数)图中峰值的大小.转换具有优化的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

Answer 1

执行时间的周期性增加必须归因于缓存仅是N路关联而不是完全关联.您正在目睹与缓存行选择算法相关的哈希冲突.

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

高速缓存行选择算法的典型硬件实现将仅使用来自存储器地址的少量位来确定应在哪个高速缓存槽中写入数据 - 在HW位移位中是空闲的.

这导致存储器范围之间的竞争,例如在地址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];
 }

示例5中的图表:高速缓存关联性说明矩阵行之间的512字节偏移是特定系统的全局最坏情况维度.当这已知时,工作缓解是将矩阵水平过度分配到某个其他维度char matrix[512][512 + 64].