Как предложить компилятору gcc более вероятную ветку

Пример:

if (almost_always_false_condition) {
       // do something
}

Есть ли способ предложить компилятору, что в 99% состояние будет ложным. Для вычисления условия требуется ~60 циклов, и он не может быть вычислен во время компиляции самим компилятором.

(ГКК 4.3)

5 ответов

Решение

Если вы хотите предложить GCC, что условие может иметь заданное значение в качестве подсказки для организации потока кода, вы должны использовать __builtin_expect( ):

if (__builtin_expect(almost_always_false_condition,0)) {
   // do something
}

Тем не менее, похоже, что вы хотите найти способ избежать оценки состояния, которое __builtin_expect( ) не буду делать Есть ли способ, которым вы можете быстро аппроксимировать условие и выполнять полную проверку только тогда, когда аппроксимация верна:

if (__builtin_expect(fastCheckThatIsTrueIfFullConditionIsTrue,0)) {
    // most of the time, we don't even get to here, so you don't need
    // to evaluate the condition
    if (almostAlwaysFalseCondition) {
        // do something
    }
}

Можете ли вы рассказать нам больше о состоянии?

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

if (a == 5 && somethingexpensive())
{
   ...
}

С расчетом a == 5 дешевле чем somethingexpensive()и если это почти всегда false Вы должны запустить его в первую очередь, чтобы избежать оценки somethingexpensive пункт.

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

static int result = doevalfunctiononlyonce();

if (result)
{
   ....    
}

Таким образом, вы снизили стоимость if к простому поиску памяти.

Если условие изменяется только в ответ на действие в другой процедуре, вы можете обновить глобальную из этой процедуры:

int condition;

void appendToList(int a)
{
   list.append(a);
   if (list.somethingexpensive())
   {
     condition = true;
   } else
   {
     condition = false;
   }
}

void someotherfunction()
{
  // if (list.somethingexpensive())
  if (condition)
  {
    ...
  }
}

Это полезно, если someotherfunction называется намного чаще, чем appendtolist функция.

Прежде всего, сколько циклов проведено в else пункт или в другом месте в программе? Если вы регистрируете профили или делаете стеки, вы тратите не менее 10% своего времени в этом тесте? Если нет, то, вероятно, есть большие проблемы, которые вы должны посмотреть в первую очередь.

Во-вторых, если вы тратите>10% времени в этом тесте, вы должны посмотреть, можно ли настроить алгоритм так, чтобы точки принятия решения были ближе к вероятности 50-50. Точка принятия решения 50-50 выдает 1 бит информации при его выполнении, а точка принятия решения 99-1 дает только около 0,07 бита.* (Т. Е. Мало что говорит, поэтому неэффективно использует циклы ЦП.) Примером этого явления является сравнение линейного поиска с двоичным.

* Если у вас есть точка принятия бинарного решения и вероятности результатов a а также b Выход информации (энтропия) в битах -(a*log(a) + b*log(b))/log(2),

Документация предполагает, что gcc выполняет (или может) выполнять профилированную оптимизацию. Это не то, что я когда-либо пытался сделать с gcc, поэтому не могу дать дальнейших советов, это может стоить того, чтобы вы зашли в Google.

На мой взгляд, лучший способ выполнить такую ​​оптимизацию - это использовать -fprofile-generate а также -fprofile-use опции. Для этого требуется база репрезентативных вариантов использования для сбора информации о том, что вероятно, а что нет, но для этой цели могут использоваться тесты. С другой стороны, код не украшен некрасивыми непереносимыми директивами.

См. https://gcc.gnu.org/onlinedocs/gcc-4.3.6/gcc/Optimize-Options.html для получения дополнительной информации об этих двух параметрах.

Другие вопросы по тегам