Les Zeros

Il ne faut pas se fier à l'image de ce billet, pour le moins trompeuse . Non, nous n'allons pas parler des avions japonais, mais plutôt des suites de zeros, véritables tueurs de performance pour les recherches.

Pour comprendre ce qu'il se passe, décrivons d'abord le mécanisme avec une simple chaîne de hash.
Imaginons une suite de "zeros", qui peut être assez longue, disons une bonne centaine (ce qui est loin d'être énorme).
Toutes les positions de cette suite sont référencées dans la table comme faisant partie de la même chaîne, en général celle qui a pour hash zéro. Lors de la prochaine séquence minimale ne comportant que des zéros, toutes ces positions seront valides, et donc testées. Nous allons donc avoir une centaine de comparaisons, qui, en plus d'être nombreuses, sont potentiellement très longues (le temps de comparaison est proportionnel à la longueur du match).
Ensuite, chaque nouveau segment de zeros viendra s'ajouter à cette chaîne, rendant les futurs tests encore plus longs.

Au final, nous générons donc énormément de comparaisons très longues.

La chaîne de hash ne peut rien faire contre ce comportement, car il est totalement valable.
De fait, nous trouverons bien la meilleure combinaison possible, c'est juste que ce sera très long.

Dans le cas de l'algorithme MMC, le problème est hérité de la chaîne de hash. Il n'est que très partiellement contrebalancé par le mécanisme de promotion, mais avec une limite d'une seule promotion par passe (implémentation actuelle), le taux de diminution des comparaisons pour chaque passe est totalement insensible.

Pour traiter le problème, il est donc recommandé de fabriquer un mécanisme de recherche dédié. Celui-ci pourra traiter les segments entiers en une seule fois, limitant même les comparaisons à de simples calculs. Les performances sur ces situations seront donc grandement améliorées.

L'impact global sur les performances d'ensemble peut être très important, car les ralentissements de la recherche dans "LZ4 HC" sont complètement liés à ces longues suites de zeros.
J'attends donc de cette évolution un impact notable, que nous mesurerons dans un prochain billet.