Warum ist "grep --ignore-case" 50 mal langsamer?

Question

Ich war sehr überrascht zu sehen, dass, wenn Sie die --ignore-case Option zu grep hinzufügen, dass es die Suche 50x mal verlangsamen kann. Ich habe das auf zwei verschiedenen Maschinen mit dem gleichen Ergebnis getestet. Ich bin gespannt auf eine Erklärung für den enormen Leistungsunterschied.

Ich möchte auch einen alternativen Befehl zu grep für Groß- und Kleinschreibung suchen. Ich brauche keine regulären Ausdrücke, nur die Suche nach festen Strings. Zunächst wird die Testdatei wird eine 50   MB Textdatei mit einigen Dummy-Daten sein, können Sie den folgenden Code verwenden, um es zu erzeugen:

TEST.TXT erstellen

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 

Demonstration

Unten ist eine Demonstration der Langsamkeit. Durch Hinzufügen der Option --ignore-case wird der Befehl 57x-mal langsamer.

$ 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 

Mögliche Erklärungen

googeln um, fand ich eine Diskussion zu grep langsam in dem UTF-8-Gebietsschema ist. Also habe ich den folgenden Test durchgeführt und es hat sich beschleunigt. Das Standardgebietsschema auf meinem Computer ist en_US.UTF-8, also scheint es, dass ich einen Performance-Boot gemacht habe, wenn ich ihn auf POSIX setze, aber jetzt kann ich natürlich nicht korrekt nach Unicode-Text suchen, was unerwünscht ist. Es ist auch immer noch 2,5 mal langsamer.

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

Alternativen

Wir Perl verwenden könnte stattdessen ist es schneller, aber immer noch 5,5-mal schneller als die Groß- und Kleinschreibung grep. Und der POSIX Grep oben ist etwa doppelt so schnell.

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

So würde ich gerne eine schnelle richtige Alternative und eine Erklärung finden, wenn jemand eine hat.

UPDATE - CentOS

den beiden Maschinen, die über beide getestet wurden, waren die unter Ubuntu einer 11,04 (Natty Narwhal), die andere 12.04 (Precise Pangolin). Das Ausführen der gleichen Tests auf einer CentOS 5.3-Maschine führt zu den folgenden interessanten Ergebnissen. Die Leistungsergebnisse der beiden Fälle sind nahezu identisch. Jetzt wurde CentOS 5.3 im Januar 2009 veröffentlicht und läuft grep 2.5.1 während Ubuntu 12.04 grep 2.10 läuft. Es könnte also Änderungen in der neuen Version und Unterschiede in den beiden Distributionen geben.

$ 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

Ich denke, der Bug-Report hilft zu verstehen, warum es langsam ist:

bug report grep, slow on ignore-case

Answer 2

eine Groß- und Kleinschreibung Suche zu tun, hat grep zuerst Ihre gesamte 50   MB-Datei umzuwandeln Fall oder der andere. Das wird Zeit brauchen. Nicht nur das, aber es gibt Speicherkopien ...

In Ihrem Testfall erstellen Sie zuerst die Datei.Dies bedeutet, dass es zwischengespeichert wird. Der erste Grep-Lauf hat nur mmap die zwischengespeicherten Seiten; Es muss nicht einmal auf die Festplatte zugreifen.

Die Groß-und Kleinschreibung Grep nicht die gleiche, aber dann versucht, diese Daten zu ändern. Dies bedeutet, dass der Kernel für jede modifizierte 4   kB-Seite eine Ausnahme macht und die gesamte 50   MB Seite für Seite in neuen Speicher kopieren muss.

Grundsätzlich würde ich erwarten dies langsamer zu sein. Vielleicht nicht 57x langsamer, aber definitiv langsamer.

Answer 3

Diese Langsamkeit ist auf Grep zurückzuführen (auf einem UTF-8-Gebietsschema) greift ständig auf Dateien "/ usr/lib/locale/locale-archive" und "/usr/lib/gconv/gconv-modules.cache" zu.

Es kann mit dem strace Dienstprogramm angezeigt werden. Beide Dateien stammen von glibc.

Answer 4

Der Grund ist, dass es einen Unicode-fähigen Vergleich für das aktuelle Gebietsschema machen muss, und nach Marats Antwort zu urteilen, ist es nicht sehr effizient dabei.

Dies zeigt, wie viel schneller es ist, wenn Unicode nicht berücksichtigt wird:

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

Natürlich ist diese Alternative wird in anderen Sprachen mit Zeichen arbeiten wie n/N, Ø/ø nicht, Ð/ð, Æ/æ und so weiter.

Eine weitere Alternative ist die Regex so zu modifizieren, dass es mit Groß- und Kleinschreibung übereinstimmt:

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

Dies ist recht schnell, aber natürlich ist es ein Schmerz jedes Zeichen in eine Klasse zu konvertieren, und es ist nicht leicht zu wandeln Sie es in einen Alias ​​oder ein sh Skript um, im Gegensatz zu dem oben genannten.

Zum Vergleich: in meinem System:

$ 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