Архив от 3 сентября, 2010

Mike Haertel, автор GNU grep, написал в рассылку FreeBSD отличное письмо по поводу производительности grep-а.

Суть в том, что grep использует модифицированный алгоритм Boyer-Moore для поиска подстроки и ему не приходится проверять каждый байт.

Там же предлагалась идея использовать mmap для увеличения производительности, чтобы ядру не читать read-ом каждый байт, а передать контроль за этим в юзерспейс — самому grep-у.

Если вдуматься, смысл этой оптимизации не очень большой. Все равно с диска считывается минимум 4 килобайта (размер физического сектора HDD), и вряд-ли Boyer-Moore сделает прыжок больше, чем на 4K.

Вторая причина в том, что каждая считанная страница памяти будет генерировать page fault. Это может быть даже дороже, чем системный вызов read().

Собственно, именно так и посчитали разработчики grep-а.

Еще одна отличная оптимизация — grep не разбивает входящий файл на строки заранее. Он сначала находит вхождение, а потом ищет начало и конец строки. Если grep-у указать ключ -n (включить счетчик строк), то ему будет необходимо из распознавать заранее, что сильно уменьшит его производительность.

$ time grep groovy tmpfs/words > /dev/null

real 0m0.927s
user 0m0.600s
sys 0m0.311s
$ time grep -n groovy tmpfs/words > /dev/null

real 0m1.924s
user 0m1.606s
sys 0m0.307s
$