Почему я не жертва предсказания ветвей?

Question

Я пишу функцию для создания gaussian фильтра (используя библиотеку armadillo), которая может быть либо 2D, либо 3D в зависимости от количества измерений ввода, который он получает. Вот код:

template <class ty> 
ty gaussianFilter(const ty& input, double sigma) 
{ 
    // Our filter will be initialized to the same size as our input. 
    ty filter = ty(input); // Copy constructor. 

    uword nRows = filter.n_rows; 
    uword nCols = filter.n_cols; 
    uword nSlic = filter.n_elem/(nRows*nCols); // If 2D, nSlic == 1. 

    // Offsets with respect to the middle. 
    double rowOffset = static_cast<double>(nRows/2); 
    double colOffset = static_cast<double>(nCols/2); 
    double sliceOffset = static_cast<double>(nSlic/2); 

    // Counters. 
    double x = 0 , y = 0, z = 0; 

for (uword rowIndex = 0; rowIndex < nRows; rowIndex++) { 
     x = static_cast<double>(rowIndex) - rowOffset; 
     for (uword colIndex = 0; colIndex < nCols; colIndex++) { 
     y = static_cast<double>(colIndex) - colOffset; 
     for (uword sliIndex = 0; sliIndex < nSlic; sliIndex++) { 
      z = static_cast<double>(sliIndex) - sliceOffset; 
      // If-statement inside for-loop looks terribly inefficient 
      // but the compiler should take care of this. 
      if (nSlic == 1){ // If 2D, Gauss filter for 2D. 
      filter(rowIndex*nCols + colIndex) = ... 
      } 
      else 
      { // Gauss filter for 3D. 
      filter((rowIndex*nCols + colIndex)*nSlic + sliIndex) = ... 
      } 
     }  
    } 
} 

Как мы видим, есть Условный оператор внутри самого внутреннего цикла, который проверяет, если размер третьего измерения (nSlic) равна 1. После того, вычисленной в начале функции nSlic не изменит ее значение, поэтому компилятор должен быть достаточно умным, чтобы оптимизировать условную ветвь, и я не должен потерять какую-либо производительность.

Однако ... если я удалю if-инструкцию из цикла, я получаю повышение производительности.

if (nSlic == 1) 
    { // Gauss filter for 2D. 
    for (uword rowIndex = 0; rowIndex < nRows; rowIndex++) { 
     x = static_cast<double>(rowIndex) - rowOffset; 
     for (uword colIndex = 0; colIndex < nCols; colIndex++) { 
     y = static_cast<double>(colIndex) - colOffset; 
     for (uword sliIndex = 0; sliIndex < nSlic; sliIndex++) { 
      z = static_cast<double>(sliIndex) - sliceOffset; 
      {filter(rowIndex*nCols + colIndex) = ... 
     } 
     } 
    } 
    } 
else 
    { 
    for (uword rowIndex = 0; rowIndex < nRows; rowIndex++) { 
     x = static_cast<double>(rowIndex) - rowOffset; 
     for (uword colIndex = 0; colIndex < nCols; colIndex++) { 
     y = static_cast<double>(colIndex) - colOffset; 
     for (uword sliIndex = 0; sliIndex < nSlic; sliIndex++) { 
      z = static_cast<double>(sliIndex) - sliceOffset; 
      {filter((rowIndex*nCols + colIndex)*nSlic + sliIndex) = ...          
     } 
     } 
    } 
    } 

После компиляции с g++ -O3 -c -o main.o main.cpp и измерением времени выполнения обоих вариантов кода я получил следующее:
(1000 повторов, 2D матрицы размера 2048)

Если-внутри:

• 66.0453 секунд
• 64.7701 секунд

Если внешняя:

• 64.0148 секунд
• 63.6808 секунд

Почему не компилятор оптимизировать ветку, если значение nSlic даже не изменится? Мне обязательно нужно перестроить код, чтобы избежать ошибки в for -loop?

Answer 1

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

Answer 2

Ваша ошибка здесь:

оптимизировать условный переход, и я не должен потерять любой производительность

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

Answer 3

Взаимодействие между компилятором и HW заключается в следующем: компилятор может оптимизировать ветвь, делая сам код оптимизированным, но, как вы можете видеть, он генерирует много раздувания кода, поскольку он эффективно дублирует весь цикл , Некоторые компиляторы могут включать эту оптимизацию по умолчанию, а другие могут потребовать явного запроса, чтобы она спросила вас об этом.

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

Еще одно примечание. Возможно, это не обязательно связано с предсказаниями ветвлений, изменение кода может изменить выравнивание в кеше кода или некоторых внутренних циклических буферах, используемых для оптимизации циклов (например, this), что может привести к значительным изменениям в исполнении. Единственный способ узнать - запустить некоторое профилирование на основе счетчиков HW (perf, vtune и т. Д.) И измерить изменение числа ветвей и неправильных прогнозов.