Dlaczego "grep --ignore-case" 50 razy wolniej?

Question

Byłem bardzo zaskoczony, gdy dodałem opcję do grep, która może spowolnić wyszukiwanie o 50x razy. Przetestowałem to na dwóch różnych maszynach z tym samym wynikiem. Jestem ciekawy, jak znaleźć wytłumaczenie ogromnej różnicy w wydajności.

Chciałbym również zobaczyć alternatywną komendę grep dla wyszukiwań niewrażliwych na wielkość liter. Nie potrzebuję wyrażeń regularnych, tylko poprawiono wyszukiwanie ciągów znaków. Pierwszy plik testowy będzie 50   MB plik tekstowy z niektórych danych manekina, można użyć następującego kodu, aby go wygenerować:

Tworzenie test.txt

yes all work and no play makes Jack a dull boy | head -c 50M > test.txt 
echo "Jack is no fun" >> test.txt 
echo "Jack is no Fun" >> test.txt 

Demonstracja

Poniżej znajduje się pokaz powolności. Po dodaniu opcji --ignore-case polecenie staje się 57 razy wolniejsze.

$ time grep fun test.txt 
all work and no plJack is no fun 
real 0m0.061s 

$ time grep --ignore-case fun test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m3.498s 

możliwych wyjaśnień

googlowania wokół znalazłem dyskusję na grep jest powolny w locale UTF-8. Przeprowadziłem następujący test i przyspieszyłem. Domyślnym ustawieniem narodowym na moim komputerze jest en_US.UTF-8, więc ustawienie go na POSIX wydaje się, że dokonało rozruchu wydajności, ale teraz oczywiście nie mogę poprawnie przeszukiwać tekstu Unicode, co jest niepożądane. Jest także nadal 2,5 razy wolniejszy.

$ time LANG=POSIX grep --ignore-case fun test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m0.142s 

Alternatywy

Mogliśmy użyć Perl zamiast tego jest szybsze, ale nadal 5,5 razy szybciej niż wrażliwej sprawy grep. A powyższy POSIX grep jest około dwa razy szybszy.

$ time perl -ne '/fun/i && print' test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m0.388s 

Chciałbym więc znaleźć szybką poprawną alternatywę i wyjaśnienie, jeśli ktoś ją ma.

AKTUALIZACJA - CentOS

dwie maszyny, które testowano jak powyżej były Ubuntu jeden 11.04 (Natty narwala inni) 12,04 (dokładne Pangolin). Uruchomienie tych samych testów na komputerze CentOS 5.3 daje następujące interesujące wyniki. Wyniki osiągnięte w obu przypadkach są niemal identyczne. Teraz CentOS 5.3 został wydany w styczniu 2009 roku i działa pod kontrolą grep 2.5.1, podczas gdy Ubuntu 12.04 uruchamia grep 2.10. Mogą więc wystąpić zmiany w nowej wersji i różnice w obu dystrybucjach.

$ time grep fun test.txt 
Jack is no fun 
real 0m0.026s 

$ time grep --ignore-case fun test.txt 
Jack is no fun 
Jack is no Fun 
real 0m0.027s 

Answer 1

myślę, że ten raport błędów pomaga w zrozumieniu, dlaczego to jest powolne:

bug report grep, slow on ignore-case

Answer 2

Aby wykonać wyszukiwanie bez uwzględniania wielkości liter, grep musi najpierw przekonwertować całą swoją 50   MB plik do jednego sprawa lub inne. To zajmie trochę czasu. Nie tylko to, ale są też kopie pamięci ...

W twoim przypadku testowym najpierw generujesz plik.Oznacza to, że będzie to buforowana pamięć. Pierwsze uruchomienie grepa ma tylko do mmap stron z pamięci podręcznej; nie musi nawet uzyskać dostępu do dysku.

Rozróżnianie wielkości liter bezczynności robi to samo, ale potem próbuje zmodyfikować te dane. Oznacza to, że jądro weźmie wyjątek dla każdej zmodyfikowanej strony 4   kB i będzie musiało skopiować całe 50   MB do nowej pamięci, po jednej stronie na raz.

Zasadniczo oczekiwałbym, że będzie wolniejszy niż. Może nie 57 razy wolniej, ale zdecydowanie wolniej.

Answer 3

To powolne działanie z powodu grep (w locale UTF-8) stale otwiera pliki "/ usr/lib/locale/locale-archive" i "/usr/lib/gconv/gconv-modules.cache".

Można to wyświetlić za pomocą narzędzia strace. Oba pliki pochodzą z glibc.

Answer 4

Powodem jest to, że musi wykonać porównanie z aktualnym językiem w Unicode, a sądząc po odpowiedzi Marata, nie jest to zbyt skuteczne.

To pokazuje, jak wiele szybciej to jest, kiedy Unicode nie jest brane pod uwagę:

$ time LC_CTYPE=C grep -i fun test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m0.192s 

Oczywiście, ta alternatywa nie będzie działać ze znaków w innych językach, takich jak N/N, O/O, Ð/ð, Æ/æ i tak dalej.

Inną alternatywą jest modyfikowanie regex tak, że mecze z case niewrażliwości:

$ time grep '[Ff][Uu][Nn]' test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m0.193s 

to rozsądnie szybko, ale oczywiście jest to ból przekonwertować każdy znak w klasie, a to nie jest łatwe do przekonwertuj go na alias lub skrypt sh, w przeciwieństwie do powyższego.

Dla porównania, w moim systemie:

$ time grep fun test.txt 
all work and no plJack is no fun 
real 0m0.085s 

$ time grep -i fun test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m3.810s