Бенчмаркинг cgrep, ack и hlgrep

Когда-то я сравнивал cgrep и ack с точки зрения функциональных возможностей, пришла пора сравнить их скорости выполнения. Кроме того, недавно мне удалось серьезно оптимизировать программу hl, да так, что при рекурсивном грепе она стала во многих случаях быстрее, чем ack. Сильной оптимизации было подвергнуто время старта программы, поэтому преимущество в скорости особенно заметно при небольшом объеме входных данных. Как и ack, hl написана на perl, но реализует другую функциональность, а именно богатую подсветку входных данных, в том числе на основе сниппетов. Таким образом, рекурсивный греп в hl — возможность чисто факультативная, без большого количества опций, доступных в cgrep и ack. Тем интересней добавить его для сравнения к двум последним. Я не стал добавлять для сравнения стандартный grep. Ему по плечу такие простые задачи, как рекурсивный поиск символов, однако он настолько быстр, что с легкостью опережает на порядок все три узкоспециализированные программы (в частности, на моей машине скорость поиска символов ARGS программой grep внутри директории /usr/include/boost в четыре раза превосходит скорость cgrep). Для бенчмаркинга я использовал замечательную программу bench, которая по сути является простым объединением библиотек criterion (я писал о criterion здесь) и turtle. Поскольку я хочу погонять шелл-функциию cgr, представленную в статье, ссылка на которую приводится в самом начале данной статьи, мне придется обернуть команду для bench в bash -ci — ведь turtle в лице bench не является полноценной bash-совместимой оболочкой и не способна загружать функции bash. Для hl я тоже буду использовать шелл-функцию hlgrep, которая определена так:

function hlgrep
{
    `env which hl` -t -r -n "$@" |
            sed 's/:\(\x1b\[22;38;5;224;49m\)\([[:digit:]]\+\)'`
               `'\(\x1b\[22;38;5;248;49m\)\(\x1b\[0m\): / ⎜ \1\2\1\3 ⎜ /' |
            column -t -s⎜ -o⎜ |
            sed 's/\(\s\+\)\(\(\x1b\[22;38;5;224;49m\)[[:digit:]]\+\3'`
               `'\x1b\[22;38;5;248;49m\)\(\s\+\)/\4\2\1/' |
            hl -u -216 '\x{239C}'
}

Но даже чистую cgrep нужно будет обернуть в bash. Проблема в том, что bench подменяет канал stdin в дочерних процессах, запущенных для тестирования, на новый канал, а cgrep, определив подмену, считает, что последний аргумент его командной строки, который обычно указывает на директорию для чтения входных файлов, должен быть просто еще одним элементом для поиска. Таким образом, нам придется сначала выполнить cd, а уже затем запускать cgrep, но уже без ссылки на директорию. Проще всего это сделать в отдельной оболочке. По той же самой причине подмены stdin, в ack нужно будет добавить специальную опцию --nofilter, которая, впрочем, не должна повлиять на его скорость. Есть еще один тонкий момент, связанный с bench: он аварийно завершается в случае, если тестируемая программа возвращает не нулевое значение. Именно это делает ack, если не находит ни одного совпадения. Поэтому перед запуском bench следует проверить, что совпадения имеются для всех тестов с ack (и, автоматически, для других тестируемых программ), при этом желательно, чтобы совпадений было больше — в конце концов мы тестируем полезную нагрузку. В качестве сценариев для тестирования я выбрал поиск символов ARGS в директории /usr/include/boost на моей машине и поиск символов parse внутри относительно небольшого проекта cexmc. Во втором случае я проверил также чистые cgrep, hl и ack. Каждый тест длился по 60 секунд. И вот что из этого вышло.

bench -v2 -L60 \
'bash -ci "(cd /usr/include/boost; cgr ARGS)"' \
'bash -ci "(cd /usr/include/boost; hlgrep ARGS)"' \
'bash -ci "(cd /usr/include/boost; ack --nofilter ARGS)"' \
'bash -ci "(cd ~/devel/cexmc; cgr parse)"' \
'bash -ci "(cd ~/devel/cexmc; hlgrep parse)"' \
'bash -ci "(cd ~/devel/cexmc; ack --nofilter parse)"' \
'bash -ci "(cd ~/devel/cexmc; cgrep -r parse)"' \
'bash -ci "(cd ~/devel/cexmc; hl -r parse)"'  \
'bash -ci "(cd ~/devel/cexmc; ack --nofilter --noenv parse)"' \
-o ~/bench-cgrep-hlgrep-ack-60s.html
benchmarking bench/bash -ci "(cd /usr/include/boost; cgr ARGS)"
analysing with 1000 resamples
measurement overhead 624.0 ns
bootstrapping with 11 of 12 samples (91%)
time                 694.1 ms   (644.7 ms .. 738.5 ms)
                     0.992 R²   (0.982 R² .. 0.999 R²)
mean                 667.6 ms   (653.5 ms .. 687.1 ms)
std dev              29.20 ms   (19.88 ms .. 38.25 ms)
variance introduced by outliers: 8% (slightly inflated)

benchmarking bench/bash -ci "(cd /usr/include/boost; hlgrep ARGS)"
analysing with 1000 resamples
bootstrapping with 5 of 6 samples (83%)
time                 2.129 s    (2.004 s .. 2.287 s)
                     0.998 R²   (0.992 R² .. 1.000 R²)
mean                 2.197 s    (2.141 s .. 2.249 s)
std dev              68.12 ms   (47.76 ms .. 82.33 ms)
variance introduced by outliers: 14% (moderately inflated)

benchmarking bench/bash -ci "(cd /usr/include/boost; ack --nofilter ARGS)"
analysing with 1000 resamples
bootstrapping with 5 of 6 samples (83%)
time                 2.250 s    (2.211 s .. 2.360 s)
                     0.999 R²   (0.995 R² .. 1.000 R²)
mean                 2.239 s    (2.219 s .. 2.279 s)
std dev              32.61 ms   (5.023 ms .. 43.91 ms)
found 1 outliers among 5 samples (20.0%)
  1 (20.0%) high mild
variance introduced by outliers: 14% (moderately inflated)

benchmarking bench/bash -ci "(cd ~/devel/cexmc; cgr parse)"
analysing with 1000 resamples
bootstrapping with 36 of 37 samples (97%)
time                 77.04 ms   (76.21 ms .. 78.01 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 76.23 ms   (75.70 ms .. 76.84 ms)
std dev              1.794 ms   (1.429 ms .. 2.352 ms)
found 2 outliers among 36 samples (5.6%)
  1 (2.8%) low mild
  1 (2.8%) high mild
variance introduced by outliers: 8% (slightly inflated)

benchmarking bench/bash -ci "(cd ~/devel/cexmc; hlgrep parse)"
analysing with 1000 resamples
bootstrapping with 33 of 34 samples (97%)
time                 94.47 ms   (93.40 ms .. 95.40 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 93.74 ms   (93.27 ms .. 94.17 ms)
std dev              1.325 ms   (1.054 ms .. 1.740 ms)
variance introduced by outliers: 3% (slightly inflated)

benchmarking bench/bash -ci "(cd ~/devel/cexmc; ack --nofilter parse)"
analysing with 1000 resamples
bootstrapping with 29 of 30 samples (96%)
time                 121.5 ms   (121.0 ms .. 122.0 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 121.6 ms   (121.1 ms .. 122.2 ms)
std dev              1.449 ms   (1.174 ms .. 1.830 ms)
variance introduced by outliers: 3% (slightly inflated)

benchmarking bench/bash -ci "(cd ~/devel/cexmc; cgrep -r parse)"
analysing with 1000 resamples
bootstrapping with 38 of 39 samples (97%)
time                 68.35 ms   (66.80 ms .. 70.55 ms)
                     0.996 R²   (0.994 R² .. 0.999 R²)
mean                 68.03 ms   (67.52 ms .. 68.83 ms)
std dev              2.001 ms   (1.543 ms .. 2.696 ms)
found 5 outliers among 38 samples (13.2%)
  4 (10.5%) high mild
  1 (2.6%) high severe
variance introduced by outliers: 12% (moderately inflated)

benchmarking bench/bash -ci "(cd ~/devel/cexmc; hl -r parse)"
analysing with 1000 resamples
bootstrapping with 34 of 35 samples (97%)
time                 87.98 ms   (87.55 ms .. 88.39 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 88.04 ms   (87.77 ms .. 88.32 ms)
std dev              836.7 μs   (676.7 μs .. 1.051 ms)
variance introduced by outliers: 3% (slightly inflated)

benchmarking bench/bash -ci "(cd ~/devel/cexmc; ack --nofilter --noenv parse)"
analysing with 1000 resamples
bootstrapping with 29 of 30 samples (96%)
time                 120.8 ms   (119.5 ms .. 122.5 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 119.7 ms   (119.3 ms .. 120.3 ms)
std dev              1.456 ms   (1.006 ms .. 2.055 ms)
found 3 outliers among 29 samples (10.3%)
  3 (10.3%) high mild
variance introduced by outliers: 3% (slightly inflated)

Графический отчет здесь. Выводы следующие: cgrep быстрее всех, особенно при большом объеме входных данных (в директории /usr/include/boost) — 0.668 против 2.20 и 2.24 сек у hlgrep и ack. При небольших объемах данных (в директории cexmc) cgrep по-прежнему лидирует, хоть и с небольшим отрывом (0.076 сек), hlgrep значительно опережает ack (0.094 против 0.122 сек) за счет стартовой скорости. Чистые варианты cgrep, hl и ack в директории cexmc незначительно быстрее шелл-функций (0.068 против 0.076 сек в случае cgrep, 0.088 против 0.094 сек в случае hl и 0.120 против 0.122 сек в случае ack) — это говорит о том, что конвейеры, состоящие из программ sed, column и hl, из которых собраны эти функции, достаточно быстры.