Сравнение строк: strcmp или посимвольно. Benchmark в черновиках

Я искал ответ на вопрос «что быстрее»

strcmp(in, "first") == 0

или

strlen(in) == 5 && in[0] == 'f' && in[1] == 'i' && in[2] == 'r' && in[3] == 's' && in[4] == 't'

И, кажется, нашёл…

Задача

Проверить, не является ли строка «специальным маркером». Всего маркеров пять: «first», «last», «even», «odd», «exit», причём по «exit» программа завершается.

За те несколько дней что я изучаю C, я встречал два подхода к сравнению: функцией strcmp и побайтово (ака посимвольно). Мнения знакомых и коллег о том, какой подход работает быстрее, разделились. Значит нужен benchmark.

Исходники

Решение, использующее strcmp, я буду называть bench_str:

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

int main() {
    char in[100] = "";

    while (scanf("%s", in)) {
        if (strcmp(in, "first") == 0) {
            printf("F\n");
        } else if (strcmp(in, "last") == 0) {
            printf("L\n");
        } else if (strcmp(in, "odd") == 0) {
            printf("O\n");
        } else if (strcmp(in, "even") == 0) {
            printf("E\n");
        } else if (strcmp(in, "exit") == 0) {
            return 0;
        } else {
            printf("unknown\n");
        }
    }

    return 0;
}

Решение, использующее побайтовое сравнение, я буду называть bench_char:

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

int main() {
    char in[100] = "";

    while (scanf("%s", in)) {
        if (strlen(in) == 5 && in[0] == 'f' && in[1] == 'i' && in[2] == 'r' && in[3] == 's' && in[4] == 't') {
            printf("F\n");
        } else if (strlen(in) == 4 && in[0] == 'l' && in[1] == 'a' && in[2] == 's' && in[3] == 't') {
            printf("L\n");
        } else if (strlen(in) == 3 && in[0] == 'o' && in[1] == 'd' && in[2] == 'd') {
            printf("O\n");
        } else if (strlen(in) == 4 && in[0] == 'e' && in[1] == 'v' && in[2] == 'e' && in[3] == 'n') {
            printf("E\n");
        } else if (strlen(in) == 4 && in[0] == 'e' && in[1] == 'x' && in[2] == 'i' && in[3] == 't') {
            return 0;
        } else {
            printf("unknown\n");
        }
    }

    return 0;
}

Компилятся и работают они одинаково корректно:

$ gcc -Wall -o ./bin/bench_str bench_str.c && ./bin/bench_str
some
unknown
first
F
last
L
exit

$ gcc -Wall -o ./bin/bench_char bench_char.c && ./bin/bench_char
any 
unknown
odd
O
even
E
exit

Входные данные

Используйте ваш любимый скриптовый язык для создания файла, содержащего изрядное число входных строк. Мне понадобилось 10M строк для того, чтобы время исполнения занимало несколько секунд. На меньших интервалах разница в скорости может быть не так заметна, и влияние прочих процессов, отжирающих ваш CPU, будет сказываться сильнее.

Я сделал make_input.php:

<?php
$variants = array(
    "first",
    "last",
    "even",
    "odd",
    "final",
    "long",
    "event",
    "omnipotent",
    "bad",
    "very bad",
    "ugly",
);

for ($i = 0; $i < 10000000; $i++) {
    $str = $variants[array_rand($variants)];
    echo $str . PHP_EOL;
}

echo "exit" . PHP_EOL;

$ php make_input.php >/tmp/input

Обратите внимание, поскольку input читается бесконечно while (scanf("%s", in)), последней строкой в файле идёт «exit» — иначе программа зациклится.

Таким набором я пытался добиться максимального разнообразия входных строк: есть неподходящие по длине, есть начинающиеся с «неправильных» букв, есть строки с «неправильными» концами, ну и, наконец, есть подходящие строки.

Push the button, Max!

Выполняем! Я перенаправил вывод в /dev/null, чтобы не тратить ресурсы на вывод результата на экран: это тоже вносит погрешность и занимает приличное время. Если не собираетесь перенаправлять вывод, я рекомендую уменьшить число входных строк на порядок или два.

Итак, на сцене побайтовое сравнение:

$ time ./bin/bench_char </tmp/input 1>/dev/null

real    0m2.962s
user    0m2.908s
sys     0m0.048s

I'd like to see the Great Leslie try THAT one! ©

На сцене strcmp:

$ time ./bin/bench_str </tmp/input 1>/dev/null

real    0m2.495s
user    0m2.448s
sys     0m0.036s

Конечно, от запуска к запуску результаты немного варьируются, но в целом картина не меняется: strcmp примерно на полсекунды быстрее, а это около 20%! И я даже молчу о читаемости кода.

В качестве крайних кейсов можно оставить только корректные строки или только некорректные.

В случае использования только корректных строк, время выполнения обеих реализаций сокращается, и преимущество strcmp падает до 15%:

$ time ./bin/bench_char </tmp/input 1>/dev/null

real    0m2.026s
user    0m1.992s
sys     0m0.028s

$ time ./bin/bench_str </tmp/input 1>/dev/null

real    0m1.739s
user    0m1.720s
sys     0m0.012s

В случае использования только некорректных строк, время выполнения bench_char практически не меняется, а вот bench_str выполняется немного дольше.В целом преимущество strcmp падает примерно до 10%:

$ time ./bin/bench_char </tmp/input 1>/dev/null

real    0m2.986s
user    0m2.936s
sys     0m0.044s

$ time ./bin/bench_str </tmp/input 1>/dev/null

real    0m2.722s
user    0m2.676s
sys     0m0.032s

Картинка к этому делу:

Case #1: только правильные строки
Case #2: микс
Case #3: только неправильные

Если кто-то знает почему я не прав и в каком случае будет обратная картина — будет очень интересно расширить кругозор.
Но если кто-то подробно расскажет почему так, будет вообще суперски!

Спасибо за внимание!

strlen(in) == 5 && in[0] == 'f' && in[1] == 'i' && in[2] == 'r' && in[3] == 's' && in[4] == 't'

in[0] == 'f' && in[1] == 'i' && in[2] == 'r' && in[3] == 's' && in[4] == 't' && in[5] == 0

$ time ./bin/bench_str </tmp/input 1>/dev/null

real    0m2.256s
user    0m2.216s
sys     0m0.036s

$ time ./bin/bench_char </tmp/input 1>/dev/null

real    0m1.818s
user    0m1.776s
sys     0m0.020s

size_t __cdecl strlen (const char * str) {
        const char *eos = str;
        while( *eos++ ) ;
        return( eos - str - 1 );
}

int __cdecl strcmp (const char * src, const char * dst)
{
        int ret = 0 ;

        while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
                ++src, ++dst;

        if ( ret < 0 )
                ret = -1 ;
        else if ( ret > 0 )
                ret = 1 ;

        return( ret );
}

    getAllData();

    timeval tv1;
    timeval tv2;
    gettimeofday(&tv1, 0);
    int64 tp1 = tv1.tv_sec + tv1._usec;

    work();

    gettimeofday(&tv2, 0);
    int64 tp2 = tv2.tv_sec + tv2._usec;
    int64 microsec = tp2 - tp1;

while (scanf("%s", in)) {
        if (in[0] == 'e' ) {
            return 0;
        } else {
            printf("unknown\n");
        }
    }

if (strlen(in) == 5 && in[0] == 'f' && in[1] == 'i' && in[2] == 'r' && in[3] == 's' && in[4] == 't') {

if (in[0] == 'f' && in[1] == 'i' && in[2] == 'r' && in[3] == 's' && in[4] == 't' && in[5] == '\0') {

==========  ===========  ================  =================================
Компилятор  Оптимизации  Результат strlen  Результат посимвольного сравнения
==========  ===========  ================  =================================
clang-3.3   -O0          16,0              13,6
clang-3.3   -O3          15,3              12,4
gcc-4.7.3   -O0          16,6              12,8
gcc-4.7.3   -O3          16,7              12,8
pathcc⊃1;     -O0          15,5              12,5
pathcc⊃1;     -O3          15,7              12,9
tcc-0.9.26  -O0          15,8              11,9
tcc-0.9.26  -O3          15,5              12,9
pcc⊃2;        -O0          15,9              13,7
pcc⊃2;        -O3          16,3              13,4
==========  ===========  ================  =================================

⊃1; 5.0.1_pre20131115
⊃2; 1.0.1_pre20131013