Соответствующая часть источника (по ссылке Godbolt в комментарии, которую вы действительно должны отредактировать в своем вопросе):
const auto cnt = std::count_if(lookups.begin(), lookups.end(),[](const auto& val){
return buckets[hash_val(val)%16] == val;});
Я не проверял заголовки libstdc ++, чтобы увидеть, реализован ли count_if с if() { count++; }, или использует ли он троичный для поддержки кода без ответвлений. Наверное, условно. (Компилятор может выбрать любой, но троичный с большей вероятностью скомпилируется в cmovcc или setcc. Без ветвей).
Похоже, что gcc переоценил стоимость безветвления для этого кода с общей настройкой . -mtune=skylake (подразумевается -march=skylake) дает нам код без ответвлений для этого независимо от -O2 против -O3 или -fno-tree-vectorize против -ftree-vectorize. (На проводнике компилятора Godbolt я также поместил счетчик в отдельную функцию, которая подсчитывает vector<int>&, поэтому нам не нужно разбираться со временем и cout code-gen в main.)
- код ветвления: gcc8.2
-O2 или -O3 и O2/3 -march=haswell или broadwell
- код без ответвления: gcc8.2
-O2/3 -march=skylake.
Странно. Код без ответвлений имеет ту же цену, что и Бродвелл против Skylake. Я задавался вопросом, предпочитает ли Скайлэйк против Хэсвелла безветвление из-за более дешевого cmov. Модель внутренних затрат GCC не всегда соответствует инструкциям x86 при ее оптимизации в середине (в GIMPLE, архитектурно-нейтральном представлении). Он еще не знает, какие инструкции x86 будут фактически использоваться для последовательности без ветвей. Так, может быть, задействована операция условного выбора, и gcc моделирует ее как более дорогую на Haswell, где cmov составляет 2 мопа? Но я протестировал -march=broadwell и все еще получил разветвленный код. Надеемся, что мы можем исключить это, предполагая, что стоимостная модель gcc знает, что Broadwell (не Skylake) был первым Uarch семейства Intel P6 / SnB, который имеет однократные операции cmov, adc и sbb (целочисленные операции с 3 входами). ).
Я не знаю, что еще в опции настройки Skylake в gcc, которая делает его предпочтительным для кода без ответвлений для этого цикла. Сбор данных эффективен на Skylake, но gcc выполняет автоматическую векторизацию (с vpgatherqd xmm) даже с -march=haswell, где это не похоже на выигрыш, потому что сбор дорог, и требует 32x64 => 64-битных умножений SIMD, используя 2x vpmuludq на каждый входной вектор. Может быть, стоит с SKL, но я сомневаюсь, HSW. Также, вероятно, пропущенная оптимизация, чтобы не упаковать элементы dword, чтобы собрать вдвое больше элементов с почти одинаковой пропускной способностью для vpgatherdd.
Я исключил, что функция была менее оптимизирована, потому что она называлась main (и помечалась cold). Как правило, рекомендуется не помещать ваши микробенчмарки в main: компиляторы, по крайней мере, используются для оптимизации main по-другому (например, для размера кода, а не просто для скорости).
Clang делает его без ответвлений даже с -O2.
Когда компиляторам приходится выбирать между ветвлением и ветвлением, у них есть эвристика, которая угадывает, что будет лучше . Если они думают, что это очень предсказуемо (например, вероятно, в основном не принято), это склоняется в пользу ветвления.
В этом случае эвристик мог бы решить, что из всех 2 ^ 32 возможных значений для int найти именно то значение, которое вы ищете, редко. ==, возможно, обманули gcc, думая, что это будет предсказуемо.
Иногда ветвление может быть лучше, в зависимости от цикла, поскольку оно может нарушить зависимость от данных. См. флаг оптимизации gcc -O3 делает код медленнее, чем -O2 для случая, когда он был очень предсказуемым, а -O3 код без ветвей был медленнее.
-O3, по крайней мере, раньше был более агрессивным при if-преобразовании условных выражений в последовательности без ветвей, такие как cmp; lea 1(%rbx), %rcx; cmove %rcx, %rbx, или в этом случае более вероятно xor -зеро / cmp / sete / add. (На самом деле gcc -march=skylake использует sete / movzx, что намного хуже.)
Без каких-либо данных профилирования / инструментария во время выполнения эти предположения могут легко оказаться неверными. В таком случае светит оптимизация по профилю . Скомпилируйте с -fprofile-generate, запустите его, затем скомпилируйте с -fprofile-use, и вы, вероятно, получите код без ответвлений.
Кстати, -O3 обычно рекомендуется в эти дни. Опасен ли уровень оптимизации -O3 в g ++? . Он не включает -funroll-loops по умолчанию, поэтому он раздувает код только при автоматической векторизации (особенно с очень большим полностью развернутым скалярным прологом / эпилогом вокруг крошечного SIMD-цикла, который узкие места на контурах. /facepalm.)