Grep -E, Sed -E - низкая производительность при использовании '[x]{1,9999}', но почему?

Question

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}' > настоящий 21м43.947с

Тест 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

В чем причина этого существенного различия производительности?

9

command-line grep regex

Источник

pa4080 29 сен '17 в 15:29

1 ответ

Решение

Другие вопросы по тегам command-line grep regex

Stéphane Chazelas 29 сен '17 в 20:58 2017-09-29 20:58 · Accepted Answer · 2017-09-29 20:58

Обратите внимание, что это не согласование, которое требует времени, но создание 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 до 1 000 001 повторений) не занимает больше времени и памяти, чем grep -Po '[0-9]{1,2}',