Как предложить компилятору 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 для получения дополнительной информации об этих двух параметрах.