Warum wird eine Datei zweimal schneller durchlaufen als in den Speicher eingelesen und zweimal berechnet?

26

Ich vergleiche folgendes

tail -n 1000000 stdout.log | grep -c '"success": true'
tail -n 1000000 stdout.log | grep -c '"success": false'

mit den folgenden

log=$(tail -n 1000000 stdout.log)
echo "$log" | grep -c '"success": true'
echo "$log" | grep -c '"success": false'

und überraschenderweise dauert die zweite fast dreimal länger als die erste. Es sollte schneller sein, nicht wahr?

phunehehe
quelle
Könnte es daran liegen, dass bei der zweiten Lösung der Dateiinhalt dreimal und im ersten Beispiel nur zweimal gelesen wird?
Laurent C.
4
Zumindest in dem zweiten Beispiel, Ihr $( command substitution )heißt nicht gestreamt. Der Rest geschieht gleichzeitig über Pipes, aber im zweiten Beispiel müssen Sie warten, bis der Vorgang log=abgeschlossen ist. Versuchen Sie es mit << HIER \ n $ {log = $ (Befehl)} \ nHIER - sehen Sie, was Sie bekommen.
mikeserv
Bei extrem großen Dateien, speicherbeschränkten Computern oder mehr Elementen, grepfür die möglicherweise eine Beschleunigung erforderlich ist, wird teedie Datei definitiv nur einmal gelesen. cat stdout.log | tee >/dev/null >(grep -c 'true'>true.cnt) >(grep -c 'false'>false.cnt); cat true.cnt; cat false.cnt
Matt
@LaurentC., Nein, im zweiten Beispiel wird es nur einmal gelesen. Es gibt nur einen Anruf zum Nachholen.
Psusi
Vergleichen Sie diese nun mit tail -n 10000 | fgrep -c '"success": true'und false.
Kojiro

Antworten:

11

Einerseits wird die erste Methode tailzweimal aufgerufen, sodass mehr Arbeit als die zweite Methode anfällt, die dies nur einmal ausführt. Auf der anderen Seite muss die zweite Methode die Daten in die Shell kopieren und dann wieder entfernen, sodass sie mehr Arbeit leisten muss als die erste Version, in taildie direkt weitergeleitet wird grep. Das erste Verfahren weist einen zusätzlichen Vorteil auf einer Multi-Prozessor - Maschine: grepmit parallel arbeiten tail, während die zweiten Methode ist streng serialisiert, zuerst tail, dann grep.

Es gibt also keinen offensichtlichen Grund, warum einer schneller sein sollte als der andere.

Wenn Sie sehen möchten, was los ist, schauen Sie sich an, welches System die Shell aufruft. Versuchen Sie es auch mit verschiedenen Schalen.

strace -t -f -o 1.strace sh -c '
  tail -n 1000000 stdout.log | grep "\"success\": true" | wc -l;
  tail -n 1000000 stdout.log | grep "\"success\": false" | wc -l'

strace -t -f -o 2-bash.strace bash -c '
  log=$(tail -n 1000000 stdout.log);
  echo "$log" | grep "\"success\": true" | wc -l;
  echo "$log" | grep "\"success\": true" | wc -l'

strace -t -f -o 2-zsh.strace zsh -c '
  log=$(tail -n 1000000 stdout.log);
  echo "$log" | grep "\"success\": true" | wc -l;
  echo "$log" | grep "\"success\": true" | wc -l'

Bei Methode 1 sind die Hauptphasen:

  1. tail liest und sucht seinen Ausgangspunkt zu finden.
  2. tailschreibt 4096-Byte-Chunks, die grepso schnell gelesen werden, wie sie produziert werden.
  3. Wiederholen Sie den vorherigen Schritt für die zweite Suchzeichenfolge.

Bei Methode 2 sind die Hauptphasen:

  1. tail liest und sucht seinen Ausgangspunkt zu finden.
  2. tail schreibt 4096-Byte-Chunks, die jeweils 128 Bytes lesen, und zsh liest jeweils 4096 Bytes.
  3. Bash oder zsh schreibt 4096-Byte-Chunks, die grepso schnell gelesen werden, wie sie produziert werden.
  4. Wiederholen Sie den vorherigen Schritt für die zweite Suchzeichenfolge.

Die 128-Byte-Chunks von Bash verlangsamen die Ausgabe der Befehlsersetzung erheblich. zsh kommt für mich genauso schnell raus wie Methode 1. Ihre Laufleistung kann je nach CPU-Typ und -Nummer, Scheduler-Konfiguration, Versionen der beteiligten Tools und Datengröße variieren.

Gilles 'SO - hör auf böse zu sein'
quelle
Ist die 4k-Zahl abhängig von der Seitengröße? Ich meine, sind schwanz und zsh beide nur mmaping syscalls? (Möglicherweise ist das eine falsche Terminologie, aber ich hoffe nicht ...) Was macht Bash anders?
mikeserv
Das ist genau richtig für Gilles! Mit zsh ist die zweite Methode auf meinem Rechner etwas schneller.
Phunehehe
Tolle Arbeit Gilles, tks.
X Tian
@mikeserv Ich habe nicht in der Quelle nachgesehen, wie diese Programme die Größe auswählen. Die wahrscheinlichsten Gründe für die Anzeige von 4096 sind eine integrierte Konstante oder der st_blksizeWert für eine Pipe, der auf diesem Computer bei 4096 liegt (und ich weiß nicht, ob dies an der MMU-Seitengröße liegt). Bashs 128 müsste eine eingebaute Konstante sein.
Gilles 'SO - hör auf böse zu sein'
@ Gilles, danke für die nachdenkliche Antwort. Ich war in letzter Zeit nur neugierig auf Seitengrößen.
mikeserv
26

Ich habe den folgenden Test durchgeführt und auf meinem System ist der resultierende Unterschied für das zweite Skript ungefähr 100-mal länger.

Meine Datei wird als Strace-Ausgabe bezeichnet bigfile

$ wc -l bigfile.log 
1617000 bigfile.log

Skripte

xtian@clafujiu:~/tmp$ cat p1.sh
tail -n 1000000 bigfile.log | grep '"success": true' | wc -l
tail -n 1000000 bigfile.log | grep '"success": false' | wc -l

xtian@clafujiu:~/tmp$ cat p2.sh
log=$(tail -n 1000000 bigfile.log)
echo "$log" | grep '"success": true' | wc -l
echo "$log" | grep '"success": true' | wc -l

Ich habe eigentlich keine Übereinstimmungen für das grep, also wird nichts bis zur letzten Pipe durchgeschrieben wc -l

Hier sind die Zeiten:

xtian@clafujiu:~/tmp$ time bash p1.sh
0
0

real    0m0.381s
user    0m0.248s
sys 0m0.280s
xtian@clafujiu:~/tmp$ time bash p2.sh
0
0

real    0m46.060s
user    0m43.903s
sys 0m2.176s

Also habe ich die beiden Skripte erneut über den Befehl strace ausgeführt

strace -cfo p1.strace bash p1.sh
strace -cfo p2.strace bash p2.sh

Hier sind die Ergebnisse aus den Spuren:

$ cat p1.strace 
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 97.24    0.508109       63514         8         2 waitpid
  1.61    0.008388           0     84569           read
  1.08    0.005659           0     42448           write
  0.06    0.000328           0     21233           _llseek
  0.00    0.000024           0       204       146 stat64
  0.00    0.000017           0       137           fstat64
  0.00    0.000000           0       283       149 open
  0.00    0.000000           0       180         8 close
...
  0.00    0.000000           0       162           mmap2
  0.00    0.000000           0        29           getuid32
  0.00    0.000000           0        29           getgid32
  0.00    0.000000           0        29           geteuid32
  0.00    0.000000           0        29           getegid32
  0.00    0.000000           0         3         1 fcntl64
  0.00    0.000000           0         7           set_thread_area
------ ----------- ----------- --------- --------- ----------------
100.00    0.522525                149618       332 total

Und p2.strace

$ cat p2.strace 
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 75.27    1.336886      133689        10         3 waitpid
 13.36    0.237266          11     21231           write
  4.65    0.082527        1115        74           brk
  2.48    0.044000        7333         6           execve
  2.31    0.040998        5857         7           clone
  1.91    0.033965           0    705681           read
  0.02    0.000376           0     10619           _llseek
  0.00    0.000000           0       248       132 open
...
  0.00    0.000000           0       141           mmap2
  0.00    0.000000           0       176       126 stat64
  0.00    0.000000           0       118           fstat64
  0.00    0.000000           0        25           getuid32
  0.00    0.000000           0        25           getgid32
  0.00    0.000000           0        25           geteuid32
  0.00    0.000000           0        25           getegid32
  0.00    0.000000           0         3         1 fcntl64
  0.00    0.000000           0         6           set_thread_area
------ ----------- ----------- --------- --------- ----------------
100.00    1.776018                738827       293 total

Analyse

Es überrascht nicht, dass in beiden Fällen der größte Teil der Zeit damit verbracht wird, auf den Abschluss eines Prozesses zu warten, aber p2 wartet 2,63-mal länger als p1, und wie andere bereits erwähnt haben, beginnen Sie spät in p2.sh.

Vergessen Sie also das waitpid, ignorieren Sie die %Spalte und sehen Sie sich die Sekunden-Spalte auf beiden Spuren an.

Größte Zeit p1 verbringt die meiste Zeit beim Lesen wahrscheinlich verständlicherweise, da es eine große zu lesende Datei gibt, aber p2 verbringt 28,82-mal mehr Zeit beim Lesen als p1. - basherwartet nicht, dass eine so große Datei in eine Variable eingelesen wird, und liest wahrscheinlich jeweils einen Puffer, teilt sich in Zeilen auf und holt sich dann eine andere.

Die Lesezahl p2 beträgt 705k gegenüber 84k für p1, wobei jeder Lesevorgang eine Kontextumschaltung in den Kernelraum und wieder zurück erfordert. Fast zehnmal so viele Lesevorgänge und Kontextwechsel.

Die Schreibzeit für p2 ist 41,93-mal länger als für p1

write count p1 schreibt mehr als p2, 42k vs 21k, jedoch sind sie viel schneller.

Wahrscheinlich wegen der echovon Zeilen in grepSchreibpuffern im Gegensatz zu Schwanz.

Außerdem verbringt p2 beim Schreiben mehr Zeit als beim Lesen, p1 ist umgekehrt!

Anderer Faktor Schauen Sie sich die Anzahl der brkSystemaufrufe an: p2 verbringt 2,42-mal mehr Zeit mit dem Brechen als beim Lesen! In p1 (es registriert nicht einmal). brkWenn das Programm seinen Adressraum erweitern muss, weil anfangs nicht genug zugewiesen wurde, liegt dies wahrscheinlich daran, dass Bash diese Datei in die Variable einlesen muss und nicht erwartet, dass sie so groß ist, und wie @scai erwähnt, wenn die Datei wird zu groß, auch das würde nicht funktionieren.

tailist wahrscheinlich ein recht effizienter Dateireader, da er genau dafür entwickelt wurde, die Datei zu speichern und nach Zeilenumbrüchen zu suchen, sodass der Kernel die Ein- / Ausgabe optimieren kann. Bash ist nicht so gut, sowohl beim Lesen als auch beim Schreiben.

p2 verbringt 44ms und 41ms in cloneund execves ist kein messbarer Betrag für p1. Vermutlich bash das Lesen und Erzeugen der Variablen aus dem Schwanz.

Schließlich führt die Gesamtsumme p1 ~ 150.000 Systemaufrufe gegenüber p2 740.000 (4,93-mal höher) aus.

Wenn Sie waitpid eliminieren, verbringt p1 0,014416 Sekunden mit der Ausführung von Systemaufrufen, p2 0,439132 Sekunden (30-mal länger).

Daher verbringt p2 die meiste Zeit im Benutzerbereich mit nichts anderem, als darauf zu warten, dass die Systemaufrufe abgeschlossen sind und der Kernel den Speicher neu organisiert.

Fazit

Ich würde niemals versuchen, mir Gedanken über das Codieren durch den Speicher zu machen, wenn ich ein Bash-Skript schreibe. Das bedeutet nicht, dass Sie nicht versuchen, effizient zu sein.

tailentwickelt, um zu tun, was es tut, ist es wahrscheinlich memory mapsdie Datei, so dass es effizient zu lesen ist und ermöglicht dem Kernel, die I / O zu optimieren.

Ein besserer Weg, um Ihr Problem zu optimieren, könnte darin bestehen, zuerst grepnach "Erfolg" zu suchen: "Zeilen" und dann nach "Wahr und Falsch" zu zählen. Außerdem grepgibt es eine Zähloption, mit der das Weiterleiten wc -ldes Schwanzes zu awkund Zählen von Wahr und Falsch umgangen wird fälscht gleichzeitig. p2 dauert nicht nur lange, sondern belastet auch das System, während der Speicher mit brks gemischt wird.

X Tian
quelle
2
TL; DR: malloc (); Wenn Sie $ log mitteilen könnten, wie groß es sein musste, und es schnell und ohne Neuzuweisungen in einem Vorgang schreiben könnten, wäre es wahrscheinlich genauso schnell.
Chris K
5

Eigentlich liest die erste Lösung die Datei auch in den Speicher! Dies wird als Caching bezeichnet und vom Betriebssystem automatisch durchgeführt.

Und wie von mikeserv bereits richtig erklärt, wird die erste Lösung ausgeführt, grep während die Datei gelesen wird, während die zweite Lösung sie ausführt, nachdem die Datei gelesen wurde tail.

Die erste Lösung ist also aufgrund verschiedener Optimierungen schneller. Das muss aber nicht immer wahr sein. Bei sehr großen Dateien, die das Betriebssystem nicht zwischenspeichern möchte, kann die zweite Lösung schneller werden. Beachten Sie jedoch, dass bei noch größeren Dateien, die nicht in Ihren Speicher passen, die zweite Lösung überhaupt nicht funktioniert.

scai
quelle
3

Ich denke, der Hauptunterschied ist ganz einfach, dass echoes langsam ist. Bedenken Sie:

$ time (tail -n 1000000 foo | grep 'true' | wc -l; 
        tail -n 1000000 foo | grep 'false' | wc -l;)
666666
333333

real    0m0.999s
user    0m1.056s
sys     0m0.136s

$ time (log=$(tail -n 1000000 foo); echo "$log" | grep 'true' | wc -l; 
                                    echo "$log" | grep 'false' | wc -l)
666666
333333

real    0m4.132s
user    0m3.876s
sys     0m0.468s

$ time (tail -n 1000000 foo > bb;  grep 'true' bb | wc -l; 
                                   grep 'false' bb | wc -l)
666666
333333

real    0m0.568s
user    0m0.512s
sys     0m0.092s

Wie Sie oben sehen können, ist der zeitaufwendige Schritt das Drucken der Daten. Wenn Sie einfach zu einer neuen Datei umleiten und diese durchgehen, ist dies viel schneller, wenn Sie die Datei nur einmal lesen.


Und wie gewünscht mit einem Here-String:

 $ time (log=$(tail -n 1000000 foo); grep 'true' <<< $log | wc -l; 
                                     grep 'false' <<< $log | wc -l  )
1
1

real    0m7.574s
user    0m7.092s
sys     0m0.516s

Dieser ist sogar noch langsamer, vermutlich, weil der Here-String alle Daten in einer langen Zeile zusammenfasst, und das verlangsamt Folgendes grep:

$ tail -n 1000000 foo | (time grep -c 'true')
666666

real    0m0.500s
user    0m0.472s
sys     0m0.000s

$ tail -n 1000000 foo | perl -pe 's/\n/ /' | (time grep -c 'true')
1

real    0m1.053s
user    0m0.048s
sys     0m0.068s

Wenn die Variable in Anführungszeichen gesetzt ist, damit keine Aufteilung erfolgt, sind die Dinge etwas schneller:

 $ time (log=$(tail -n 1000000 foo); grep 'true' <<< "$log" | wc -l; 
                                     grep 'false' <<< "$log" | wc -l  )
666666
333333

real    0m6.545s
user    0m6.060s
sys     0m0.548s

Aber immer noch langsam, da die Geschwindigkeitsbegrenzung die Daten druckt.

terdon
quelle
Warum versuchst du <<<es nicht? Es wäre interessant zu sehen, ob das einen Unterschied macht.
Graeme
3

Ich habe es auch versucht ... Zuerst habe ich die Datei erstellt:

printf '"success": "true"
        "success": "true"
        "success": "false"
        %.0b' `seq 1 500000` >|/tmp/log

Wenn Sie das oben genannte selbst ausführen, sollten Sie 1,5 Millionen Zeilen /tmp/logmit einem Verhältnis von 2: 1 von "success": "true"Zeilen zu "success": "false"Zeilen erstellen .

Als nächstes habe ich einige Tests durchgeführt. Ich habe alle Tests über einen Proxy durchgeführt, musste shalso timenur einen einzigen Prozess überwachen und konnte daher ein einziges Ergebnis für den gesamten Auftrag anzeigen.

Dies scheint die schnellste zu sein, obwohl es einen zweiten Dateideskriptor hinzufügt und tee,ich denke, ich kann erklären, warum:

    time sh <<-\CMD
        . <<HD /dev/stdin | grep '"success": "true"' | wc -l
            tail -n 1000000 /tmp/log | { tee /dev/fd/3 |\
                grep '"success": "false"' |\
                    wc -l 1>&2 & } 3>&1 &
        HD
    CMD
666666
333334
sh <<<''  0.11s user 0.08s system 84% cpu 0.224 total

Hier ist dein erstes:

    time sh <<\CMD
        tail -n 1000000 /tmp/log | grep '"success": "true"' | wc -l
        tail -n 1000000 /tmp/log | grep '"success": "false"' | wc -l
    CMD

666666
333334
sh <<<''  0.31s user 0.17s system 148% cpu 0.323 total

Und dein zweites:

    time sh <<\CMD
        log=$(tail -n 1000000 /tmp/log)
        echo "$log" | grep '"success": "true"' | wc -l
        echo "$log" | grep '"success": "false"' | wc -l
    CMD
666666
333334
sh <<<''  2.12s user 0.46s system 108% cpu 2.381 total

Sie können sehen, dass es in meinen Tests mehr als 3 * Geschwindigkeitsunterschiede gab, als Sie es in eine Variable eingelesen haben.

Ich denke, ein Teil davon ist, dass eine Shell-Variable geteilt und von der Shell behandelt werden muss, wenn sie gelesen wird - es ist keine Datei.

A here-documentdagegen ist in jeder Hinsicht ein file- einfile descriptor, ohnehin. Und wie wir alle wissen - Unix arbeitet mit Dateien.

Was mich am meisten interessiert here-docsist, dass man sie file-descriptors- als Straight |pipe- manipulieren und ausführen kann. Dies ist sehr praktisch, da Sie ein wenig mehr Freiheit haben, zu zeigen, |pipewohin Sie möchten.

Ich musste teedie, tailweil die erste die grepisst here-doc |pipeund die zweite nichts mehr zu lesen hat. Aber da ich |pipedes in /dev/fd/3und nahm es wieder auf, um >&1 stdout,es weiterzugeben, machte es nicht viel aus. Wenn Sie grep -cso viele andere verwenden, empfehlen Sie:

    time sh <<-\CMD
        . <<HD /dev/stdin | grep -c '"success": "true"'
            tail -n 1000000 /tmp/log | { tee /dev/fd/3 |\
                grep -c '"success": "false"' 1>&2 & } 3>&1 &
        HD
    CMD
666666
333334
sh <<<''  0.07s user 0.04s system 62% cpu 0.175 total

Es geht noch schneller.

Aber wenn ich es ohne . sourcingdas ausführe, heredockann ich den ersten Prozess nicht erfolgreich im Hintergrund ausführen, um sie vollständig gleichzeitig auszuführen. Hier ist es ohne Hintergrund:

    time sh <<\CMD
        tail -n 1000000 /tmp/log | { tee /dev/fd/3 |\
            grep -c '"success": "true"' 1>&2 & } 3>&1 |\
                grep -c '"success": "false"'
    CMD
666666
333334
sh <<<''  0.10s user 0.08s system 109% cpu 0.165 total

Aber wenn ich das hinzufüge &:

    time sh <<\CMD
        tail -n 1000000 /tmp/log | { tee /dev/fd/3 |\
            grep -c '"success": "true"' 1>&2 & } 3>&1 & |\
                grep -c '"success": "false"'
    CMD
sh: line 2: syntax error near unexpected token `|'

Trotzdem scheint der Unterschied, zumindest für mich, nur ein paar Hundertstelsekunden zu betragen. Nehmen Sie ihn also so, wie Sie wollen.

Wie auch immer, der Grund, warum es schneller läuft, teeist, dass beide grepsgleichzeitig mit nur einem Aufruf von tail. teeduplicates die Datei für uns ausführen und sie an den zweiten grepProzess weiterleiten - alles läuft auf einmal von Anfang bis Ende, so dass sie alle landen auch ungefähr zur selben Zeit.

Kehren Sie also zu Ihrem ersten Beispiel zurück:

    tail | grep | wc #wait til finished
    tail | grep | wc #now we're done

Und dein zweites:

    var=$( tail ) ; #wait til finished
    echo | grep | wc #wait til finished
    echo | grep | wc #now we're done

Aber wenn wir unsere Eingaben aufteilen und unsere Prozesse gleichzeitig ausführen:

          3>&1  | grep #now we're done
              /        
    tail | tee  #both process together
              \  
          >&1   | grep #now we're done
U / min mikeserv
quelle
1
+1 aber dein letzter Test ist mit einem Syntaxfehler gestorben, ich glaube nicht, dass die Zeiten dort korrekt sind :)
terdon
@terdon Sie könnten sich irren - ich wies darauf hin, dass es gestorben ist. Ich habe den Unterschied zwischen & und no & gezeigt - wenn Sie es hinzufügen, wird die Shell verärgert. Aber ich habe viel kopiert / eingefügt, damit ich ein oder zwei durcheinander gebracht habe, aber ich denke, sie sind in Ordnung ...
mikeserv
sh: Zeile 2: Syntaxfehler in der Nähe des unerwarteten Tokens "|"
Terdon
@terdon Ja, dass - "Ich kann den ersten Prozess, der sie gleichzeitig ausführt, nicht erfolgreich im Hintergrund ausführen. Sehen Sie?" Der erste ist nicht im Hintergrund, aber wenn ich & hinzufüge, um dies zu tun, "unerwartetes Token". Wenn ich . Quelle der Heredoc Ich kann die & verwenden.
mikeserv