Использование __builtin_expected для проверки границ

Question

У меня есть эта функция, которая с учетом Gray code возвращает следующий код Grey. Вы можете найти более полное объяснение того, как это работает here. Дело в том, что я хотел сделать эту функцию приращения модульной, так что приращение кода серого, соответствующего UINT_MAX, возвращает код серого, соответствующий 0 (соответственно самый старший бит и 0). Поскольку это не поведение по умолчанию, я добавил чек для этого особого случая. Вот полный алгоритм:

unsigned next_gray(unsigned gray) 
{ 
    static const unsigned msb 
     = 1u << (CHAR_BITS - sizeof(unsigned) - 1u); 

    // gray is odd 
    if (__builtin_parity(gray)) 
    { 
     if (__builtin_expect(gray == msb, false)) 
     { 
      return 0u; 
     } 
     else 
     { 
      unsigned y = gray & -gray; 
      return gray^(y << 1u); 
     } 
    } 

    // gray is even 
    return gray^1; 
} 

Итак, фактический вопрос на самом деле о предсказании ветвления. Я часто читал, что __builtin_expect должен использоваться только тогда, когда ветвь действительно может быть выбрана или действительно вряд ли будет выбрана, что является обычным примером для ускорения программы, когда ошибок нет.

Учитывая, что я не обрабатываю случай с ошибкой, я не уверен, что использование __builtin_expect для проверки границ, как это, является хорошей идеей. Является ли это хорошим местом для использования __builtin_expect или увеличивает максимальное значение, достаточно общую операцию для обмана прогноза ветвления?

Примечание: как всегда, комментарии и ответы подчеркнуть то, что не ясно, в моих вопросах :)

дам немного больше контекста: эта функция предназначается, чтобы быть частью библиотеки, разработанные для ради того, чтобы быть библиотекой и не использоваться каким-либо конкретным проектом, как знать. Поэтому добавление __builtin_expect подразумевает, что я ожидаю, что люди будут в основном увеличивать другие значения, а затем максимальное значение; без какого-либо фактического проекта, я хочу знать, является ли это безопасным предположением.

Answer 1

Взятые из the GCC online docs:

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

Это хорошее место для использования __builtin_expect или увеличивает максимальное значение, достаточно общую операцию для обмана прогноза ветвления?

Все это зависит от вашего приложения. Если значение gray равномерно распределено, то оно будет 1 из (UINT_MAX+1), но можете ли вы сказать это точно? Вот почему docs рекомендую использовать -fprofile-arcs.

gcov wikipedia article действительно содержит простой пример использования -fprofile-arcs и gcov, чтобы получить информацию для принятия обоснованного решения.

Update:

Если вы не можете профиль, то при прочих равных условиях края случай gray == msb очень маловероятно, так что вы, вероятно, безопасно с использованием __builtin_expect. Однако, если вы не можете настроить профиль, потому что не знаете, как будет использоваться ваша библиотека, это больше похоже на pessimization, чем на оптимизацию.Если я использую вашу библиотеку и всегда перехожу в gray, так что она равна msb, так как ваша библиотека будет не так быстро для меня. Общие библиотеки, которые не написаны с конкретным приложением, обычно стараются быть хорошими для среднего случая или без каких-либо предположений о вводе. Вот почему вы видите различные реализации malloc, такие как jemalloc и tcmalloc. Оба оптимизированы для очень конкретных случаев использования, и если вы используете его таким образом, который не похож на то, что он был оптимизирован для него, это не будет сделано. Также может вас заинтересовать this blog article.