Grep -E, Sed -E - низкая производительность при использовании '[x] {1,9999}', но почему?
Когда grep или sed используются с опцией - extended-regexp и шаблоном ] {1,9999} является частью используемого регулярного выражения, производительность этих команд снижается. Для большей ясности ниже применяются несколько тестов. [1] [2]
- Относительная производительность
grep -E,egrepиsed -Eпочти одинакова, поэтому только тест, выполненный с помощьюgrep -E.
Тест 1
$ time grep -E '[0-9]{1,99}' < /dev/null
real 0m0.002s
Тест 2
$ time grep -E '[0-9]{1,9999}' < /dev/null
> real 0m0.494s
Тест 3
$ time grep -E '[0123456789]{1,9999}' < /dev/null
> real 21m43.947s
Тест 4
$ time grep -E '[0123456789]+' < /dev/null
$ time grep -E '[0123456789]*' < /dev/null
$ time grep -E '[0123456789]{1,}' < /dev/null
$ time grep -P '[0123456789]{1,9999}' < /dev/null
real 0m0.002s
В чем причина такой значительной разницы в производительности?
1 ответ
Обратите внимание, что это не согласование требует времени, а создание RE. Вы обнаружите, что он также использует довольно много оперативной памяти:
$ valgrind grep -Eo '[0-9]{1,9999}' < /dev/null
==6518== HEAP SUMMARY:
==6518== in use at exit: 1,603,530,656 bytes in 60,013 blocks
==6518== total heap usage: 123,613 allocs, 63,600 frees, 1,612,381,621 bytes allocated
$ valgrind grep -Eo '[0-9]{1,99}' < /dev/null
==6578== in use at exit: 242,028 bytes in 613 blocks
==6578== total heap usage: 1,459 allocs, 846 frees, 362,387 bytes allocated
$ valgrind grep -Eo '[0-9]{1,999}' < /dev/null
==6594== HEAP SUMMARY:
==6594== in use at exit: 16,429,496 bytes in 6,013 blocks
==6594== total heap usage: 12,586 allocs, 6,573 frees, 17,378,572 bytes allocated
Количество выделений кажется примерно пропорциональным количеству итераций, но выделенная память, кажется, растет в геометрической прогрессии.
Это зависит от того, как реализованы регулярные выражения GNU. Если вы скомпилируете GNU grep с помощью CPPFLAGS=-DDEBUG ./configure && make и выполните эти команды, вы увидите экспоненциальный эффект в действии. Если вы углубитесь в это, это будет означать, что вам придется пройти через множество теорий по DFA и погрузиться в реализацию gnulib regexp.
Здесь вы можете использовать PCRE, которые, кажется, не имеют такой же проблемы: grep -Po '[0-9]{1,65535}' (максимум, хотя вы всегда можете сделать что-то вроде [0-9](?:[0-9]{0,10000}){100} для 1-1000,001 повторений), не занимает больше времени ни памяти, чем grep -Po '[0-9]{1,2}'.