Как провести бенчмарк или кто быстрее, Слон или Селедка?

Я часто слышу советы по сравнению алгоритмов — “проведи бенчмарк и будет понятно”. Или сам довольно часто хочу проверить производительность того или иного инструмента или алгоритма.

В сети много анти-примеров как люди проводят бенчмарк. Видел много правильных и успешных бенчмарков, видел кривые бенчмарки. Ниже будет описание как нужно проводить бенчмарк, с простыми примерами на простом C.
Для тех, кто профи в этом я вряд ли открою что то новое, а для тех, кто хочет этому научится — соберу знания в одной статье.

Когда не надо проводить бенчмарк

Да. Начнем с этого. Не надо этого делать сравнение заведомо одинаковых алгоритмов (как в статье http://habrahabr.ru/post/198588/ ) — всегда будет такое стечение обстоятельств, что кто то быстрее, хотя это не так. Можно и нужно провести 15 измерений и получить, что они одинаковы в рамках погрешности, но зачем, если можно посмотреть код и увидеть что они идентичны.

Что меряем?

Всегда нужно понимать что мы меряем: время, IO операции в штуках, МБ по сети/диску. Если мы меряем время мы должны определиться, что мы меряем — real time — реальное “человеческое” время работы алгоритма, cpu time — время затраченное процессором конкретно на этот процесс, “real — cpu” time — время внешних взаимодействий (диск, сеть, другие процессы).

Где меряем?

Мы должны определить разрез в котором будут производится измерения, он должен соответствовать поставленной задаче. Например мы можем замерять время выполнения 1000 раз функции pcre_exec и 1000 раз функции regexec или можем запустить

$ time ./a.out
$ time ./b.out

Результаты этих двух измерений будут разные, т.к. помимо 1000 раз pcre_exec мы еще запустили процесс, прочитали бинарик с диска и скорее всего сделали вывод в консоль. Вам сильно повезет, если они будут похожи на настоящие, но они могут быть и принципиально не верными. Проведя 15-17 измерений мы получим приличный разброс и величину погрешности больше, чем измереная величина.

Окружение?

Что нам может помешять? Другие процессы (хотят cpu, время на переключение процессов, большая таблица с процессами в ядре), конкуренты в IO, конкуренты в сети.
Сломать результаты нашего бенчмарка может отличающееся окружение, но может и идентичное.

Пример ломающего идентичного окружения:
Мы хотим понять кто быстрее Слон или Селедка. Если мы заставим Слона бежать по берегу и Селедку бежать по берегу, то получим бредовый результат. Селедка сдохнет, да и бежать не будет.
Пример ломающего разного окружения:
Мы заставляем Слона бежать в гору, а Селедку плыть по течению. Думаю тут сдохнет Слон.

Суммарно

Мы всегда должны понимать, что проводя бенчмарк мы сравниваем один частный случай и не более. Т.е. libpcre может оказатся медленее posix regular exp с некоторыми регулярками и при некоторых использованиях, а может и быстрее на порядок для других.

Пример

В качестве примера, я хочу сравнить скорость работы libpcre3 и posix regular expressions на примере очень простого регулярного выражения и простой строки. Единственное, что будет замеряно — это время 10 000 000 запусков pcre_exec и regexec.

Исходник pcre3.c:

#include <stdio.h>
#include <pcre.h>
#include <string.h>

#define max 10000000

int main(int argc, char* argv[])
{
    char *pattern = "[cd]";
    char *str = "abcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdef";

    struct timeval  tvStart, tvFinish;

    pcre *re;
    int options = 0;
    const char *error;
    int erroffset;
    re = pcre_compile (pattern, options, &error, &erroffset, NULL);
    if (!re){ // в случае ошибки компиляции
       printf("Error on pcre_compile, exit(1)");
       return 1;
    }
    int ovector[30];
    unsigned int i=0;
    size_t strl = strlen(str);
    gettimeofday(&tvStart, NULL);
    for (i=0; i<max; i++) {
        pcre_exec (re, NULL, str, strl, 0, 0, ovector, 30);
    }
    gettimeofday(&tvFinish, NULL);

    double time_in_mill_start = (tvStart.tv_sec) * 1000 + (tvStart.tv_usec) / 1000; 
    double time_in_mill_end = (tvFinish.tv_sec) * 1000 + (tvFinish.tv_usec) / 1000; 
    printf("Time Start= %fmsn", time_in_mill_start);
    printf("Time End= %fmsn", time_in_mill_end);
    printf("Time Length= %fmsn", time_in_mill_end - time_in_mill_start);
    printf("Iterations=%ldn", max);
    printf("Time per iteration=%fn", (time_in_mill_end - time_in_mill_start) / max);

    return 0;

}

Исходник prex.c:

#include <regex.h>
#include <stdio.h>

#define max 10000000

int main(int argc, char* argv[])
{
    int    status;
    regex_t    re;
    char *pattern = "[cd]";
    const char *string = "abcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdef";

    struct timeval  tvStart, tvFinish;

    if (regcomp(&re, pattern, REG_EXTENDED|REG_NOSUB) != 0) {
	printf("Error on regcompn exit(1)");
        return 1 ;
    }
    unsigned int i=0;
    gettimeofday(&tvStart, NULL);
    for (i=0; i<max; i++) {
	regexec(&re, string, (size_t) 0, NULL, 0);
    }
    gettimeofday(&tvFinish, NULL);

    double time_in_mill_start = (tvStart.tv_sec) * 1000 + (tvStart.tv_usec) / 1000; 
    double time_in_mill_end = (tvFinish.tv_sec) * 1000 + (tvFinish.tv_usec) / 1000; 

    printf("Time Start= %fmsn", time_in_mill_start);
    printf("Time End= %fmsn", time_in_mill_end);
    printf("Time Length= %fmsn", time_in_mill_end - time_in_mill_start);
    printf("Iterations=%ldn", max);
    printf("Time per iteration=%fn", (time_in_mill_end - time_in_mill_start) / max);
    regfree(&re);
    return 0;
}

Собираем:

$ gcc pcre3.c -lpcre -o pcre3.o
$ gcc prex.c -o prex.o

Перезугружаемся в single user mode. Это нужно, чтобы избежать конкурентности процессов в cpu и выделении ram.
Запускаем пару раз “в пустую”, не глядя на результаты

$ ./pcre3.o > /dev/null
$ ./pcre3.o > /dev/null
$ ./prex.o > /dev/null
$ ./prex.o > /dev/null

Это нужно чтобы все что мы используем (например .so библиотеки) были полностью в кеше файловой системы и не мешали нам медленным чтением с диска.

Результаты:

$
$
$ ./pcre3.o
Time Start= 1416480861763.000000ms
Time End= 1416480863174.000000ms
Time Length= 1411.000000ms
Iterations=10000000
Time per iteration=0.000141
$
$
$ ./prex.o
Time Start= 1416480880955.000000ms
Time End= 1416480881920.000000ms
Time Length= 965.000000ms
Iterations=10000000
Time per iteration=0.000097

Вместо заключения

Мы измеряли кто быстрее, Слон или Селдка. Получили результат. Мы не меряли: “кто лучше”, кто ест меньше cpu, не меряли на примере супер больших ли супер маленьких строк. Мы не меряли работу со сложными регулярными выражениями. Для нашего простого частного случая Posix Regular Expressions был быстрее.

P.S. В результате измерений Слон и Селедка не пострадали.

P.P.S. Слон очень хорошо плавает. Обычно слоны передвигаются шагом со скоростью 2-6 км/ч, но на короткое время могут развивать скорость до 35-40 км/ч. Селедки очень хорошо плавают. Скорость селедки я не нашел, т.к. гугл предлагал мне популярный салат.

Автор: piromanlynx

Источник