Почему векторизация дерева делает этот алгоритм сортировки 2x медленнее?

Алгоритм сортировки этот вопрос становится в два раза быстрее (!), если включен в gcc (4.7.2). Сильно упрощенный C-код этого вопроса (оказалось, что я могу инициализировать массив со всеми нулями, странное поведение производительности остается, но это делает рассуждение намного проще):

#include <time.h>
#include <stdio.h>

#define ELEMENTS 100000

int main() {
  int a[ELEMENTS] = { 0 };
  clock_t start = clock();
  for (int i = 0; i < ELEMENTS; ++i) {
    int lowerElementIndex = i;
    for (int j = i+1; j < ELEMENTS; ++j) {
      if (a[j] < a[lowerElementIndex]) {
        lowerElementIndex = j;
      }
    }
    int tmp = a[i];
    a[i] = a[lowerElementIndex];
    a[lowerElementIndex] = tmp;
  } 
  clock_t end = clock();
  float timeExec = (float)(end - start) / CLOCKS_PER_SEC;
  printf("Time: %2.3f\n", timeExec);
  printf("ignore this line %d\n", a[ELEMENTS-1]);
}

После долгой игры с флагами оптимизации оказалось, что -ftree-vectorize также дает это странное поведение, поэтому мы можем взять -fprofile-arcs из вопроса. После профилирования с помощью perf я обнаружил, что единственное релевантное различие:

Быстрый случай gcc -std=c99 -O2 simp.c (работает в 3.1s)

    cmpl    %esi, %ecx
    jge .L3
    movl    %ecx, %esi
    movslq  %edx, %rdi
.L3:

Медленный случай gcc -std=c99 -O2 -ftree-vectorize simp.c (работает в 6.1s)

    cmpl    %ecx, %esi
    cmovl   %edx, %edi
    cmovl   %esi, %ecx

Что касается первого фрагмента: учитывая, что массив содержит только нули, мы всегда переходим к .L3. Это может сильно выиграть от предсказания ветвей.

Я полагаю, что инструкции cmovl не могут воспользоваться предсказанием ветвления.

Вопросы:

  • Верны ли все мои предположения? Это делает алгоритм медленным?

  • Если да, то как я могу предотвратить gcc из этой инструкции (за исключением тривиального обходного пути -fno-tree-vectorization, конечно), но при этом делая как можно больше оптимизаций?

  • Что это за -ftree-vectorization? Документация довольно смутно, мне нужно немного больше объяснений, чтобы понять, что происходит.

Обновление: Так как оно появилось в комментариях: странное поведение производительности w.r.t. флаг -ftree-vectorize остается со случайными данными. Как указывает Якк, для сортировки выбора на самом деле сложно создать набор данных, который привел бы к множеству неверных предсказаний отрасли.

Так как он также появился: у меня есть процессор Core i5.

На основе комментария Якка, я создал тест. Код ниже (онлайн без повышения), конечно, уже не является алгоритмом сортировки; Я только вынул внутреннюю петлю. Его единственная цель - изучить эффект предсказания ветвей: Мы пропускаем ветвь if в цикле for с вероятностью p.

#include <algorithm>
#include <cstdio>
#include <random>
#include <boost/chrono.hpp>
using namespace std;
using namespace boost::chrono;
constexpr int ELEMENTS=1e+8; 
constexpr double p = 0.50;

int main() {
  printf("p = %.2f\n", p);
  int* a = new int[ELEMENTS];
  mt19937 mt(1759);
  bernoulli_distribution rnd(p);
  for (int i = 0 ; i < ELEMENTS; ++i){
    a[i] = rnd(mt)? i : -i;
  }
  auto start = high_resolution_clock::now();
  int lowerElementIndex = 0;
  for (int i=0; i<ELEMENTS; ++i) {
    if (a[i] < a[lowerElementIndex]) {
      lowerElementIndex = i;
    }
  } 
  auto finish = high_resolution_clock::now();
  printf("%ld  ms\n", duration_cast<milliseconds>(finish-start).count());
  printf("Ignore this line   %d\n", a[lowerElementIndex]);
  delete[] a;
}

Интересующие петли:

Это будет обозначаться как cmov

g++ -std=c++11 -O2 -lboost_chrono -lboost_system -lrt branch3.cpp

    xorl    %eax, %eax
.L30:
    movl    (%rbx,%rbp,4), %edx
    cmpl    %edx, (%rbx,%rax,4)
    movslq  %eax, %rdx
    cmovl   %rdx, %rbp
    addq    $1, %rax
    cmpq    $100000000, %rax
    jne .L30

Это будет обозначаться как no cmov, флаг -fno-if-conversion был указан Turix в его ответе.

g++ -std=c++11 -O2 -fno-if-conversion -lboost_chrono -lboost_system -lrt branch3.cpp

    xorl    %eax, %eax
.L29:
    movl    (%rbx,%rbp,4), %edx
    cmpl    %edx, (%rbx,%rax,4)
    jge .L28
    movslq  %eax, %rbp
.L28:
    addq    $1, %rax
    cmpq    $100000000, %rax
    jne .L29

Разница бок о бок

cmpl    %edx, (%rbx,%rax,4) |     cmpl  %edx, (%rbx,%rax,4)
movslq  %eax, %rdx          |     jge   .L28
cmovl   %rdx, %rbp          |     movslq    %eax, %rbp
                            | .L28:

Время выполнения как функция параметра Бернулли p

effect of branch prediction

Код с инструкцией cmov абсолютно нечувствителен к p. Код без инструкции cmov является победителем, если p<0.26 или 0.81<p и не более 4.38x быстрее (p=1). Конечно, худшая ситуация для предсказателя ветвления составляет около p=0.5, где код на 1.58x медленнее, чем код с инструкцией cmov.

Ответы

Ответ 1

Примечание. Отвечено на вопрос до добавления графика к вопросу; некоторые ссылки на код сборки здесь могут быть устаревшими.

(адаптирован и расширен из нашего выше чата, что было достаточно стимулирующим, чтобы заставить меня сделать немного больше исследований.)

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

Повторите свой третий вопрос: хотя в вашем случае фактически нет векторизации, начиная с шага 11 ( "Условное исполнение" ) здесь, кажется, что один шагов, связанных с оптимизацией векторизации, - это "сгладить" условные выражения в целых циклах, как этот бит в вашем цикле:

if (a[j] < a[lowerElementIndex]
    lowerElementIndex = j;

По-видимому, это происходит, даже если нет векторизации.

Это объясняет, почему компилятор использует условные инструкции перемещения (cmovl). Цель состоит в том, чтобы полностью избежать ветки (в отличие от попытки правильно ее предсказать). Вместо этого две команды cmovl будут отправляться по конвейеру до того, как будет получен результат предыдущего cmpl, и результат сравнения будет "переадресован", чтобы включить/предотвратить перемещение до их обратной записи (т.е. До они фактически вступают в силу).

Обратите внимание, что если цикл был векторизован, это могло бы стоить того, чтобы он дошел до точки, где несколько итераций через цикл могли эффективно выполняться параллельно.

Тем не менее, в вашем случае попытка оптимизации на самом деле обходится, потому что в сплющенном цикле два условных перемещения отправляются через конвейер каждый раз через цикл. Это само по себе также может быть не так уж и плохим, за исключением того, что существует опасность RAW-данных, которая вызывает второе перемещение (cmovl %esi, %ecx), чтобы ждать завершения доступа к массиву/памяти (movl (%rsp,%rsi,4), %esi), даже если результат будет в конечном счете проигнорирован. Отсюда огромное время, потраченное на это cmovl. (Я бы ожидал, что это проблема с тем, что ваш процессор не имеет достаточно сложной логики, встроенной в реализацию предикации/пересылки, чтобы справиться с опасностью.)

С другой стороны, в неоптимизированном случае, как вы правильно поняли, предсказание ветвления может помочь избежать необходимости ждать результата соответствующего доступа к массиву/памяти (инструкция movl (%rsp,%rcx,4), %ecx). В этом случае, когда процессор правильно прогнозирует взятую ветвь (которая для массива all-0 будет выполняться каждый раз, но [равно] в случайном массиве должно [по-прежнему] быть грубо больше, чем [ отредактировано за комментарий @Yakk] в полтора раза), ему не нужно ждать, пока доступ к памяти завершится, и поставит в очередь следующие несколько инструкций в цикле. Таким образом, при правильных прогнозах вы получаете импульс, тогда как в неверных прогнозах результат не хуже, чем в "оптимизированном" случае, и, более того, лучше из-за способности иногда избегать двухзначных "cmovl инструкций в трубопровод.

[Следующее было удалено из-за моего ошибочного предположения о вашем процессоре за ваш комментарий.]
Вернемся к вашим вопросам, я бы предложил посмотреть на эту ссылку выше, чтобы узнать больше о флагах, относящихся к векторизации, но, в конце концов, я уверен, что прекрасно игнорировать эту оптимизацию, учитывая, что ваш Celeron не способен (в этом контексте).

[Добавлено после удаления выше]
Повторите свой второй вопрос ( "... как я могу предотвратить gcc от испускания этой инструкции..." ), вы можете попробовать флаги -fno-if-conversion и -fno-if-conversion2 (не уверены, что они всегда работают - они больше не работают мой mac), хотя я не думаю, что ваша проблема связана с инструкцией cmovl вообще (т.е. я не всегда буду использовать эти флаги), просто с ее использованием в этом конкретном контексте (где предсказание ветвлений будет очень полезный, данный @Yakk указывает на ваш алгоритм сортировки).