Grep -E, Sed -E - niska wydajność przy użyciu „[x] {1,9999}”, ale dlaczego?

9

Gdy greplub sedsą używane z opcją, --extended-regexpa wzorzec {1,9999}jest częścią używanego wyrażenia regularnego, wydajność tych poleceń staje się niska. Aby być bardziej zrozumiałym, poniżej zastosowano kilka testów. [1] [2]

  • Względna wydajność grep -E, egrepi sed -Ejest prawie równa, więc tylko testy, które zostały wykonane z grep -Esą świadczone.

Test 1

$ time grep -E '[0-9]{1,99}' < /dev/null

real    0m0.002s

Test 2

$ time grep -E '[0-9]{1,9999}' < /dev/null

> real    0m0.494s

Test 3

$ grep -E '[0123456789] {1,9999}' </ dev / null

> prawdziwe 21m43.947s

Test 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

Jaki jest powód tak znaczącej różnicy w wydajności?

command-line grep regex pa4080
źródło
3
To ciekawe spostrzeżenie - domyślam się, że trzeba by głęboko zagłębić się w wewnętrzne elementy grepa, aby dowiedzieć się, jak buduje parsowane drzewo (byłoby również interesujące porównać [0-9]+)
steeldriver
3
Dane wejściowe nie mają znaczenia. Jak sugeruje @steeldriver, spowolnienie poprzedza dopasowanie. Prostsza test jest time grep -E '[0-9]{1,99}' </dev/nullkontra time grep -E '[0-9]{1,9999}' </dev/null. Nawet bez danych wejściowych drugie polecenie jest powolne (16.04). Zgodnie z oczekiwaniami, z pominięciem -Ei ucieczki {i }zachowuje się tak samo i zastępując -Ez -Pnie wolno (PCRE jest inny silnik). Najciekawsze jest to, jak wiele szybciej [0-9] jest niż ., xa nawet [0123456789]. Z żadnym z tych i {1,9999}, grepzużywa ogromną ilość pamięci RAM; Nie odważyłem się, aby działał dłużej niż ~ 10 minut.
Eliah Kagan
3
@ αғsнιη Nie, { }są ' 'cytowane ; pocisk przekazuje je w niezmienionej postaci grep. W każdym razie {1,9999}byłoby to bardzo szybkie i proste rozszerzenie nawiasów klamrowych . Powłoka po prostu ją rozszerzy 1 9999.
Eliah Kagan
4
@ αғsнιη Nie wiem dokładnie, co masz na myśli, ale zdecydowanie nie ma to nic wspólnego z powłoką. Podczas długotrwałego polecenia użyłem psi topdo sprawdzenia, czy grepprzekazano oczekiwane argumenty i czy nie bashzużywa dużo pamięci RAM i procesora. Oczekuję grepi sedużywam funkcji regex POSIX zaimplementowanych w libc do dopasowywania BRE / ERE; Nie powinienem tak naprawdę mówić o grepprojektowaniu, chyba że grepprogramiści postanowili korzystać z tej biblioteki.
Eliah Kagan
3
Sugeruję, aby zastąpić testy time grep ... < /dev/null, aby ludzie nie połączyli rzeczywistego problemu z danymi, które zostały dostarczone, grepi innymi istotami obcymi.
mur

Odpowiedzi:

10

Zauważ, że to nie dopasowanie zajmuje dużo czasu, ale budowa RE. Przekonasz się, że zużywa również sporo pamięci RAM:

$ 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

Liczba przydziałów wydaje się w przybliżeniu proporcjonalna do liczby iteracji, ale przydzielona pamięć wydaje się rosnąć wykładniczo.

To zależy od sposobu implementacji wyrażeń regularnych GNU. Jeśli skompilować GNU grepz CPPFLAGS=-DDEBUG ./configure && makei uruchomić te polecenia, zobaczysz gwałtowny efekt w działaniu. Głębsze niż to oznaczałoby przejrzenie wielu teorii na temat DFA i zanurzenie się w implementacji regexp gnulib.

Tutaj możesz zamiast tego użyć PCRE, które nie wydają się mieć tego samego problemu: grep -Po '[0-9]{1,65535}'(maksimum, chociaż zawsze możesz robić rzeczy takie jak [0-9](?:[0-9]{0,10000}){100}dla 1 do 1 000 0001 powtórzeń) nie zajmuje więcej czasu ani pamięci niż grep -Po '[0-9]{1,2}'.

Stéphane Chazelas
źródło
Czy jest jakiś sposób na obejście tego?
Sergiy Kolodyazhnyy
3
@SergiyKolodyazhnyy, możesz użyć, grep -Po '[0-9]{1,9999}co nie wydaje się mieć problemu.
Stéphane Chazelas
1
To nie tylko w sed -Elub grep -E, ale w awkrównież posiada tę niską wydajność (około ostatniego polecenia awk). może awktakże nie możesz używać PCRE?
αғsнιη