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

Question

У меня есть эта функция, которая, учитывая код Грея, возвращает следующий код Грея. Вы можете найти более полное объяснение о том, как это работает здесь. Дело в том, что я хотел сделать эту функцию приращения модульной, чтобы приращение кода Грея соответствовало 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

Взято из онлайн-документов GCC:

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

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

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

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

Обновить:

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