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

9

Когда 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

> настоящий 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

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

command-line grep regex pa4080
источник
3
Это интересное наблюдение - я полагаю, вам нужно было бы углубиться во внутренности grep, чтобы точно выяснить, как именно он строит дерево разбора (было бы также интересно сравнить [0-9]+)
steeldriver
3
Вход не имеет значения. Как предполагает @steeldriver, замедление предшествует сопоставлению. Более простой тест - time grep -E '[0-9]{1,99}' </dev/nullпротив time grep -E '[0-9]{1,9999}' </dev/null. Даже без ввода вторая команда работает медленно (16.04). Как и следовало ожидать, опуская -Eи побег {и }ведешь себя так же и замену -Eс -Pне медленно (PCRE является другим двигателем). Самое интересное, насколько быстрее [0-9] это чем ., xи даже [0123456789]. С любым из них и {1,9999}, grepпотребляет огромное количество оперативной памяти; Я не осмелился позволить этому бежать больше чем ~ 10 минут.
Элия ​​Каган
3
@ αғsнιη Нет, { }они ' 'указаны ; оболочка передает их без изменений grep. Во всяком случае, {1,9999}было бы очень быстрое и простое расширение скобки . Оболочка просто расширит его до 1 9999.
Элия ​​Каган
4
@ αғsнιη Я не совсем понимаю, что ты имеешь в виду, но это определенно не имеет ничего общего с оболочкой. Во время длительной команды я использовал psи topдля проверки grepбыл передан ожидаемый аргумент и то, что он не bashпотребляет много оперативной памяти и процессора. Я ожидаю, grepи sedоба используют функции регулярного выражения POSIX, реализованные в libc для соответствия BRE / ERE; Я не должен был говорить grepконкретно о дизайне, за исключением того, что grepразработчики решили использовать эту библиотеку.
Элия ​​Каган
3
Я предлагаю вам заменить тесты time grep ... < /dev/null, чтобы люди не связывали реальную проблему с данными, поступающими в систему, grepи другими посторонними вещами.
Муру

Ответы:

10

Обратите внимание, что это не согласование, которое требует времени, но создание 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}'.

Стефан Шазелас
источник
Есть ли способ обойти это?
Сергей Колодяжный
3
@SergiyKolodyazhnyy, вы можете использовать, grep -Po '[0-9]{1,9999}который, кажется, не проблема.
Стефан
1
Это не только sed -Eили grep -E, но в awkтоже имеет эту низкую производительность (о последней команде AWK). Может быть, awkтакже не может использовать PCRE?
αғsнιη