Ответ 1
gcc -O3 использует cmov для условного, поэтому он удлиняет цепочку зависимостей, связанных с циклом, чтобы включить cmov (это 2 часа и 2 цикла латентности на вашем процессоре Intel Sandybridge в соответствии с таблицами инструкций Agner Fog. См. также x86 tag wiki). Это один из случаев, когда cmov отстой.
Если данные были даже умеренно непредсказуемыми, cmov, вероятно, был бы победой, поэтому это довольно разумный выбор для компилятора. (Тем не менее, компиляторы могут иногда использовать нераспространяемый код слишком много.)
I поместите свой код в проводник-компилятор 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, но оно близко (у Sandybridge только 3 порта ALU, в отличие от Haswell 4).
BTW, записывая его как sum += (data[c] >= 128 ? data[c] : 0);, чтобы вывести cmov из цепочки отрезков цикла, потенциально полезно. Все еще много инструкций, но 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 циклу. Тем не менее, цикл - это 5 совпадающих доменных доменов на Sandybridge, поэтому он не может выполнять в 1c на итерацию в любом случае, поэтому латентность не является узким местом.
Он, вероятно, работает примерно на одну итерацию за 2 цикла (узкое место по пропускной способности ветки), против одного на 3 цикла для цикла -O3. Следующим узким местом была бы пропускная способность ALU uop: 4 ALU uops (в незанятом случае), но только 3 порта ALU. (ADD может работать на любом порту).
Прогнозирование конвейерного анализа в точности совпадает с вашими таймингами ~ 3 сек для -O3 против ~ 2 секунд для -O2.
Haswell/Skylake может запускать неиспользуемый случай за один раз за 1,25 цикла, так как он может выполнить невозбранную ветвь в том же цикле, что и принятая ветвь, и имеет 4 порта ALU. (Или немного меньше, так как цикл 5 uop не совсем выдает в 4 раза каждый цикл).
(Только что протестировано: Skylake @3.9GHz запускает разветвленную версию всей программы в 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 дважды, потому что он не понимает, что он может просто увеличивать нуль вместо sign-extend, когда условие уже обнулено всеми отрицательными целыми числами.