So beschleunigen Sie das Entladen von LZ4 in ClickHouse

Wenn Sie Abfragen in ClickHouse ausführen, können Sie feststellen, dass im Profiler an einer der ersten Stellen häufig die Funktion LZ_decompress_fast sichtbar ist. Warum passiert das? Diese Frage wurde zum Grund für die gesamte Studie zur Auswahl des besten Dekomprimierungsalgorithmus. Hier veröffentliche ich die gesamte Studie und die Kurzversion finden Sie in meinem Bericht über HighLoad ++ Siberia.

ClickHouse-Daten werden in komprimierter Form gespeichert. Und während der Ausführung von Anforderungen versucht ClickHouse fast nichts zu tun - verwenden Sie ein Minimum an CPU-Ressourcen. Es kommt vor, dass alle Berechnungen, die eine Weile dauern können, bereits gut optimiert sind und die Anforderung vom Benutzer gut geschrieben wurde. Dann bleibt die Freigabe durchzuführen.



Die Frage ist - warum kann das Entladen von LZ4 ein Engpass sein? Es scheint, dass LZ4 ein sehr leichter Algorithmus ist : Die Komprimierungsrate liegt je nach Daten normalerweise zwischen 1 und 3 GB / s pro Prozessorkern. Dies ist deutlich mehr als die Geschwindigkeit des Festplattensubsystems. Darüber hinaus verwenden wir alle verfügbaren Kernel und die Erweiterung skaliert linear über alle physischen Kernel.

Es sind jedoch zwei Punkte zu beachten. Zunächst werden komprimierte Daten von der Festplatte gelesen, und die Komprimierungsrate wird in der Menge der nicht komprimierten Daten angegeben. Wenn das Komprimierungsverhältnis groß genug ist, muss fast nichts von den Datenträgern gelesen werden. Gleichzeitig werden jedoch viele komprimierte Daten generiert, was sich natürlich auf den CPU-Verbrauch auswirkt: Der Umfang der Datenkomprimierungsarbeit bei LZ4 ist nahezu proportional zum Volumen der komprimierten Daten.

Zweitens ist das Lesen von Daten von Datenträgern möglicherweise überhaupt nicht erforderlich, wenn sich die Daten im Cache befinden. Dazu können Sie sich auf den Seitencache verlassen oder Ihren eigenen Cache verwenden. In einer Spaltendatenbank ist die Verwendung des Caches effizienter, da nicht alle Spalten in den Cache fallen, sondern nur häufig verwendete. Aus diesem Grund ist LZ4 in Bezug auf die CPU-Auslastung häufig ein Engpass.

Daher noch zwei Fragen. Wenn die Datenkomprimierung "verlangsamt" wird, sollten sie möglicherweise überhaupt nicht komprimiert werden? In der Praxis ist diese Annahme jedoch bedeutungslos. Kürzlich war es in ClickHouse möglich, nur zwei Datenkomprimierungsoptionen zu konfigurieren - LZ4 und Zstandard . Der Standardwert ist LZ4. Durch Umschalten auf Zstandard können Sie die Komprimierung stärker und langsamer machen. Bis vor kurzem war es jedoch unmöglich, die Komprimierung vollständig zu deaktivieren - LZ4 wird als angemessenes Minimum angesehen, das immer verwendet werden kann. Deshalb liebe ich den LZ4 wirklich. :) :)

Aber kürzlich erschien im englischsprachigen Chat-Chat von ClickHouse ein mysteriöser Fremder, der sagte, er habe ein sehr schnelles Festplattensubsystem (NVMe SSD) und alles hänge von der Komprimierung ab - es wäre schön, es ausschalten zu können. Ich antwortete, dass es keine solche Möglichkeit gibt, aber es ist einfach hinzuzufügen. Einige Tage später erhielten wir eine Poolanforderung , die die Methode der none implementiert. Ich fragte nach den Ergebnissen - wie sehr dies half, wie schnell die Anfragen waren. Die Person sagte, dass sich diese neue Funktion in der Praxis als nutzlos herausstellte, da Daten ohne Komprimierung zu viel Platz beanspruchten.

Die zweite Frage lautet: Wenn es einen Cache gibt, warum nicht die bereits unkomprimierten Daten darin speichern? Dies ist zulässig - in vielen Fällen wird es möglich sein, die Notwendigkeit einer Dekompression zu beseitigen. Und in ClickHouse gibt es einen solchen Cache - einen Cache aus erweiterten Blöcken . Es ist jedoch schade, aufgrund der geringen Effizienz viel RAM dafür auszugeben. Es rechtfertigt sich nur bei kleinen, aufeinanderfolgenden Anfragen, die fast dieselben Daten verwenden.

Allgemeine Überlegung: Daten sollten vorzugsweise immer komprimiert werden. Brennen Sie sie immer auf eine komprimierte Festplatte. Über das Netzwerk auch mit Komprimierung übertragen. Meiner Meinung nach sollte die Standardkomprimierung als gerechtfertigt angesehen werden, selbst wenn die Übertragung in ein 10-Gigabit-Netzwerk ohne Überzeichnung innerhalb des Rechenzentrums erfolgt und die Übertragung von Daten ohne Komprimierung zwischen Rechenzentren im Allgemeinen nicht akzeptabel ist.

Warum LZ4?

Warum wird LZ4 verwendet? Ist es möglich, etwas noch einfacher zu wählen? Im Prinzip ist es möglich und es ist richtig und nützlich. Aber schauen wir uns zuerst an, zu welcher Klasse von Algorithmen LZ4 gehört.

Erstens hängt es nicht vom Datentyp ab. Wenn Sie beispielsweise im Voraus wissen, dass Sie ein Array von Ganzzahlen haben, können Sie eine der vielen Varianten des VarInt-Algorithmus verwenden - dies ist effizienter für die CPU. Zweitens hängt LZ4 nicht zu stark von den erforderlichen Annahmen im Datenmodell ab. Angenommen, Sie haben eine geordnete Zeitreihe von Sensorablesungen - ein Array mit Nummern vom Typ float. Dann können Sie die Deltas berechnen und dann weiter komprimieren, was im Hinblick auf das Kompressionsverhältnis effizienter ist.

Das heißt, LZ4 kann problemlos für alle Byte-Arrays verwendet werden - für alle Dateien. Natürlich hat er seine eigene Spezialisierung (mehr dazu weiter unten), und in einigen Fällen ist ihre Verwendung bedeutungslos. Wenn Sie es jedoch als Allzweckalgorithmus bezeichnen, ist dies ein kleiner Fehler. Beachten Sie, dass LZ4 dank des internen Geräts den RLE- Algorithmus automatisch als Sonderfall implementiert.

Eine andere Frage: Ist LZ4 der optimalste Algorithmus dieser Klasse für die Kombination von Geschwindigkeit und Kompressionskraft? Solche Algorithmen werden als Pareto-Grenze bezeichnet - dies bedeutet, dass es keinen anderen Algorithmus gibt, der in einem Indikator streng besser und in anderen nicht schlechter ist (und sogar in einer Vielzahl von Datensätzen). Es gibt Algorithmen, die schneller sind, aber ein niedrigeres Komprimierungsverhältnis ergeben, und es gibt Algorithmen, die mehr komprimieren, aber gleichzeitig langsamer komprimieren oder dekomprimieren.

Tatsächlich ist die LZ4 keine Pareto-Grenze. Es gibt Optionen, die etwas besser sind. Dies ist beispielsweise LZTURBO aus einem bestimmten Powturbo . Dank der Community auf encode.ru (dem größten und ungefähr einzigen Forum für Datenkomprimierung) besteht kein Zweifel an der Zuverlässigkeit der Ergebnisse. Der Entwickler verteilt den Quellcode oder die Binärdateien jedoch nicht, sondern gibt sie nur an einen begrenzten Personenkreis zum Testen oder für viel Geld weiter (wie bisher noch niemand bezahlt hat). Es lohnt sich auch, auf Lizard (ehemals LZ5) und Density zu achten. Sie können bei der Auswahl einer bestimmten Komprimierungsstufe etwas besser als LZ4 arbeiten. Achten Sie auch auf LZSSE - eine äußerst interessante Sache. Es ist jedoch besser, es nach dem Lesen dieses Artikels anzusehen.

Wie funktioniert LZ4?

Schauen wir uns an, wie LZ4 im Allgemeinen funktioniert. Dies ist eine der Implementierungen des LZ77-Algorithmus: L und Z geben die Namen der Autoren (Lempel und Ziv) und 77 an - 1977, als der Algorithmus veröffentlicht wurde. Es gibt viele andere Implementierungen: QuickLZ, FastLZ, BriefLZ, LZF, LZO sowie gzip und zip bei Verwendung niedriger Komprimierungsstufen.

Ein mit LZ4 komprimierter Datenblock enthält eine Folge von Datensätzen (Befehlen, Anweisungen) zweier Typen:

1. Literal: "Nehmen Sie die nächsten N Bytes wie sie sind und kopieren Sie sie in das Ergebnis."
2. Übereinstimmung (Übereinstimmung): "Nehmen Sie N Bytes, die bereits durch den Versatzversatz von der aktuellen Position dekomprimiert wurden."

Ein Beispiel. Vor der Komprimierung:
Hello world Hello

Nach der Komprimierung:
literals 12 "Hello world " match 5 12

Wenn wir einen komprimierten Block nehmen und ihn mit dem Cursor durchlaufen und diese Befehle ausführen, erhalten wir als Ergebnis die anfänglichen, nicht komprimierten Daten.

Wir haben uns grob angesehen, wie die Daten dekomprimiert werden. Der Punkt ist auch klar: Um eine Komprimierung durchzuführen, codiert der Algorithmus sich wiederholende Bytesequenzen unter Verwendung von Übereinstimmungen.

Klar und einige Eigenschaften. Dieser Algorithmus ist byteorientiert - er zerlegt einzelne Bytes nicht, sondern kopiert sie nur vollständig. Hier liegt beispielsweise der Unterschied zur Entropiecodierung. Zum Beispiel ist zstd eine Zusammensetzung aus LZ77 und Entropiecodierung.

Beachten Sie, dass die Größe des komprimierten Blocks nicht zu groß gewählt wird, um beim Entladen nicht viel RAM zu verbrauchen. um den Direktzugriff in einer komprimierten Datei (die aus vielen komprimierten Blöcken besteht) nicht zu verlangsamen; und manchmal, damit der Block in einen CPU-Cache passt. Sie können beispielsweise 64 KB auswählen, sodass Puffer für komprimierte und nicht komprimierte Daten in den L2-Cache passen und die Hälfte verbleibt.

Wenn wir eine größere Datei komprimieren müssen, verketten wir einfach die komprimierten Blöcke. Gleichzeitig ist es bequem, neben jedem komprimierten Block zusätzliche Daten zu platzieren - Größen, Prüfsumme.

Der maximale Offset für das Match ist in LZ4 - 64 Kilobyte begrenzt. Dieser Wert wird als Schiebefenster bezeichnet. In der Tat bedeutet dies, dass Übereinstimmungen in einem Fenster von 64 Kilobyte Größe mit dem Cursor erfolgen können, der sich mit dem Cursor bewegt, wenn sich der Cursor vorwärts bewegt.

Schauen wir uns nun an, wie Daten komprimiert werden - mit anderen Worten, wie übereinstimmende Sequenzen in einer Datei gefunden werden. Natürlich können Sie das Suffix trie verwenden (großartig, wenn Sie davon gehört haben). Es gibt Optionen, bei denen die längste übereinstimmende Sequenz garantiert zu den vorherigen Bytes im Komprimierungsprozess gehört. Dies wird als optimales Parsen bezeichnet und ergibt ein fast besseres Komprimierungsverhältnis für ein festes komprimiertes Blockformat. Es gibt jedoch effektivere Optionen - wenn wir eine ausreichend gute Übereinstimmung in den Daten finden, aber nicht unbedingt die längste. Der effizienteste Weg, dies zu finden, ist die Verwendung einer Hash-Tabelle.

Dazu gehen wir mit dem Cursor durch den Quelldatenblock und nehmen einige Bytes nach dem Cursor. Zum Beispiel 4 Bytes. Hash sie und füge den Offset vom Anfang des Blocks in die Hash-Tabelle ein - wo diese 4 Bytes aufeinander trafen. Der Wert 4 heißt min-match - mit Hilfe einer solchen Hash-Tabelle können wir Übereinstimmungen von mindestens 4 Bytes finden.

Wenn wir uns die Hash-Tabelle angesehen haben und dort bereits ein Datensatz vorhanden ist und der Versatz das Schiebefenster nicht überschreitet, prüfen wir, wie viele weitere Bytes nach diesen vier Bytes übereinstimmen. Vielleicht fällt noch viel mehr zusammen. Es ist auch möglich, dass eine Kollision in der Hash-Tabelle aufgetreten ist und nichts übereinstimmt. Dies ist normal - Sie können den Wert in der Hash-Tabelle einfach durch einen neuen ersetzen. Kollisionen in der Hash-Tabelle führen einfach zu einem niedrigeren Komprimierungsverhältnis, da weniger Übereinstimmungen vorhanden sind. Übrigens wird diese Art von Hash-Tabelle (mit fester Größe und ohne Kollisionsauflösung) als Cache-Tabelle, als Cache-Tabelle bezeichnet. Dies ist auch logisch - im Falle einer Kollision vergisst die Cache-Tabelle nur den alten Datensatz.

Die Aufgabe für den aufmerksamen Leser. Die Daten seien ein Array von Zahlen wie UInt32 im Little-Endian-Format, das Teil einer Folge natürlicher Zahlen ist: 0, 1, 2 ... Erklären Sie, warum diese Daten bei Verwendung von LZ4 nicht komprimiert werden (die Menge der komprimierten Daten ist nicht geringer als die Menge der nicht komprimierten Daten).

Wie man Dinge beschleunigt

Deshalb möchte ich das Entladen von LZ4 beschleunigen. Mal sehen, wie der Entladezyklus aussieht. Hier ist die Schleife im Pseudocode:

  während (...)
 {
     read (input_pos, literal_length, match_length);

     copy (output_pos, input_pos, literal_length);
     output_pos + = literal_length;

     read (input_pos, match_offset);

     copy (output_pos, output_pos - match_offset,
         match_length);
     output_pos + = match_length;
 }} 

Das LZ4-Format ist so konzipiert, dass sich Literale und Übereinstimmungen in einer komprimierten Datei abwechseln. Und natürlich steht das Wörtliche immer an erster Stelle (denn von Anfang an hat das Match nichts zu bieten). Daher werden ihre Längen zusammen codiert.

In der Tat ist alles etwas komplizierter. Ein Byte wird aus der Datei gelesen und zwei Halbbytes daraus entnommen, in denen Zahlen von 0 bis 15 codiert sind. Wenn die entsprechende Zahl nicht gleich 15 ist, wird dies als Länge des Literals bzw. der Übereinstimmung betrachtet. Und wenn es 15 ist, ist die Länge länger und es wird in den folgenden Bytes codiert. Dann wird das nächste Byte gelesen und sein Wert zur Länge addiert. Wenn es gleich 255 ist, fahren wir fort - wir lesen das nächste Byte auf die gleiche Weise.

Beachten Sie, dass das maximale Komprimierungsverhältnis für das LZ4-Format 255 nicht erreicht. Und die zweite (nutzlose) Beobachtung: Wenn Ihre Daten sehr redundant sind, erhöht die Verwendung von LZ4 das Komprimierungsverhältnis doppelt.

Wenn wir die Länge des Literal (und dann auch die Länge der Übereinstimmung und den Versatz der Übereinstimmung) lesen, reicht es aus, um einfach zwei Speicherelemente zu kopieren, um sie zu lösen.

So kopieren Sie ein Stück Speicher

Es scheint, dass Sie die memcpy Funktion verwenden können, die nur zum Kopieren von Speicherelementen dient. Dies ist jedoch nicht optimal und immer noch falsch.

Warum ist die Verwendung der memcpy-Funktion nicht optimal? Weil sie:

1. befindet sich normalerweise in der libc-Bibliothek (und die libc-Bibliothek wird normalerweise dynamisch verknüpft, und der memcpy-Aufruf erfolgt indirekt über PLT).
2. nicht im Einklang mit dem in der Kompilierungszeit unbekannten Größenargument,
3. unternimmt große Anstrengungen, um die "Schwänze" eines Speicherfragments, die nicht ein Vielfaches der Größe eines Maschinenworts oder Registers haben, korrekt zu verarbeiten.

Der letzte Punkt ist der wichtigste. Angenommen, wir haben die memcpy-Funktion gebeten, genau 5 Bytes zu kopieren. Es wäre sehr gut, 8 Bytes gleichzeitig mit zwei movq-Anweisungen zu kopieren.

Hello world Hello wo ...
^^^^^ ^^^ - src
^^^^^ ^^^ - dst

Aber dann werden wir drei zusätzliche Bytes kopieren - das heißt, wir werden den übertragenen Puffer ins Ausland schreiben. Die memcpy Funktion hat nicht das Recht, dies zu tun. Da wir einige Daten in unserem Programm überschreiben, wird es eine „Passage“ aus dem Speicher geben. Und wenn wir an einer nicht ausgerichteten Adresse geschrieben haben, können sich diese zusätzlichen Bytes auf einer nicht zugewiesenen virtuellen Speicherseite oder auf einer Seite ohne Schreibzugriff befinden. Dann bekommen wir Segfault (das ist gut).

In unserem Fall können wir jedoch fast immer zusätzliche Bytes schreiben. Wir können zusätzliche Bytes im Eingabepuffer lesen, solange sich die zusätzlichen Bytes vollständig darin befinden. Unter den gleichen Bedingungen können wir zusätzliche Bytes in den Ausgabepuffer schreiben - da wir sie bei der nächsten Iteration trotzdem überschreiben.

Diese Optimierung ist bereits in der ursprünglichen LZ4-Implementierung enthalten:

  inline void copy8 (UInt8 * dst, const UInt8 * src)
 {
     memcpy (dst, src, 8);  /// Eigentlich wird memcpy hier nicht aufgerufen.
 }}

 inline void wildCopy8 (UInt8 * dst, const UInt8 * src, UInt8 * dst_end)
 {
     tun
     {
         copy8 (dst, src);
         dst + = 8;
         src + = 8;
     } while (dst <dst_end);
 }} 

Um diese Optimierung nutzen zu können, müssen Sie nur überprüfen, ob wir weit genug vom Rand des Puffers entfernt sind. Dies sollte kostenlos sein, da wir bereits prüfen, ob die Puffergrenzen überschritten werden. Und die Verarbeitung der letzten paar Bytes - das "Ende" der Daten - kann nach der Hauptschleife erfolgen.

Es gibt jedoch noch einige Feinheiten. Der Zyklus enthält zwei Kopien - Literal und Match. Bei Verwendung der Funktion LZ4_decompress_fast (anstelle von LZ4_decompress_safe) wird die Prüfung jedoch einmal durchgeführt - wenn das Literal kopiert werden muss. Beim Kopieren einer Übereinstimmung wird keine Überprüfung durchgeführt, aber die LZ4-Formatspezifikation selbst enthält Bedingungen, die es ermöglichen, sie zu vermeiden:

Die letzten 5 Bytes sind immer Literale
Die letzte Übereinstimmung muss mindestens 12 Byte vor dem Ende des Blocks beginnen.
Folglich kann ein Block mit weniger als 13 Bytes nicht komprimiert werden.

Speziell ausgewählte Eingabedaten können ein Speicherlaufwerk verursachen. Wenn Sie die Funktion LZ4_decompress_fast verwenden, benötigen Sie Schutz vor fehlerhaften Daten. Komprimierte Daten sollten mindestens eine Prüfsumme sein. Wenn Sie Schutz vor einem Angreifer benötigen, verwenden Sie die Funktion LZ4_decompress_safe. Andere Optionen: Nehmen Sie eine kryptografische Hash-Funktion als Prüfsumme, die jedoch mit ziemlicher Sicherheit die gesamte Leistung beeinträchtigt. entweder mehr Speicher für Puffer zuweisen; Weisen Sie entweder Speicher für Puffer mit einem separaten Aufruf von mmap zu und erstellen Sie eine Schutzseite.

Wenn ich einen Code sehe, der Daten von 8 Bytes kopiert, frage ich sofort - warum genau 8 Bytes? Sie können 16 Bytes mit SSE-Registern kopieren:

  inline void copy16 (UInt8 * dst, const UInt8 * src)
 {
 #if __SSE2__
     _mm_storeu_si128 (reinterpret_cast <__ m128i *> (dst),
         _mm_loadu_si128 (reinterpret_cast <const __m128i *> (src)));
 #else
     memcpy (dst, src, 16);
 #endif
 }}

 inline void wildCopy16 (UInt8 * dst, const UInt8 * src, UInt8 * dst_end)
 {
     tun
     {
         copy16 (dst, src);
         dst + = 16;
         src + = 16;
     } while (dst <dst_end);
 }} 

Das Kopieren von 32 Byte für AVX und 64 Byte für AVX-512 funktioniert ähnlich. Außerdem können Sie den Zyklus mehrmals erweitern. Wenn Sie sich jemals angesehen haben, wie memcpy implementiert ist, dann ist dies genau der memcpy Ansatz. (Übrigens wird der Compiler in diesem Fall die Schleife weder erweitern noch vektorisieren. Dies erfordert das Einfügen umständlicher Überprüfungen.)

Warum wird dies in der ursprünglichen LZ4-Implementierung nicht durchgeführt? Erstens ist es nicht offensichtlich, ob dies besser oder schlechter ist. Das Ergebnis hängt von der Größe der Fragmente ab, die kopiert werden müssen. Plötzlich sind sie alle kurz und zusätzliche Arbeit wird nutzlos sein? Und zweitens werden die Bedingungen im LZ4-Format zerstört, die es Ihnen ermöglichen, unnötigen Brunch in der inneren Schleife zu vermeiden.

Trotzdem werden wir diese Option vorerst berücksichtigen.

Tricky Kopie

Zurück zur Frage - ist es immer möglich, Daten auf diese Weise zu kopieren? Angenommen, wir müssen eine Übereinstimmung kopieren, dh ein Stück Speicher aus dem Ausgabepuffer, der sich in einem gewissen Versatz hinter dem Cursor befindet, an die Position dieses Cursors kopieren.

Stellen Sie sich einen einfachen Fall vor: Sie müssen 5 Bytes mit Offset 12 kopieren:

Hello world ...........
^^^^^ - src
^^^^^ - dst

Hello world Hello wo ...
^^^^^ - src
^^^^^ - dst

Es gibt jedoch einen komplizierteren Fall - wenn wir ein Stück Speicher kopieren müssen, dessen Länge größer als der Versatz ist. Das heißt, es zeigt teilweise Daten an, die noch nicht in den Ausgabepuffer geschrieben wurden.

Kopieren Sie 10 Bytes mit Offset 3:

abc .............
^^^^^^^^^^ - src
^^^^^^^^^^ - dst

abc abcabcabca ...
^^^^^^^^^^ - src
^^^^^^^^^^ - dst

Während des Komprimierungsprozesses haben wir alle Daten, und eine solche Übereinstimmung kann durchaus gefunden werden. Die Funktion memcpy eignet sich nicht zum Kopieren: Sie unterstützt nicht den Fall, dass sich die Bereiche der Speicherfragmente überschneiden. Die memmove Funktion memmove auch nicht geeignet, da das Speicherfragment, von dem die Daten memmove werden sollen, noch nicht vollständig initialisiert ist. Sie müssen kopieren, als würden wir byteweise kopieren.

  op [0] = match [0];
 op [1] = match [1];
 op [2] = match [2];
 op [3] = match [3];
 ... 

So funktioniert es:

a bc a ............
^ - src
^ - dst

a b ca b ...........
^ - src
^ - dst

ab c ab c ..........
^ - src
^ - dst

abc a bc a .........
^ - src
^ - dst

abca b ca b ........
^ - src
^ - dst

Das heißt, wir müssen eine sich wiederholende Sequenz erstellen. In der ursprünglichen LZ4-Implementierung wurde überraschend unverständlicher Code dafür geschrieben:

  const unsigned dec32table [] = {0, 1, 2, 1, 4, 4, 4, 4};
 const int dec64table [] = {0, 0, 0, -1, 0, 1, 2, 3};

 const int dec64 = dec64table [Offset];
 op [0] = match [0];
 op [1] = match [1];
 op [2] = match [2];
 op [3] = match [3];
 match + = dec32table [offset];
 memcpy (op + 4, match, 4);
 match - = dec64; 

Wir kopieren die ersten 4 Bytes byteweise, verschieben sie um eine magische Zahl, kopieren die nächsten 4 Bytes als Ganzes und verschieben den Zeiger so, dass er mit einer anderen magischen Zahl übereinstimmt. Der Code-Autor ( Jan Collet ) hat aus irgendeinem lächerlichen Grund vergessen, einen Kommentar zu hinterlassen, was dies bedeutet. Darüber hinaus sind Variablennamen verwirrend. Beide heißen dec ... table, aber wir addieren eine davon und subtrahieren die andere. Außerdem ist ein anderer nicht signiert und der andere ist int. Es lohnt sich jedoch, Tribut zu zollen: Erst kürzlich hat der Autor diesen Platz im Code verbessert.

So funktioniert es tatsächlich. Kopieren Sie die ersten 4 Bytes:

abc abca .........
^^^^ - src
^^^^ - dst

Jetzt können Sie 4 Bytes gleichzeitig kopieren:

abcabca bcab .....
^^^^ - src
^^^^ - dst

, 8 :

abcabcabcab cabcabca .....
^^^^^^^^ - src
^^^^^^^^ - dst

, — . Folgendes ist passiert:

 inline void copyOverlap8(UInt8 * op, const UInt8 *& match, const size_t offset)
 {
    /// 4 % n.
    /// Or if 4 % n is zero, we use n.
    /// It gives equivalent result, but is better CPU friendly for unknown reason.
    static constexpr int shift1[] = { 0, 1, 2, 1, 4, 4, 4, 4 };

    /// 8 % n - 4 % n
    static constexpr int shift2[] = { 0, 0, 0, 1, 0, -1, -2, -3 };

    op[0] = match[0];
    op[1] = match[1];
    op[2] = match[2];
    op[3] = match[3];

    match += shift1[offset];
    memcpy(op + 4, match, 4);
    match += shift2[offset];
 }} 

, , . , , — 16 .

« » , ( offset < 16 , offset < 8 ). () 16- :

 inline void copyOverlap16(UInt8 * op, const UInt8 *& match, const size_t offset)
 {
    /// 4 % n.
    static constexpr int shift1[]
        = { 0, 1, 2, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 };

    /// 8 % n - 4 % n
    static constexpr int shift2[]
        = { 0, 0, 0, 1, 0, -1, -2, -3, -4, 4, 4, 4, 4, 4, 4, 4 };

    /// 16 % n - 8 % n
    static constexpr int shift3[]
        = { 0, 0, 0, -1, 0, -2, 2, 1, 8, -1, -2, -3, -4, -5, -6, -7 };

    op[0] = match[0];
    op[1] = match[1];
    op[2] = match[2];
    op[3] = match[3];

    match += shift1[offset];
    memcpy(op + 4, match, 4);
    match += shift2[offset];
    memcpy(op + 8, match, 8);
    match += shift3[offset];
 }} 

? , SIMD-, 16 , ( 1 15). , , .

— pshufb ( packed shuffle bytes) SSSE3 ( S). 16- . . — «»: 0 15 — , . , 127 — .

Hier ist ein Beispiel:

 xmm0: abc.............
xmm1: 0120120120120120

pshufb %xmm1, %xmm0

xmm0: abcabcabcabcabca 

— ! :

 inline void copyOverlap16Shuffle(UInt8 * op, const UInt8 *& match, const size_t offset)
 {
#ifdef __SSSE3__

    static constexpr UInt8 __attribute__((__aligned__(16))) masks[] =
     {
        0, 1, 2, 1, 4, 1, 4, 2, 8, 7, 6, 5, 4, 3, 2, 1, /* offset = 0, not used as mask, but for shift amount instead */
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* offset = 1 */
        0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
        0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0,
        0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,
        0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1,
        0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0, 1,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0,
     };

    _mm_storeu_si128(reinterpret_cast<__m128i *>(op),
        _mm_shuffle_epi8(
            _mm_loadu_si128(reinterpret_cast<const __m128i *>(match)),
            _mm_load_si128(reinterpret_cast<const __m128i *>(masks) + offset)));

    match += masks[offset];

#else
    copyOverlap16(op, match, offset);
 #endif
 }} 

_mm_shuffle_epi8 — intrinsic , pshufb .

, ? SSSE3 — , 2006 . AVX2 , 32 , 16- . packed shuffle bytes, vector permute bytes — , . AVX-512 VBMI , 64 , . ARM NEON — vtbl (vector table lookup), 8 .

, pshufb 64- MMX-, 8 . . , , 16 ( ).

Highload++ Siberia , 8 ( ) — !

if

, , 16 . ?

, . , , , . , .

, . , , , 65 536 . 65 536 . , , 65 551 . , , 96 128 — . , «» mmap ( madvice). - page faults. , .

?

, , :

1. 16 8.
2. shuffle- offset < 16 .
3. if.

.

Beispiel 1:
Xeon E2650v2, ., AppVersion.
reference: 1.67 GB/sec.
16 bytes, shuffle: 2.94 GB/sec ( 76% ).

Beispiel 2:
Xeon E2650v2, ., ShowsSumPosition.
reference: 2.30 GB/sec.
16 bytes, shuffle: 1.91 GB/sec ( 20% ).

, . , . - , . , . — 16 . : , , .

, C++ : 8- 16- ; shuffle-.

 template <size_t copy_amount, bool use_shuffle>
void NO_INLINE decompressImpl(
     const char * const source,
     char * const dest,
     size_t dest_size) 

, shuffle . , :

 sudo echo 'performance' | tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
kill -STOP $(pidof firefox) $(pidof chromium) 

«» (c Xeon E5645), , . , , . , shuffle-, , 16- .

:

 sudo kill -STOP $(pidof python) $(pidof perl) $(pgrep -u skynet) $(pidof cqudp-client) 

. thermal throttling power capping.

, , . , , . . , , . : ClickHouse , , . , ( — ?). .

, , . « » . , , , .

, . . - . — ClickHouse 64 . ( .)

, « », , . , , , - . . , , . .

, , . «» , . , . Thompson Sampling.

, , . — : , . . , . , C++. — , - , ; .

? , . . -, , . -, , , «» .

, , Thompson Sampling — ( , ). , , - , , . , .

, «» . , , «», . — . , , .

, , , , «»:

 /// For better convergence, we don't use proper estimate of stddev.
/// We want to eventually separate between two algorithms even in case
/// when there is no statistical significant difference between them.
double sigma() const
 {
    return mean() / sqrt(adjustedCount());
 }}

double sample(pcg64 & rng) const
 {
     ...
    return std::normal_distribution<>(mean(), sigma())(rng);
 }} 

, — memory latencies.

, , — LZ4 .

, :
— reference (baseline): LZ4 ;
— variant 0: 8 , shuffle;
— variant 1: 8 , shuffle;
— variant 2: 16 , shuffle;
— variant 3: 16 , shuffle;
— «» , .

CPU

CPU, , . , CPU ?

ClickHouse , 256 100 ( 256 ). , CPU , . CPU:
— Intel® Xeon® CPU E5-2650 v2 @ 2.60GHz
— Intel® Xeon® CPU E5-2660 v4 @ 2.00GHz
— Intel® Xeon® CPU E5-2660 0 @ 2.20GHz
— Intel® Xeon® CPU E5645 @ 2.40GHz
— Intel Xeon E312xx (Sandy Bridge)
— AMD Opteron(TM) Processor 6274
— AMD Opteron(tm) Processor 6380
— Intel® Xeon® CPU E5-2683 v4 @ 2.10GHz
— Intel® Xeon® CPU E5530 @ 2.40GHz
— Intel® Xeon® CPU E5440 @ 2.83GHz
— Intel® Xeon® CPU E5-2667 v2 @ 3.30GHz

— , R&D:
— AMD EPYC 7351 16-Core Processor — AMD.
— Cavium ThunderX2 — x86, AArch64. SIMD- . 224 56 .

13 , 256 6 (reference, 0, 1, 2, 3, adaptive), 10 , . 199 680 , .

, CPU . : LZ4 ( — ). , Cavium . ClickHouse, «» Xeon E5-2650 v2 , , ClickHouse x86.

 ┌─cpu───────────────────┬──ref─┬─adapt─┬──max─┬─best─┬─adapt_boost─┬─max_boost─┬─adapt_over_max─┐
│ E5-2667 v2 @ 3.30GHz │ 2.81 │ 3.19 │ 3.15 │ 3 │ 1.14 │ 1.12 │ 1.01 │
│ E5-2650 v2 @ 2.60GHz │ 2.5 │ 2.84 │ 2.81 │ 3 │ 1.14 │ 1.12 │ 1.01 │
│ E5-2683 v4 @ 2.10GHz │ 2.26 │ 2.63 │ 2.59 │ 3 │ 1.16 │ 1.15 │ 1.02 │
│ E5-2660 v4 @ 2.00GHz │ 2.15 │ 2.49 │ 2.46 │ 3 │ 1.16 │ 1.14 │ 1.01 │
│ AMD EPYC 7351 │ 2.03 │ 2.44 │ 2.35 │ 3 │ 1.20 │ 1.16 │ 1.04 │
│ E5-2660 0 @ 2.20GHz │ 2.13 │ 2.39 │ 2.37 │ 3 │ 1.12 │ 1.11 │ 1.01 │
│ E312xx (Sandy Bridge) │ 1.97 │ 2.2 │ 2.18 │ 3 │ 1.12 │ 1.11 │ 1.01 │
│ E5530 @ 2.40GHz │ 1.65 │ 1.93 │ 1.94 │ 3 │ 1.17 │ 1.18 │ 0.99 │
│ E5645 @ 2.40GHz │ 1.65 │ 1.92 │ 1.94 │ 3 │ 1.16 │ 1.18 │ 0.99 │
│ AMD Opteron 6380 │ 1.47 │ 1.58 │ 1.56 │ 1 │ 1.07 │ 1.06 │ 1.01 │
│ AMD Opteron 6274 │ 1.15 │ 1.35 │ 1.35 │ 1 │ 1.17 │ 1.17 │ 1 │
│ E5440 @ 2.83GHz │ 1.35 │ 1.33 │ 1.42 │ 1 │ 0.99 │ 1.05 │ 0.94 │
│ Cavium ThunderX2 │ 0.84 │ 0.87 │ 0.87 │ 0 │ 1.04 │ 1.04 │ 1 │
└───────────────────────┴──────┴───────┴──────┴──────┴─────────────┴───────────┴────────────────┘ 

ref, adapt, max — (, ). best — , 0 3. adapt_boost — baseline. max_boost — baseline. adapt_over_max — .

, x86 12–20%. ARM 4%, , . , «» Intel.

Schlussfolgerungen

. , LZ4 12–20%, . . , .

, , «» , ZStandard level 1 LZ4: IO .

— , . , .

: . LZ4 , Lizard, Density LZSSE , . , LZ4 LZSSE ClickHouse.

LZ4 : . : , . . , inc- dec- . , 12–15% 32 , 16, . 32 — , .

, , page cache userspace ( mmap, O_DIRECT userspace page cache — ), - ( CityHash128 CRC32-C, HighwayHash, FARSH XXH3). , .

, master, . HighLoad++ Siberia, .