Comment accélérer le déchargement de LZ4 dans ClickHouse

Lors de l'exécution de requêtes dans ClickHouse, vous pouvez remarquer que dans le profileur, à l'un des premiers endroits, la fonction LZ_decompress_fast est souvent visible. Pourquoi cela se produit-il? Cette question est devenue la raison de toute l'étude sur le choix du meilleur algorithme de décompression. Ici, je publie l'étude entière, et la version courte peut être trouvée dans mon rapport sur HighLoad ++ Siberia.

Les données ClickHouse sont stockées sous forme compressée. Et pendant l'exécution des requêtes, ClickHouse essaie de ne rien faire - utiliser un minimum de ressources CPU. Il arrive que tous les calculs qui pourraient prendre un certain temps soient déjà bien optimisés, et la requête est bien écrite par l'utilisateur. Reste alors à effectuer la libération.



La question est, pourquoi la version LZ4 peut-elle être un goulot d'étranglement? Il semblerait que LZ4 soit un algorithme très léger : le taux de compression, selon les données, varie généralement de 1 à 3 Go / s par cœur de processeur. C'est bien plus que la vitesse du sous-système de disque. De plus, nous utilisons tous les noyaux disponibles et l'expansion évolue linéairement sur tous les noyaux physiques.

Mais il y a deux points à garder à l'esprit. Premièrement, les données compressées sont lues à partir du disque et le taux de compression est donné en quantité de données non compressées. Si le taux de compression est suffisamment grand, alors presque rien ne doit être lu sur les disques. Mais en même temps, beaucoup de données compressées sont générées, et bien sûr, cela affecte la consommation du processeur: la quantité de travail de compression de données dans le cas de LZ4 est presque proportionnelle au volume des données compressées lui-même.

Deuxièmement, la lecture des données à partir des disques peut ne pas être nécessaire du tout si les données sont dans le cache. Pour ce faire, vous pouvez compter sur le cache de pages ou utiliser votre propre cache. Dans une base de données de colonnes, l'utilisation du cache est plus efficace car toutes les colonnes n'y entrent pas, mais seulement celles fréquemment utilisées. C'est pourquoi LZ4, en termes de charge CPU, est souvent un goulot d'étranglement.

D'où deux autres questions. Si la compression des données "ralentit", alors peut-être qu'elles ne devraient pas du tout être compressées? Mais en pratique, cette hypothèse n'a pas de sens. Récemment, dans ClickHouse, il n'a été possible de configurer que deux options de compression de données - LZ4 et Zstandard . La valeur par défaut est LZ4. En passant à Zstandard, vous pouvez rendre la compression plus forte et plus lente. Mais il était impossible de désactiver complètement la compression jusqu'à récemment - LZ4 est considéré comme un minimum raisonnable, qui peut toujours être utilisé. C'est pourquoi j'aime vraiment le LZ4. :)

Mais récemment, un mystérieux inconnu est apparu dans le chat de discussion anglophone ClickHouse, qui a dit qu'il avait un sous-système de disque très rapide (NVMe SSD) et que tout dépend de la compression - ce serait bien de pouvoir le désactiver. J'ai répondu qu'il n'y a pas une telle possibilité, mais c'est facile à ajouter. Quelques jours plus tard, nous avons reçu une demande de pool , qui implémente la méthode de compression none . J'ai demandé les résultats - combien cela a aidé, la rapidité des demandes. La personne a déclaré que cette nouvelle fonctionnalité s'est avérée inutile dans la pratique, car les données sans compression ont commencé à prendre trop de place.

La deuxième question qui se pose est: s'il y a un cache, pourquoi ne pas y stocker les données déjà non compressées? Ceci est autorisé - dans de nombreux cas, il sera possible de se débarrasser du besoin de décompression. Et dans ClickHouse, il existe un tel cache - un cache de blocs étendus . Mais c'est dommage d'y consacrer beaucoup de RAM à cause de sa faible efficacité. Il ne se justifie que sur de petites requêtes consécutives qui utilisent presque les mêmes données.

Considération générale: les données doivent être compressées, de préférence toujours. Gravez-les toujours sur un disque compressé. Transmettez sur le réseau également avec compression. À mon avis, la compression par défaut doit être considérée comme justifiée même lors du transfert vers un réseau de 10 gigabits sans surabonnement dans le centre de données, et le transfert de données sans compression entre les centres de données est généralement inacceptable.

Pourquoi LZ4?

Pourquoi LZ4 est-il utilisé? Est-il possible de choisir quelque chose de plus simple encore? En principe, c'est possible, c'est juste et utile. Mais regardons d'abord à quelle classe d'algorithmes appartient LZ4.

Premièrement, cela ne dépend pas du type de données. Par exemple, si vous savez à l'avance que vous disposerez d'un tableau d'entiers, vous pouvez utiliser l'une des nombreuses variantes de l'algorithme VarInt - il sera plus efficace sur le CPU. Deuxièmement, LZ4 ne dépend pas trop des hypothèses requises sur le modèle de données. Supposons que vous ayez une série chronologique ordonnée de lectures de capteur - un tableau avec des nombres de type float. Ensuite, vous pouvez calculer les deltas, puis compresser davantage, ce qui sera plus efficace en termes de taux de compression.

Autrement dit, LZ4 peut être utilisé sans problème pour tous les tableaux d'octets - pour tous les fichiers. Bien sûr, il a sa propre spécialisation (plus de détails ci-dessous), et dans certains cas, son utilisation n'a pas de sens. Mais si vous l'appelez un algorithme à usage général, ce sera une petite erreur. Et notez que, grâce au dispositif interne, LZ4 implémente automatiquement l'algorithme RLE comme cas particulier.

Autre question: LZ4 est-il l'algorithme le plus optimal de cette classe pour la combinaison de la vitesse et de la force de compression? De tels algorithmes sont appelés pareto frontier - cela signifie qu'aucun autre algorithme n'est strictement meilleur dans un indicateur et pas pire dans d'autres (et même sur une grande variété de jeux de données). Il existe des algorithmes plus rapides, mais qui donnent un taux de compression plus faible, et d'autres qui compressent plus, mais en même temps, compressent ou décompressent plus lentement.

En fait, le LZ4 n'est pas une frontière pareto. Il existe des options légèrement meilleures. Par exemple, c'est LZTURBO d'un certain powturbo . Il n'y a aucun doute sur la fiabilité des résultats grâce à la communauté sur encode.ru (le plus grand et approximativement le seul forum de compression de données). Mais le développeur ne distribue pas le code source ou les binaires, mais ne les donne qu'à un cercle restreint de personnes pour des tests ou pour beaucoup d'argent (comme personne n'a payé jusqu'à présent). Il convient également de prêter attention au lézard (anciennement LZ5) et à la densité . Ils peuvent fonctionner un peu mieux que LZ4 lors du choix d'un niveau de compression. Faites également attention à LZSSE - une chose extrêmement intéressante. Cependant, il vaut mieux le regarder après avoir lu cet article.

Comment fonctionne LZ4?

Voyons comment fonctionne LZ4 en général. C'est l'une des implémentations de l'algorithme LZ77: L et Z indiquent les noms des auteurs (Lempel et Ziv), et 77 - en 1977, lorsque l'algorithme a été publié. Il a de nombreuses autres implémentations: QuickLZ, FastLZ, BriefLZ, LZF, LZO, ainsi que gzip et zip lors de l'utilisation de faibles niveaux de compression.

Un bloc de données compressé à l'aide de LZ4 contient une séquence d'enregistrements (commandes, instructions) de deux types:

1. Littéral: "prenez les N octets suivants tels quels et copiez-les dans le résultat."
2. Match (match): "prendre N octets qui ont déjà été décompressés par le décalage de décalage par rapport à la position actuelle."

Un exemple. Avant la compression:
Hello world Hello

Après compression:
literals 12 "Hello world " match 5 12

Si nous prenons un bloc compressé et le parcourons avec le curseur, en exécutant ces commandes, nous obtiendrons les données initiales non compressées en conséquence.

Nous avons examiné en gros comment les données sont décompressées. Le point est également clair: pour effectuer la compression, l'algorithme code des séquences d'octets répétitives à l'aide de correspondances.

Clair et quelques propriétés. Cet algorithme est orienté octet - il ne dissèque pas les octets individuels, mais les copie uniquement dans son intégralité. C'est là que réside, par exemple, la différence avec le codage entropique. Par exemple, zstd est une composition de LZ77 et de codage entropique.

Notez que la taille du bloc compressé n'est pas choisie trop grande pour ne pas dépenser beaucoup de RAM lors du déchargement; afin de ne pas ralentir l'accès aléatoire dans un fichier compressé (composé de nombreux blocs compressés); et parfois pour que le bloc tienne dans un cache CPU. Par exemple, vous pouvez choisir 64 Ko - de sorte que les tampons pour les données compressées et non compressées tiendront dans le cache L2 et la moitié restera.

Si nous devons compresser un fichier plus volumineux, nous allons simplement concaténer les blocs compressés. En même temps, à côté de chaque bloc compressé, il est pratique de placer des données supplémentaires - tailles, somme de contrôle.

Le décalage maximum pour la correspondance est limité, en LZ4 - 64 kilo-octets. Cette valeur est appelée une fenêtre coulissante. En effet, cela signifie qu'au fur et à mesure que le curseur avance, les correspondances peuvent se trouver dans une fenêtre de 64 kilo-octets par rapport au curseur, qui se déplace avec le curseur.

Voyons maintenant comment compresser les données - en d'autres termes, comment trouver les séquences correspondantes dans un fichier. Bien sûr, vous pouvez utiliser le suffixe trie (idéal si vous en avez entendu parler). Il existe des options dans lesquelles la séquence de correspondance la plus longue est garantie d'être parmi les octets précédents dans le processus de compression. C'est ce qu'on appelle l'analyse optimale et donne un taux de compression presque meilleur pour un format de bloc compressé fixe. Mais il existe des options plus efficaces - lorsque nous trouvons une correspondance suffisamment bonne dans les données, mais pas nécessairement la plus longue. Le moyen le plus efficace de le trouver est d'utiliser une table de hachage.

Pour ce faire, nous parcourons le bloc de données source avec le curseur et prenons quelques octets après le curseur. Par exemple, 4 octets. Les hacher et mettre dans la table de hachage le décalage depuis le début du bloc - où ces 4 octets se sont rencontrés. La valeur 4 est appelée min-match - à l'aide d'une telle table de hachage, nous pouvons trouver des correspondances d'au moins 4 octets.

Si nous avons regardé la table de hachage, et qu'il y a déjà un enregistrement là-bas, et si l'offset ne dépasse pas la fenêtre glissante, alors nous vérifions combien d'octets supplémentaires correspondent après ces quatre octets. Il y a peut-être beaucoup plus qui coïncident. Il est également possible qu'une collision se soit produite dans la table de hachage et que rien ne corresponde. C'est normal - vous pouvez simplement remplacer la valeur de la table de hachage par une nouvelle. Les collisions dans la table de hachage entraîneront simplement un taux de compression plus faible car il y a moins de correspondances. Soit dit en passant, ce type de table de hachage (de taille fixe et sans résolution de collision) est appelé table de cache, une table de cache. Cela est également logique - en cas de collision, la table de cache oublie simplement l'ancien enregistrement.

La tâche du lecteur attentif. Soit les données un tableau de nombres comme UInt32 en petit format endian, qui fait partie d'une séquence de nombres naturels: 0, 1, 2 ... Expliquez pourquoi lorsque vous utilisez LZ4 ces données ne sont pas compressées (la quantité de données compressées n'est pas inférieure à la quantité de données non compressées).

Comment accélérer les choses

Donc, je veux accélérer le déchargement de LZ4. Voyons à quoi ressemble le cycle de déchargement. Voici la boucle en pseudocode:

  tandis que (...)
 {
     lire (input_pos, literal_length, match_length);

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

     lecture (input_pos, match_offset);

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

Le format LZ4 est conçu pour que les littéraux et les correspondances alternent dans un fichier compressé. Et évidemment, le littéral vient toujours en premier (car depuis le tout début, le match n'a nulle part où aller). Par conséquent, leurs longueurs sont codées ensemble.

En fait, tout est un peu plus compliqué. Un octet est lu dans le fichier et deux quartets sont extraits de celui-ci, dans lesquels les nombres de 0 à 15. sont codés. Si le nombre correspondant n'est pas égal à 15, alors il est considéré comme la longueur du littéral et de la correspondance, respectivement. Et si c'est 15, alors la longueur est plus longue et elle est codée dans les octets suivants. Ensuite, l'octet suivant est lu et sa valeur est ajoutée à la longueur. De plus, s'il est égal à 255, alors nous continuons - nous lisons l'octet suivant de la même manière.

Notez que le taux de compression maximum pour le format LZ4 n'atteint pas 255. Et la deuxième observation (inutile): si vos données sont très redondantes, alors l'utilisation de LZ4 augmentera le taux de compression doubler.

Lorsque nous lisons la longueur du littéral (puis aussi la longueur de la correspondance et le décalage de la correspondance), pour desserrer il suffit de copier simplement deux morceaux de mémoire.

Comment copier un morceau de mémoire

Il semblerait que vous pouvez utiliser la fonction memcpy , qui est juste conçue pour copier des morceaux de mémoire. Mais ce n'est pas optimal et toujours incorrect.

Pourquoi l'utilisation de la fonction memcpy n'est-elle pas optimale? Parce qu'elle:

1. généralement situé dans la bibliothèque libc (et la bibliothèque libc est généralement liée dynamiquement, et l'appel memcpy ira indirectement, via PLT),
2. pas en ligne avec l'argument taille inconnu au moment de la compilation,
3. fait beaucoup d'efforts pour traiter correctement les «queues» d'un fragment de mémoire qui ne sont pas multiples de la taille d'un mot machine ou d'un registre.

Le dernier point est le plus important. Supposons que nous ayons demandé à la fonction memcpy de copier exactement 5 octets. Il serait très bien de copier 8 octets à la fois, en utilisant deux instructions movq pour cela.

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

Mais ensuite, nous allons copier trois octets supplémentaires - c'est-à-dire que nous allons écrire à l'étranger le tampon transféré. La fonction memcpy n'a pas le droit de le faire - en effet, parce que nous allons écraser certaines données dans notre programme, il y aura un «passage» de la mémoire. Et si nous avons écrit à une adresse non alignée, ces octets supplémentaires peuvent être situés sur une page de mémoire virtuelle non allouée ou sur une page sans accès en écriture. Ensuite, nous obtenons un défaut de segmentation (c'est bien).

Mais dans notre cas, nous pouvons presque toujours écrire des octets supplémentaires. Nous pouvons lire des octets supplémentaires dans le tampon d'entrée tant que les octets supplémentaires s'y trouvent entièrement. Dans les mêmes conditions, nous pouvons écrire des octets supplémentaires dans le tampon de sortie - car à la prochaine itération, nous les remplacerons de toute façon.

Cette optimisation est déjà dans l'implémentation LZ4 d'origine:

  inline void copy8 (UInt8 * dst, const UInt8 * src)
 {
     memcpy (dst, src, 8);  /// En fait, memcpy n'est pas appelé ici.
 }

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

Pour profiter de cette optimisation, il suffit de vérifier que l'on est assez loin de la frontière du buffer. Cela devrait être gratuit, car nous vérifions déjà que les limites de tampon sont dépassées. Et le traitement des derniers octets - la "queue" des données - peut se faire après la boucle principale.

Cependant, il y a encore quelques subtilités. Il y a deux exemplaires dans le cycle - littéral et match. Mais lorsque vous utilisez la fonction LZ4_decompress_fast (au lieu de LZ4_decompress_safe), la vérification est effectuée une fois - lorsque nous devons copier le littéral. Lors de la copie d'une correspondance, la vérification n'est pas effectuée, mais dans la spécification du format LZ4, il existe des conditions qui permettent de l'éviter:

Les 5 derniers octets sont toujours des littéraux
La dernière correspondance doit commencer au moins 12 octets avant la fin du bloc.
Par conséquent, un bloc de moins de 13 octets ne peut pas être compressé.

Des données d'entrée spécialement sélectionnées peuvent provoquer un lecteur de mémoire. Si vous utilisez la fonction LZ4_decompress_fast, vous avez besoin d'une protection contre les données incorrectes. Les données compressées doivent être au moins une somme de contrôle. Et si vous avez besoin d'une protection contre un attaquant, utilisez la fonction LZ4_decompress_safe. Autres options: prenez une fonction de hachage cryptographique comme somme de contrôle, mais cela tuera presque certainement toutes les performances; soit allouer plus de mémoire aux tampons; allouez de la mémoire aux tampons avec un appel distinct à mmap et créez une page de garde.

Quand je vois un code qui copie des données de 8 octets, je demande immédiatement - pourquoi exactement 8 octets? Vous pouvez copier 16 octets à l'aide des registres SSE:

  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)
 {
     faire
     {
         copy16 (dst, src);
         dst + = 16;
         src + = 16;
     } while (dst <dst_end);
 } 

La copie de 32 octets pour AVX et de 64 octets pour AVX-512 fonctionne de manière similaire. De plus, vous pouvez étendre le cycle plusieurs fois. Si vous avez déjà regardé comment memcpy , c'est exactement l'approche. (Soit dit en passant, le compilateur dans ce cas ne développera ni ne vectorisera la boucle: cela nécessitera l'insertion de vérifications lourdes.)

Pourquoi cela n'est-il pas fait dans l'implémentation LZ4 d'origine? Premièrement, il n'est pas évident que ce soit meilleur ou pire. Le résultat dépend de la taille des fragments qui doivent être copiés. Soudain, ils sont tous courts et le travail supplémentaire sera inutile? Et deuxièmement, il détruit ces conditions au format LZ4 qui vous permettent d'éviter les brunchs inutiles dans la boucle intérieure.

Néanmoins, nous garderons cette option à l'esprit pour l'instant.

Copie délicate

Retour à la question - est-il toujours possible de copier des données de cette façon? Supposons que nous ayons besoin de copier une correspondance, c'est-à-dire de copier un morceau de mémoire du tampon de sortie qui est à un certain décalage derrière le curseur à la position de ce curseur.

Imaginez un cas simple - vous devez copier 5 octets à l'offset 12:

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

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

Mais il y a un cas plus compliqué - quand nous devons copier un morceau de mémoire dont la longueur est supérieure au décalage. C'est-à-dire qu'il indique partiellement des données qui n'ont pas encore été écrites dans le tampon de sortie.

Copiez 10 octets à l'offset 3:

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

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

Dans le processus de compression, nous avons toutes les données, et une telle correspondance peut très bien être trouvée. La fonction memcpy ne convient pas pour la copier: elle ne prend pas en charge le cas où les plages de fragments de mémoire se croisent. Soit dit en passant, la fonction memmove ne convient pas non plus, car le fragment de mémoire d'où obtenir les données n'est pas encore complètement initialisé. Vous devez copier comme si nous copions par octet.

  op [0] = correspond à [0];
 op [1] = correspond à [1];
 op [2] = correspond à [2];
 op [3] = correspond à [3];
 ... 

Voici comment cela fonctionne:

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

Autrement dit, nous devons créer une séquence répétitive. Dans l'implémentation LZ4 d'origine, un code étonnamment incompréhensible a été écrit pour cela:

  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] = correspond à [0];
 op [1] = correspond à [1];
 op [2] = correspond à [2];
 op [3] = correspond à [3];
 match + = dec32table [offset];
 memcpy (op + 4, match, 4);
 match - = dec64; 

Nous copions les 4 premiers octets octet par bit, décalons d'un certain nombre magique, copions les 4 octets suivants dans leur ensemble, décalons le pointeur pour qu'il corresponde à un autre nombre magique. L'auteur du code ( Jan Collet ), pour une raison ridicule, a oublié de laisser un commentaire sur ce que cela signifie. De plus, les noms de variables prêtent à confusion. Les deux s'appellent dec ... table, mais nous ajoutons l'un d'eux et soustrayons l'autre. De plus, un autre n'est pas signé et l'autre est int. Cependant, il vaut la peine de rendre hommage: tout récemment, l'auteur a amélioré cette place dans le code.

Voici comment cela fonctionne réellement. Copiez les 4 premiers octets:

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

Vous pouvez maintenant copier 4 octets à la fois:

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

Vous pouvez continuer comme d'habitude en copiant 8 octets à la fois:

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

, — . :

 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 — .

Voici un exemple:

 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.

.

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

Exemple 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.

. , 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, .