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

Question

Я нахожу эту тему Why is it faster to process a sorted array than an unsorted array?. И попробуйте запустить этот код. И я нахожу странное поведение. Если я скомпилирую этот код с флагом оптимизации -O3, то для запуска нужно выполнить 2.98605 sec. Если я компилирую с -O2, то он принимает 1.98093 sec. Я пытаюсь запустить этот код несколько раз (5 или 6) на одной машине в одной и той же среде, я закрываю все другое программное обеспечение (хром, скайп и т. Д.).

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. Спасибо за помощь.

P.S. добавить код

#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 CPU, в соответствии с Agner Fog's instruction tables См. Также тег x86 wiki). Это one of the cases where cmov sucks.

Если данные были даже умеренно непредсказуемыми, cmov, вероятно, был бы победой, поэтому это довольно разумный выбор для компилятора. (Тем не менее, compilers may sometimes use branchless code too much.) .)

I put your code on the Godbolt compiler explorer, чтобы увидеть 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, но она близка (у Sandybridge только 3 порта ALU, в отличие от 4-го Хасуэлла).

BTW, записывая его как sum += (data[c] >= 128 ? data[c] : 0);, чтобы взять cmov из цепочки отрезков цепи, потенциально полезной. Все еще много инструкций, но cmov на каждой итерации не зависит. Это compiles as expected in gcc6.3 -O2 and earlier, но 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 циклу. Тем не менее, петля - это 5 совпадающих доменных доменов на Sandybridge, поэтому в любом случае она не может выполняться с 1c на итерацию, поэтому латентность не является узким местом.

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

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

---

Хасуэллы/Skylake может запустить не-взятый случай, в один за 1.25 циклы, так как он может выполнить не-взятую отрасль в том же цикле, как взятая отрасль и имеет 4 порта ALU. (Или немного меньше с a 5 uop loop doesn't quite issue at 4 uops every cycle).

(Только испытания:.. Skylake @ 3.9GHz запускает версию ветвистой всей программы в 1.45s, или безфилиальные версию в 1.68s Таким образом, разница гораздо меньше есть)

---

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

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

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

---

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

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