Флаг оптимизации gcc -O3 делает код медленнее, чем -O2

Question

Я нахожу эту тему Почему быстрее обрабатывать отсортированный массив, чем несортированный массив?, И попробуйте запустить этот код. И я нахожу странное поведение. Если я скомпилирую этот код с -O3 флаг оптимизации это занимает 2.98605 sec бежать. Если я скомпилирую с -O2 занимает 1.98093 sec, Я пытаюсь запустить этот код несколько раз (5 или 6) на одной и той же машине в той же среде, закрываю все остальные программы (chrome, skype и т. Д.).

gcc --version
gcc (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Так, пожалуйста, вы можете объяснить мне, почему это происходит? Я читаю gcc руководство, и я вижу, что -O3 включает в себя -O2, Спасибо за помощь.

PS добавь код

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Answer 1

gcc -O3 использует cmov для условного выражения, поэтому он расширяет цепочку зависимостей, переносимых циклом, для включения cmov (что соответствует 2 мопам и 2 циклам задержки на вашем процессоре Intel Sandybridge, согласно таблицам инструкций Agner Fog. См. также вики-тег x86). Это один из случаев, когда cmov отстой

Если данные были даже умеренно непредсказуемы, cmov вероятно, это будет победа, так что это довольно разумный выбор для компилятора. (Тем не менее, компиляторы могут иногда использовать код без ответвлений слишком много.)

Я поместил ваш код в проводник компилятора Godbolt, чтобы увидеть asm (с хорошим выделением и фильтрацией нерелевантных строк. Однако вам все равно придется прокручивать весь код сортировки, чтобы добраться до main()).

.L82:  # the inner loop from gcc -O3
    movsx   rcx, DWORD PTR [rdx]  # sign-extending load of data[c]
    mov     rsi, rcx
    add     rcx, rbx        # rcx = sum+data[c]
    cmp     esi, 127
    cmovg   rbx, rcx        # sum = data[c]>127 ? rcx : sum
    add     rdx, 4          # pointer-increment
    cmp     r12, rdx
    jne     .L82

gcc мог бы сохранить MOV, используя LEA вместо ADD.

Узкие места цикла в задержке ADD->CMOV (3 цикла), так как одна итерация цикла записывает rbx с CMO, а следующая итерация читает rbx с ADD.

Цикл содержит только 8 мопов слитых доменов, поэтому он может выдавать один раз за 2 цикла. Давление в порте исполнения также не является таким уж плохим узким местом, как задержка sum dep цепочка, но она близка (Sandybridge имеет только 3 порта ALU, в отличие от Haswell 4).

Кстати, писать это как sum += (data[c] >= 128 ? data[c] : 0); взять cmov вне переносимой петлей цепи dep потенциально полезен. Еще много инструкций, но cmov в каждой итерации не зависит. Это компилируется, как и ожидалось в gcc6.3 -O2 и раньше, но gcc7 де-оптимизирует в cmov по критическому пути ( https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82666). (Он также автоматически векторизуется с более ранними версиями gcc, чем if() способ написать это.)

Clang снимает CMOV с критического пути даже с оригинальным источником.

---

gcc -O2 использует ветку (для gcc5.x и старше), которая хорошо предсказывает, потому что ваши данные отсортированы. Поскольку современные процессоры используют предсказание ветвлений для обработки зависимостей управления, цепочка зависимостей, переносимых циклами, короче: просто add (Задержка 1 цикла).

Сравнение и ветвление в каждой итерации являются независимыми благодаря предсказанию ветвления + умозрительному выполнению, которое позволяет продолжить выполнение до того, как направление ветвления будет точно известно.

.L83:   # The inner loop from gcc -O2
    movsx   rcx, DWORD PTR [rdx]  # load with sign-extension from int32 to int64
    cmp     ecx, 127
    jle     .L82        # conditional-jump over the next instruction 
    add     rbp, rcx    # sum+=data[c]
.L82:
    add     rdx, 4
    cmp     rbx, rdx
    jne     .L83

Существует две цепочки зависимостей, переносимых циклами: sum и счетчик петель. sum имеет длину 0 или 1 цикл, а счетчик цикла всегда равен 1 циклу. Однако в Sandybridge цикл равен 5 мопам с плавкими доменами, поэтому он все равно не может выполняться при 1c на каждую итерацию, поэтому задержка не является узким местом.

Вероятно, он выполняется со скоростью примерно одна итерация на 2 цикла (узкое место при пропускной способности команд ветвления), в отличие от одного на 3 цикла для цикла -O3. Следующим узким местом будет пропускная способность ALU uop: 4 ALU uops (в невыполненном случае), но только 3 порта ALU. (ADD может работать на любом порту).

Этот прогноз конвейерного анализа в точности совпадает с вашими временами ~3 секунды для -O3 против ~2 секунд для -O2.

---

Haswell / Skylake может запускать невыполненный случай по одному на каждые 1,25 цикла, поскольку он может выполнить не занятое отделение в том же цикле, что и занятое отделение, и имеет 4 порта ALU. (Или чуть меньше, так как цикл по 5 моп не вполне выдает при 4 моп каждый цикл).

(Только что протестировано: Skylake @ 3,9 ГГц запускает разветвленную версию всей программы за 1,45 секунды или версию без разветвлений за 1,68 секунды. Так что разница там намного меньше.)

---

g++6.3.1 использует cmov даже в -O2, но g++5.4 по-прежнему ведет себя как 4.9.2.

С g++6.3.1 и g++5.4, используя -fprofile-generate / -fprofile-use производит ветвистую версию даже при -O3 (с -fno-tree-vectorize).

CMOV-версия цикла из более нового gcc использует add ecx,-128 / cmovge rbx,rdx вместо CMP/CMOV. Это немного странно, но, вероятно, это не тормозит. ADD записывает выходные регистры, а также флаги, что создает большее давление на количество физических регистров. Но пока это не узкое место, оно должно быть примерно равным.

---

Более новый gcc автоматически векторизует цикл с -O3, что значительно ускоряет работу даже с SSE2. (Например, мой i7-6700k Skylake запускает векторизованную версию за 0,74 с, что примерно вдвое быстрее, чем скаляр. -O3 -march=native за 0,35 с использованием векторов AVX2 256b).

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