grep.asm – Schritt 2: Ein besseres `cat`

2018-09-22

Sorry für die lange Wartezeit. Geht nicht wirklich schnell voran im Moment. Tja.

Auch dieses Posting braucht wieder einen Disclaimer: Da ich kein Assembler-Experte bin, bin ich über jede Korrektur und jeden Verbesserungshinweis dankbar!

Mehr Daten auf einmal lesen

Eines der großen Probleme der vorherigen Version war, dass wir ein Byte nach dem anderen gelesen haben. Dadurch wurde der Code zwar ein bisschen einfacher, aber das ist wirklich langsam. Wenn man erwartet, mehr als nur ein paar Bytes zu lesen, dann sollte man das anders machen. Mein bevelbar liest von STDIN und liest in der Tat Byte für Byte, aber da fließen eben auch nicht viele Daten. Die meiste Zeit über schläft bevelbar, also interessiert es keinen.

Anders bei einem grep. Mein voriger Code hat etwa 1.8 Sekunden gebraucht, um eine Datei von 4 MB zu verarbeiten. Das ist echt nicht gut. Jetzt dauert es nur noch etwa 60 Millisekunden, was immer noch nicht schnell ist, aber schonmal deutlich besser als vorher.

Dieser Performance-Sprung liegt daran, dass jetzt eben nicht mehr Byte für Byte gelesen wird. Man erinnere sich, dass „Byte für Byte lesen“ bedeutet, für jedes Byte einen Syscall absetzen zu müssen. Jeder Syscall ist mit viel Overhead verbunden und daher kommt es zu einer unnötigen Verzögerung. Um das zu vermeiden, allokiert das Programm jetzt einen großen Puffer von 4 MB und setzt nur noch einen read()-Syscall ab. (Idealerweise. read muss nicht alle angeforderten Bytes tatsächlich lesen, sondern kann auch schon vorher zurückkehren. Dann muss man es nochmal aufrufen, um den Rest zu bekommen.)

Faul bin ich aber immer noch: Das Programm liest den gesamten Input, bis ein End-of-File erreicht wird. Das heißt, wenn man durch eine Datei von 1 GB Größe greppen will, dann braucht man 1 GB an Speicher. Das lässt sich später aber leicht optimieren – ich habe das Programm schon so organisiert, dass sich die anderen Funktionen nicht mehr um dieses Implementierungsdetail kümmern müssen. Die arbeiten alle mit einem „struct“, in welchem beschrieben ist: „Hier ist ein Puffer, die aktuelle Zeile fängt hier an und ist so lang.“

Okay, so sieht die Hauptschleife jetzt (ohne Kommentare) aus:

.text
.global _start

_start:
    pushq %rbp
    movq %rsp, %rbp

    subq $64, %rsp
    movq %rbp, %rdi
    call init_buffer_info

    .Lreadwriteloop:
        movq %rbp, %rdi
        call next_line

        cmpq $0, %rax
        je .Lreadwriteloop_end

        movq %rbp, %rdi
        call test_match

        cmpq $0, %rax
        je .Lreadwriteloop

        movq %rbp, %rdi
        call print_current

        jmp .Lreadwriteloop

    .Lreadwriteloop_end:
        movq $0, %rdi
        call exit

In Pseudocode:

- Initialize a thing called "buffer info".
- Loop:
    - Read a line. (Update "buffer info" and mark the current line.)
    - Exit if no line left.
    - Test if the current line matches a pattern.
    - Loop again, if it doesn't.
    - Print the current line.

Im Moment wird beim ersten Aufruf von next_line() alles in einen großen Puffer eingelesen. Spätere Aufrufe aktualisieren dann nur noch Pointer und Counter. Wie man aber sehen kann, ist das für die Hauptschleife und die Funktionen egal.

Wieso? Auf dem lokalen Stack von _start wird Speicher für 64 Bytes allokiert. Dort drin speichern wir dann ein „struct“ namens „buffer info“. „struct“ meint hier im Wesentlichen dasselbe wie ein struct in C. Es enthält diverse Felder:

 -8(%rbp), 8 = pointer to data (char *)
-16(%rbp), 8 = allocated size of entire buffer (size_t)
-24(%rbp), 8 = current fill of buffer (size_t)
-32(%rbp), 8 = offset for current line in buffer (size_t)
-40(%rbp), 8 = length of current line (size_t)

So ziemlich alle Funktionen arbeiten mit diesem struct: next_line() sorgt dafür, dass der Pointer und die Counter auf die aktuelle Zeile zeigen; test_match() arbeitet nur auf der aktuellen Zeile; print_current() gibt ausschließlich die aktuelle Zeile aus.

Die Details von next_line() überspringen wir jetzt. Da sind viele Kommentare drin. Ähnlich wie bei der vorigen Version verwaltet es Speicher mit dem Syscall brk() und liest Daten mit read().

Mit `rep stosb` Speicher initialisieren

Eine frühe Version von init_buffer_info() sah so aus:

movq $0, -8(%rdi)
movq $0, -16(%rdi)
movq $0, -24(%rdi)
movq $0, -32(%rdi)
movq $0, -40(%rdi)

Heißt also, es wird nur ein Haufen Nullen in den Speicher geschrieben. Das sind jetzt nur fünf Instruktionen, die nur ein Mal während der gesamten Laufzeit des Programms aufgerufen werden, also spielt’s sehr wahrscheinlich keine Rolle, wie man das macht. Die Frage stellte sich aber trotzdem: Was, wenn man ein paar Megabytes an Speicher initialisieren wollte? Oder mehr?

Klar, man kann es so machen (für len >= 1):

movq $0, %rcx
movq $pointer, %rdi
.Lloop_start:
    movb $0, (%rdi)
    inc %rdi
    inc %rcx
    cmpq $len, %rcx
    jne .Lloop_start

Aber gibt’s da keinen besseren Weg? Da ich nun nicht allzu viel Erfahrung mit Assembler habe, ist das beste, was ich finden konnte, der „rep“-Mechanismus, der mit „string instructions“ zusammenarbeitet.

In diesem konkreten Fall benutzen wir mal rep stosb:

movq $pointer, %rdi
movq $40, %rcx
movb $0, %al
rep stosb

Wir schreiben also eine 40 in %rcx, dann ein NULL-Byte nach %al. stosb liest dann dieses Byte aus %al aus und schreibt es im Speicher an die Stelle von %rdi. (Segmentierung ignorieren wir.) stosb erhöht dann auch automatisch den Pointer %rdi um eins, damit beim nächsten Aufruf das folgende Byte im String angefasst wird. Und wie ruft man stosb nochmal auf? rep erledigt das. rep lässt die Instruktion immer und immer wieder laufen, bis irgendwann %rcx den Wert 0 erreicht.

Das ist also eine sehr knappe Form von memset().

Noch ein kleines Detail. String-Operationen wie stosb können den Wert in %rdi erhöhen, wie oben gesehen, oder verringern. Das hängt davon ab, ob das „direction flag“ gesetzt ist. Mit std kann man es setzen oder mit cld löschen.

Noch mehr `rep`: Mit `repne scasb` ein `strlen()` implementieren

Okay, unser grep liest also einen großen Haufen Daten und schreibt sie in einen Puffer. Den muss es dann natürlich durchsuchen, um die einzelnen Zeilen herauszufischen – weil grep ein zeilenorientiertes Programm ist.

Man erinnere sich an das struct vom Anfang:

 -8(%rbp), 8 = pointer to data (char *)
...
-32(%rbp), 8 = offset for current line in buffer (size_t)
-40(%rbp), 8 = length of current line (size_t)

Bei jedem Aufruf muss next_line() also offset erhöhen und length aktualisieren. Das tut es, indem es bei pointer + offset startet und dann jedes folgende Byte prüft, ob es ein Newline-Character ist. Sobald einer gefunden ist, wird die beobachtete Länge in length abgelegt.

Das ist im Wesentlichen dasselbe wie das traditionelle strlen(), bloß dass eben auf ein Newline geprüft wird und nicht auf ein NULL-Byte.

Nun könnte man das natürlich so programmieren, dass man einfach manuell eine Schleife schreibt. Genau das hatte ich zuerst auch gemacht und das sah so aus:

current_line_length:
    /* Find the length of the current line.
     *
     * in:
     *   %rdi, pointer to base of info struct
     *
     * out:
     *   %rax, current line length */

    movq $0, %rax
    movq -8(%rdi), %rbx
    movq -24(%rdi), %rcx
    movq -32(%rdi), %rdx
    addq %rdx, %rbx

    .Lfind_next_newline_loop:
        cmpb $10, (%rbx)
        je .Lfind_next_newline_found

        incq %rax
        incq %rbx
        incq %rdx
        cmpq %rdx, %rcx
        je .Lfind_next_newline_exceeded_bounds_check

        jmp .Lfind_next_newline_loop

    .Lfind_next_newline_found:
        incq %rax
        ret

    .Lfind_next_newline_exceeded_bounds_check:
        ret

Ziemlich lang und ausführlich.

Hier kann man dann wieder ein rep-Konstrukt stattdessen verwenden:

current_line_length:
    movq -8(%rdi), %rdx
    movq -32(%rdi), %rbx
    addq %rbx, %rdx

    movq -24(%rdi), %rcx
    movq -32(%rdi), %rbx
    subq %rbx, %rcx
    movq %rcx, %rbx

    movq %rdx, %rdi
    movb $10, %al
    cld
    repne scasb

    subq %rcx, %rbx
    movq %rbx, %rax
    ret

Diesmal benutzen wir repne statt wie oben rep. Das wiederholt ebenfalls die Instruktion, bis %rcx 0 erreicht hat, prüft aber zusätzlich auch das „Zero Flag“, wie man bei Intel in der Dokumentation zum x86 Instruction Set nachlesen kann.

Jetzt muss man ein kleines Detail kennen: Wenn man ein cmp %rax, %rbx ausführt, zieht die CPU die beiden Register voneinander ab. Ein darauffolgendes je („jump if equal“) ist dann dafür gedacht, den Sprung durchzuführen, wenn die beiden Werte gleich waren – oder anders gesagt, wenn eine Subtraktion 0 ergeben hat. Dafür wird das Zero Flag benutzt. Wenn es also gesetzt ist (Subtraktion ergab 0), dann waren die beiden Werte gleich.

Wenn die Intel-Doku also von „repeat while ZF flag is clear“ spricht, ist das dasselbe, wie wenn man sagen würde „repeat while a comparison did not determine two values to be equal“. Deswegen ist auch repnz („repeat while not zero“) nur ein Alias für repne („repeat while not equal“).

Gut. Wir wissen jetzt also, was repne tut. Jetzt brauchen wir noch eine String-Operation ähnlich zu stosb, was wir in init_buffer_info() benutzt haben, aber diesmal soll sie den String nicht verändern, sondern nur Bytes daraus mit einem Wert vergleichen. Und das erledigt dann scasb: Das ist kurz für „scan string, length byte“. Das führt ein cmpb %al, (%rdi) aus und erhöhrt/verringert danach %rdi. Das repne drumherum wertet dann das Ergebnis dieses cmp aus (und prüft, ob %rcx die 0 erreicht hat).

Kurzum, wir haben nun ein strlen().

Da ist immer noch eine ganze Menge „Noise“ oben im Code um das eigentliche repne scasb drumherum. Trotzdem glaube ich, dass das so besser ist als der vorherige Spaghetti-Code. Man muss nur mit rep* vertraut sein.

Fazit

Reguläre Ausdrücke sind immer noch nicht in Sicht, aber wir haben schonmal ein paar der naiven Dinge des ersten cat behoben. Der Code beachtet jetzt auch die Rückgabewerte von Syscalls.

Oh, wenn man sich den Code von grep.asm anschaut, beachte man bitte die Git-Tags. Unter blogpost-step-2 findet man den die zu diesem Blogpost zugehörige Version.

Jetzt ist es also Zeit, test_match() zu schreiben.

Fortsetzung: Diese Serie geht in grep.asm – Schritt 3: Reguläre Ausdrücke erkennen weiter.

Comments?

grep.asm – Schritt 2: Ein besseres cat

Mehr Daten auf einmal lesen

Mit rep stosb Speicher initialisieren

Noch mehr rep: Mit repne scasb ein strlen() implementieren

Fazit

grep.asm – Schritt 2: Ein besseres `cat`

Mit `rep stosb` Speicher initialisieren

Noch mehr `rep`: Mit `repne scasb` ein `strlen()` implementieren