Gcc -O0 превосходит -O3 по размерам матрицы, которые являются степенями 2 (матричные транспозиции)

(Для целей тестирования) я написал простой метод для вычисления транспонирования матрицы 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 программы превосходит версию 03 в кратности 512?

EDIT: Обратите внимание на величину спайков в этом (логарифмическом) графике. Транспонирование матрицы 1024x1024 с оптимизацией фактически занимает столько же времени, сколько и перенос матрицы 1300x1300 без оптимизации. Если это проблема с ошибкой кэш-памяти/сбоя страницы, то кто-то должен объяснить мне, почему макет памяти настолько сильно отличается для оптимизированной версии программы, что она терпит неудачу для двух степеней свободы, просто для восстановления высокой производительности для несколько больших матриц. Должны ли кэшированные ошибки создавать более шагообразные шаблоны? Почему время выполнения снова уменьшается? (и почему оптимизация создала ошибки кэша, которых раньше не было?)

EDIT: должны быть коды ассемблера, созданные 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

Ответ 1

Периодическое увеличение времени выполнения должно быть связано с тем, что кеш является только N-образным ассоциативным, а не полностью ассоциативным. Вы являетесь свидетелем столкновения хэшей, связанного с алгоритмом выбора строки кэша.

Самый быстрый L1-кеш имеет меньшее количество строк кэша, чем следующий уровень L2. На каждом уровне каждая строка кэша может быть заполнена только из ограниченного набора источников.

Типичные HW-реализации алгоритмов выбора строки кэша будут просто использовать несколько бит из адреса памяти для определения того, в каком кэш-слоте должны записываться данные - в сдвигах бит 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].

Ответ 2

Улучшение производительности, вероятно, связано с кэшированием CPU/RAM.

Когда данные не имеют значения 2, загрузка строки кеша (например, 16, 32 или 64 слова) переносит больше, чем данные, требующие привязки к шине, бесполезно, как выясняется. Для набора данных, который имеет мощность 2, используются все предварительно выбранные данные.

Готов поспорить, если вам нужно отключить кеширование L1 и L2, производительность будет полностью гладкой и предсказуемой. Но это было бы намного медленнее. Кэширование действительно помогает производительности!

Ответ 3

Комментарий с кодом: В случае -O3 с

#include <cstdlib>

extern void transpose(const size_t n, double* a)
{
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = i + 1; j < n; ++j) {
            std::swap(a[i * n + j], a[j * n + i]); // or your expanded version.
        }
    }
}

компиляция с помощью

$ g++ --version
g++ (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1
...
$ g++ -g1 -std=c++11 -Wall -o test.S -S test.cpp -O3

Я получаю

_Z9transposemPd:
.LFB68:
    .cfi_startproc
.LBB2:
    testq   %rdi, %rdi
    je  .L1
    leaq    8(,%rdi,8), %r10
    xorl    %r8d, %r8d
.LBB3:
    addq    $1, %r8
    leaq    -8(%r10), %rcx
    cmpq    %rdi, %r8
    leaq    (%rsi,%rcx), %r9
    je  .L1
    .p2align 4,,10
    .p2align 3
.L10:
    movq    %r9, %rdx
    movq    %r8, %rax
    .p2align 4,,10
    .p2align 3
.L5:
.LBB4:
    movsd   (%rdx), %xmm1
    movsd   (%rsi,%rax,8), %xmm0
    movsd   %xmm1, (%rsi,%rax,8)
.LBE4:
    addq    $1, %rax
.LBB5:
    movsd   %xmm0, (%rdx)
    addq    %rcx, %rdx
.LBE5:
    cmpq    %rdi, %rax
    jne .L5
    addq    $1, %r8
    addq    %r10, %r9
    addq    %rcx, %rsi
    cmpq    %rdi, %r8
    jne .L10
.L1:
    rep ret
.LBE3:
.LBE2:
    .cfi_endproc

И что-то совсем другое, если я добавляю -m32.

(Примечание: для сборки не имеет значения, использую ли я std:: swap или ваш вариант)

Чтобы понять, что вызывает шипы, вы, вероятно, хотите визуализировать операции с памятью.

Ответ 4

Чтобы добавить к другим: g++ -std=c++11 -march=core2 -O3 -c -S - версия gcc 4.8.2 (MacPorts gcc48 4.8.2_0) - x86_64-apple-darwin13.0.0:

__Z9transposemPd:
LFB0:
        testq   %rdi, %rdi
        je      L1
        leaq    8(,%rdi,8), %r10
        xorl    %r8d, %r8d
        leaq    -8(%r10), %rcx
        addq    $1, %r8
        leaq    (%rsi,%rcx), %r9
        cmpq    %rdi, %r8
        je      L1
        .align 4,0x90
L10:
        movq    %r9, %rdx
        movq    %r8, %rax
        .align 4,0x90
L5:
        movsd   (%rdx), %xmm0
        movsd   (%rsi,%rax,8), %xmm1
        movsd   %xmm0, (%rsi,%rax,8)
        addq    $1, %rax
        movsd   %xmm1, (%rdx)
        addq    %rcx, %rdx
        cmpq    %rdi, %rax
        jne     L5
        addq    $1, %r8
        addq    %r10, %r9
        addq    %rcx, %rsi
        cmpq    %rdi, %r8
        jne     L10
L1:
        rep; ret

В основном то же, что и код @ksfone, для:

#include <cstddef>

void transpose(const size_t _n, double* _A) {
    for(size_t i=0; i < _n; ++i) {
        for(size_t 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;
        }
    }
}

Помимо различий Mach-O 'as' (дополнительные подчеркивания, выравнивания и местоположения DWARF), это то же самое. Но очень сильно отличается от выхода сборки OP. Более "плотная" внутренняя петля.