Warum ist wc so langsam?

17

Warum ist das Dienstprogramm wc so langsam?

Wenn ich es auf einer großen Datei laufen lasse, dauert es ungefähr 20 mal länger als md5sum:

MyDesktop:/tmp$ dd if=/dev/zero bs=1024k count=1024 of=/tmp/bigfile
1024+0 records in
1024+0 records out
1073741824 bytes (1.1 GB) copied, 0.687094 s, 1.6 GB/s

MyDesktop:/tmp$ time wc /tmp/bigfile 
         0          0 1073741824 /tmp/bigfile

real    0m45.969s
user    0m45.424s
sys     0m0.424s

MyDesktop:/tmp$ time md5sum /tmp/bigfile 
cd573cfaace07e7949bc0c46028904ff  /tmp/bigfile

real    0m2.520s
user    0m2.196s
sys     0m0.316s

Es ist nicht nur eine seltsame Randbedingung, da die Datei mit Nullen gefüllt ist. Ich sehe den gleichen Leistungsunterschied, auch wenn die Datei mit zufälligen Daten gefüllt ist oder eine Textdatei ist.

(Dies ist auf Ubuntu 13.04, 64 Bit)

Johnny
quelle
Hinweis für diejenigen, die sich nur um die Zeilenanzahl kümmern: wc -l <Dateiname> ist bei sehr großen Dateien viel schneller.
EL

Antworten:

27

Also ging ich zur Quelle und es sieht so aus, als ob die Langsamkeit im Umgang mit Doppelbyte-Zeichen liegt. Grundsätzlich muss für jedes eingelesene Zeichen ein Aufruf erfolgen mbrtowc(), um zu versuchen, es in ein breites Zeichen umzuwandeln. Dieses breite Zeichen wird dann geprüft, um festzustellen, ob es sich um ein Worttrennzeichen, ein Zeilentrennzeichen usw. handelt.

Tatsächlich kann ich, wenn ich meine Gebietsschemavariable LANGvon der Standardvariable ändere en_US.UTF-8(UTF-8 ist ein Multibyte-Zeichensatz) und auf " C" (einfacher Einzelbyte-Zeichensatz) setze, wcEinzelbyte-Optimierungen verwenden, was dies erheblich beschleunigt. dauert nur etwa ein Viertel so lange wie zuvor.

Außerdem muss nur jedes Zeichen überprüft werden, ob es Wörter ( -w), Zeilenlängen ( -L) oder Zeichen ( -m) zählt. Wenn es nur Byte- und / oder Zeilenzählungen durchführt, kann es die Verarbeitung breiter Zeichen überspringen und läuft dann extrem schnell - schneller als md5sum.

Ich lief es durch gprof, und die Funktionen, die die Multibyte - Zeichen (werden verwendet , um handhaben mymbsinit(), mymbrtowc(), myiswprint()usw.) nehmen bis zu 30% der Ausführungszeit allein, und der Code , dass die Schritte durch den Puffer ist viel komplexer , weil es zu Behandeln Sie Schritte mit variabler Größe durch den Puffer für Zeichen mit variabler Größe und füllen Sie alle unvollständigen Zeichen, die sich über den Puffer erstrecken, wieder an den Anfang des Puffers, damit sie beim nächsten Mal verarbeitet werden können.

Nachdem ich nun weiß, wonach ich suchen muss, habe ich einige Posts gefunden, in denen die Langsamkeit von utf-8 mit einigen Dienstprogrammen erwähnt wird:

/programming/13913014/grepping-a-huge-file-80gb-any-way-to-speed-it-up http://dtrace.org/blogs/brendan/2011/12/08 / 2000x-performance-win /

Johnny
quelle
2
Oh, ich habe gerade gemerkt, dass Sie OP sind. : p
Ivan Chau
2
Dies ist zwar die am häufigsten gewählte Antwort, aber irrelevant. md5sumErlaubt Ihnen niemals das Zählen der Wortnummer und wcberechnet nicht den MD5-Hash der Datei! Es ist, als würde man fragen, warum mein Auto im Vergleich zu meiner Schreibmaschine beim Schreiben von Text so langsam ist.
user49468
5
@ user49468: Es ist vernünftig anzunehmen, dass beide E / A-gebunden sind, da beide jedes Byte der Eingabedatei lesen müssen. Diese Antwort beweist, dass wcbei der Verarbeitung von Mehrbyte-Zeichen die CPU tatsächlich gebunden ist.
MSalters
2
@ user49468: wc und md5sum können verschiedene Dinge tun, aber beide lesen eine Datei und führen eine relativ einfache Berechnung durch, man berechnet eine Prüfsumme, man zählt Bytes, Worttrennzeichen und Zeilenumbrüche. Nun, ich fand es einfach, hatte aber die zusätzliche Komplexität von Multibyte-Zeichensätzen nicht berücksichtigt. Es ist eher so, als würde man fragen: "Warum fährt mein Auto 20 Mal schneller als mein Minivan?" Sie würden einen Unterschied zwischen den beiden erwarten, aber keinen 20-fachen Unterschied.
Johnny
1
@ Johnny Ihr Auto / Minivan Vergleich fehlt der Aspekt, dass beide entwickelt wurden, um Sie in den Laden zu transportieren. Es ist also ein Geschwindigkeitsvergleich vorhanden. Ein Vergleich Ihres Autos mit dem Streifenlackierfahrzeug ist besser geeignet. Nur weil beide die Straße benutzen, ist ihre Geschwindigkeit nicht relevant, da der Streifenmaler nicht zum Einkaufen geeignet ist und umgekehrt.
user49468
1

Nur eine Vermutung, aber Sie vergleichen Äpfel mit Orangen in Bezug auf das, was sie wctun, und das, was sie md5sumtun.

md5sums aufgabe

Beim md5sumVerarbeiten einer Datei wird die Datei einfach als Stream geöffnet und der Stream über die MD5-Prüfsummenfunktion ausgeführt, die nur sehr wenig Speicher benötigt. Es ist im Wesentlichen CPU & Disk I / O gebunden.

wc's aufgabe

Wenn wces ausgeführt wird, ist es viel mehr, als nur die Datei zeichenweise zu analysieren. Es muss die Struktur der Datei analysieren und Zeilen für Zeilen bestimmen, wo sich die Grenzen zwischen den Zeichen befinden und ob es sich um eine Wortgrenze handelt oder nicht.

Beispiel

Stellen Sie sich die folgenden Zeichenfolgen vor und wie sich jeder Algorithmus durch sie bewegen müsste, wenn sie sie analysieren:

“Hello! Greg”
“Hello!Greg”
“Hello\nGreg”
“A.D.D.”
“Wow, how great!”
“wow     \n\n\n    great”
“it was a man-eating shark.”

In MD5 werden diese Zeichenfolgen nur zeichenweise durchlaufen. Denn wces muss entscheiden, was eine Wort- und Liniengrenze ist, und die Anzahl der Vorkommen verfolgen, die es sieht.

Zusätzliche WC-Diskussionen

Ich habe diese Codierungsherausforderung aus dem Jahr 2006 gefunden , in der die Implementierung wcin .NET erläutert wird . Die Schwierigkeiten liegen auf der Hand, wenn Sie sich einen Teil des Pseudocodes ansehen. Dies könnte also hilfreich sein, um zu verstehen, warum dieser wcVorgang so viel langsamer ist als andere Vorgänge.

slm
quelle
1
Sie beschreiben etwas anderes als den standardmäßigen Unix- Befehl wc (zumindest nicht den, der mit Ubuntu geliefert wird). Das wc zählt keine eindeutigen Wörter, nur Wörter, so "Hallo Hallo Welt" ist 3 Wörter, nicht 2.
Johnny
Basierend auf dieser Theorie klingt es, als würde eine einfachere Aufgabe, wie das Zählen von Linien, schneller gehen. Ändert die Änderung von 'wc' zur Angabe einer Zeilenzahl die Ergebnisse erheblich? "wc-l"
Joshua Miller
@ Johnny - Ich habe nie gesagt, dass es einzigartige Worte zählt, die du gesagt hast. wczählt mehrere Dinge, wie es die Datei analysiert. Beim Parsen der Datei werden die Anzahl der Wörter, Zeilen und Bytes gezählt. Lesen Sie die Manpage!
slm
@JoshuaMiller - Unklar, ob wcdas Zählen von Zeilen das interne Parsen einschränkt, sodass nur diese Dinge gezählt werden oder nur die Zeilenergebnisse gemeldet werden , obwohl immer noch alles gezählt wird.
slm
@slm Du hast gesagt, es zählen einzigartige Wörter, dein Beispiel sagt „Hallo! Greg ”ergibt Hallo 1, Greg 1 , dh zählt für jedes Wort. Und das .Net-Projekt, mit dem Sie verknüpft haben, sagt: "Eine der Hauptaufgaben besteht darin, einen Datensatz zu durchsuchen und die Anzahl der Wiederholungen eines bestimmten Wortes zu zählen. Wenn Sie beispielsweise den Satz" Hallo, ja, hallo "eingeben, wird Ihnen dies mitgeteilt das Wort "Hallo" wurde zweimal verwendet und das Wort "Ja" wurde einmal verwendet. " Während in Wirklichkeit das Ergebnis von Echo "Hallo, ja hallo" | wc --words , ist "3", nicht "Hallo: 2, Ja: 1"
Johnny