0

Встретил в одном коде конструкцию такого вида

#define EXPECTED(condition)   __builtin_expect(!!(condition), 1)
...
if(EXPECTED(cond1)){
    doSomething1
    return true;
} else if(EXPECTED(cond2)){
    doSomething2
    return true;
} else if(EXPECTED(condN)){
    doSomethingN
    return true;
} else {
    return false;
}

Насколько я понял - это попытка указать, что ветка else - самая маловероятная.

Вопрос - такая вот оптимизация дает хоть что-то?

7
  • Обычно их __builtin_expect и используют пачками, чаще для определения типа переменной через __builtin_types_compatible_p, например: coliru.stacked-crooked.com/a/be12a57be0162860
    – NewView
    19 фев 2019 в 13:12
  • В каком смысле "дает"? Эффект в коде от нее есть. А вот правильно ли угадал автор кода, что "ветка else - самая маловероятная" - вопрос отдельный. 19 фев 2019 в 15:08
  • @NewView: А где в вашем примере __builtin_expect? 19 фев 2019 в 15:13
  • __builtin_choose_expr - но из принципа можно построить и на __builtin_expect
    – NewView
    19 фев 2019 в 15:37
  • 1
    @NewView, это абсолютно разные вещи... __builtin_choose_expr — это однострочный аналог #if#else#endif, а __builtin_expect управляет оптимизацией в зависимости от вероятностного значения выражения.
    – Fat-Zer
    19 фев 2019 в 15:58

1 ответ 1

2

Вопрос - такая вот оптимизация дает хоть что-то?

Да, например на x86/amd64 (да и на большинстве других архитектур), это переставляет ветви местами.

Подопытный код. (на godbolt'е)

#include <stdio.h>
#include <stdlib.h>

#ifdef USE_EXPECTED
#  define UNEXPECTED(condition)   __builtin_expect((condition), 0)
#else // USE_EXPECTED
#  define UNEXPECTED(condition)   (condition)
#endif // USE_EXPECTED

int main(int argc, char **argv) {
    if(UNEXPECTED(argc!=1)){
        fprintf(stderr, "Unexpected number");
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

Компиляция

gcc -O2 -S main.c -o main-normal.S
gcc -DUSE_EXPECTED -O2 -S main.c -o main-unexpected.S

Результат diff -y main-normal.S main-expect.S (несущественные части вырезаны):

.LC0:                                   .LC0:
        .string "Unexpected number"             .string "Unexpected number"
main:                                   main:
.LFB38:                                 .LFB38:
        .cfi_startproc                          .cfi_startproc
        cmpl    $1, %edi                        cmpl    $1, %edi
        je      .L5                   |         jne     .L11
                                      >         xorl    %eax, %eax
                                      >         ret
                                      > .L11:
        subq    $8, %rsp                        subq    $8, %rsp
        movq    stderr(%rip), %rcx              movq    stderr(%rip), %rcx
        leaq    .LC0(%rip), %rdi                leaq    .LC0(%rip), %rdi
        movl    $17, %edx                       movl    $17, %edx
        movl    $1, %esi                        movl    $1, %esi
        call    fwrite@PLT                      call    fwrite@PLT
        movl    $1, %eax                        movl    $1, %eax
        popq    %rdx                            popq    %rdx
        ret                           <
.L5:                                  <
        xorl    %eax, %eax            <
        ret                                     ret

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

В 99% на практике таким оптимизациям, конечно же, — грош цена (по разным причинам), но всегда можно придумать такую задачу/выбрать такую архитектуру, где это может оказаться значимым.

5
  • Вопрос не про то, что делает __builtin_expect, а про то, есть ли смысл запихивать его во все ветки if-else if, дабы соптимизировать конечный else
    – rjhdby
    19 фев 2019 в 16:15
  • @rjhdby: Если автор кода правильно угадал, что конечный else является самой вероятной веткой - то конечно есть смысл. 19 фев 2019 в 16:57
  • @rjhdby, не вижу, почему это может не иметь смысла... и ещё кроме собственно того что это задаёт, что последнее условие наименее вероятно это упорядочивает все остальные условия...
    – Fat-Zer
    19 фев 2019 в 17:14
  • Вот я и спрашиваю - какой смысл? Если все N ветвей, кроме else(который и так в конце) "ожидаемы", то где выигрыш от перестановок? Вот, например, godbolt.org/z/hY3AHj в функции БЕЗ expect все ветки достижимы с близкими затратами и всего два реальных джампа, в функции с exspect, затраты в среднем больше и 4 реальных джампа. Вот я и пытаюсь понять, где оптимизация?
    – rjhdby
    20 фев 2019 в 7:42
  • @rjhdby, во-первых, для варианта с оптимизацией стоило в real-jmp считать выполненные переходы вперёд и не выполненные назад — и те и другие вызывают сброс конвеера, что собственно и является основным предметом оптимизации, значения получились бы 0—1—2—2… а во-вторых, как я уже говорил, такое задание в каждом условии устанавливает порядок P(cond1)>>P(cond2)>>…>>P(else), что собственно и отражается в коде. для того чтобы задать, что min(P(cond1),P(cond2)…)>>else было бы достаточно задать EXPECTED только в последнем условии. Ещё пара примеров.
    – Fat-Zer
    20 фев 2019 в 8:57

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.