Как понять сложную скорость

Извините, может быть, слишком абстрактный вопрос, но для меня это вполне практично + может быть, некоторые эксперты имеют схожий опыт и могут объяснить это.

У меня есть большой код размером около 10000 строк.

Я замечаю, что если в определенном месте я положил

if ( expression ) continue;

где выражение всегда false (дважды проверено с логикой кода и cout), но зависит от неизвестных параметров (поэтому компилятор не может просто избавиться от этой строки во время компиляции) скорость программы увеличено на 25% (результат расчета одинаковый). Если я измеряю скорость самого цикла, коэффициент ускорения больше 3.

Почему это может случиться и какие возможные способы использовать эту возможность ускорения без таких трюков?

P.S. Я использую оптимизацию gcc 4.7.3, -O3.

Дополнительная информация:

Я пробовал два разных выражения, оба работают.
Если я изменил строку на:
```
if ( expression ) { cout << " HELLO " << endl; continue; };
```
скорость ушла.
Если я изменил строку на:
```
expression;
```
скорость ушла.
Код, который окружает строку, выглядит следующим образом:
```
for ( int i = a; ;  ) {
  do {
    i += d;
    if ( d*i > d*ilast ) break;

      // small amount of calculations, and conditional calls of continue;

  } while ( expression0 );
  if ( d*i > dir*ilast ) break;

  if ( expression ) continue;

   // very big amount calculations, and conditional calls of continue;

}
```
цикл for выглядит странно. Это потому, что я изменил петли, чтобы поймать эту горло бутылки. Изначально выражение было равно выражению 0, а вместо do-loop у меня было только это.

Я попытался использовать __builtin_expect, чтобы понять предсказание ветвей. С

  // the expression (= false) is supposed to be true by branch prediction.
if ( __builtin_expect( !!(expression), 1) ) continue;

скорость увеличивается на 25%.

  // the expression (= false) is supposed to be false by branch prediction.
if ( __builtin_expect( !!(expression), 0) ) continue;

скорость ушла.

Если я использую -O2 вместо -O3, эффект исчезнет. Код немного (~ 3%) медленнее, чем быстрая версия O3 с ложным условием.
То же самое для "-O2 -finline-functions -funswitch-loops -fpredictive-commoning -fgcse-after-reload -ftree-vectorize". С еще одним вариантом: "-O2 -finline-functions -funswitch-loops -fpredictive-commoning -fgcse-after-reload -ftree-vectorize -fipa-cp-clone" эффект усиливается. С "линией" скорость такая же, без "линии" код на 75% медленнее.

Причина заключается только в следующем условном операторе. Таким образом, код выглядит следующим образом:

for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  if ( expression ) continue;

    // calculations1

  if ( expression2 ) {
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

Значение выражения2 почти всегда ложно. Поэтому я изменил его следующим образом:

for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  // if ( expression ) continue; // don't need this anymore

    // calculations1

  if ( __builtin_expect( !!(expression2), 0 ) ) { // suppose expression2 == false
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

И получили желаемые 25% ускорения. Еще немного. И поведение больше не зависит от критической линии.

Если кто-то знает материалы, которые могут объяснить это поведение без догадок, я буду очень рад прочитать и принять их ответ.

Ответ 1

Нашел.

Причина была в справедливом следующем условном операторе. Таким образом, код выглядит следующим образом:

for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  if ( expression ) continue;

    // calculations1

  if ( expression2 ) {
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

Значение выражения2 почти всегда ложно. Поэтому я изменил его следующим образом:

for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  // if ( expression ) continue; // don't need this anymore

    // calculations1

  if ( __builtin_expect( !!(expression2), 0 ) ) { // suppose expression2 == false
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

И получили желаемые 25% ускорения. Еще немного. И поведение больше не зависит от критической линии.

Я не уверен, как это объяснить, и не может найти достаточно материала по предсказанию ветвей.

Но я догадываюсь, что нужно пропустить вычисления2, но компилятор не знает об этом и предположим, что expression2 == true по умолчанию. Между тем, предположим, что при простой проверке

if ( expression ) continue;

выражение == false и прекрасно пропускает вычисления2, как это должно быть сделано в любом случае. Если в случае, если мы имеем более сложные операции (например, cout), предположим, что выражение истинно и трюк не работает.

Ответ 2

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

Это почти всегда приводит к худшему коду. Почему этого не происходит, я могу только предположить одно: вы не компилировали данные профилирования. Следовательно, компилятор должен делать предположения. В частности, он должен делать предположения о возможности того, что ветвь будет взята во время выполнения.

Ясно, что поскольку сделанные им предположения различны, вполне возможно, что полученный код отличается скоростью.

Ответ 3

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

Единственное, что я могу предложить, чтобы помочь вам сузить, если это проблема оптимизации компилятора или оптимизация после компиляции (ЦП), заключается в том, чтобы снова скомпилировать ваш код с помощью -O2 vs -O3, но на этот раз добавьте следующие дополнительные опции: -fverbose-asm -S. Проведите каждый из выходов в два разных файла, а затем запустите что-то вроде sdiff, чтобы сравнить их. Вы должны увидеть много различий.

К сожалению, без хорошего понимания кода ассемблера, будет сложно сделать головы или хвосты, и, честно говоря, не так много людей в Qaru имеют терпение (или время) потратить больше, чем на несколько минут на это вопрос. Если вы не владеете сборкой (предположительно x86), я бы предложил найти сотрудника или друга, который поможет вам разобрать вывод сборки.