учебный пример вероятных() и маловероятных() подсказок компилятора

Question

Как продемонстрировать для студентов удобство использования likely и unlikely подсказки компилятора (__builtin_expect)?

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

Answer 1

Вот один я использую, очень неэффективен реализация чисел Фибоначчи:

#include <stdio.h> 
#include <inttypes.h> 
#include <time.h> 
#include <assert.h> 

#define likely(x) __builtin_expect((x),1) 
#define unlikely(x) __builtin_expect((x),0) 

uint64_t fib(uint64_t n) 
{ 
    if (opt(n == 0 || n == 1)) { 
     return n; 
    } else { 
     return fib(n - 2) + fib(n - 1); 
    } 
} 

int main(int argc, char **argv) 
{ 
    int i, max = 45; 
    clock_t tm; 

    if (argc == 2) { 
     max = atoi(argv[1]); 
     assert(max > 0); 
    } else { 
     assert(argc == 1); 
    } 

    tm = -clock(); 
    for (i = 0; i <= max; ++i) 
     printf("fib(%d) = %" PRIu64 "\n", i, fib(i)); 
    tm += clock(); 

    printf("Time elapsed: %.3fs\n", (double)tm/CLOCKS_PER_SEC); 
    return 0; 
} 

Чтобы продемонстрировать, используя GCC:

~% gcc -O2 -Dopt= -o test-nrm test.c 
~% ./test-nrm 
... 
fib(45) = 1134903170 
Time elapsed: 34.290s 

~% gcc -O2 -Dopt=unlikely -o test-opt test.c 
~% ./test-opt 
... 
fib(45) = 1134903170 
Time elapsed: 33.530s 

Несколько сотен миллисекунд меньше. Это усиление связано с предсказанием программируемой ветви.

Но теперь, за что программист должен действительно делать вместо этого:

~% gcc -O2 -Dopt= -fprofile-generate -o test.prof test.c 
~% ./test.prof 
... 
fib(45) = 1134903170 
Time elapsed: 77.530s /this run is slowed down by profile generation. 

~% gcc -O2 -Dopt= -fprofile-use -o test.good test.c 
~% ./test.good 
fib(45) = 1134903170 
Time elapsed: 17.760s 

С компилятором автоматизированного выполнения профилирования, нам удалось сократить от первоначальных 34.290s до 17.760s. Гораздо лучше, чем с предсказанием программистской ветви!