Сравнение строк: 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: только неправильные

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

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