La preuve par le graphique

Dans un précédent billet, nous avons vu que le meilleur principe pour accélérer les recherches est de chaîner les bonnes positions, que la meilleure façon de créer des chaînes est de les indicer par un Hash. Enfin nous avons vu que, pour éviter des tests inutiles, mieux vaut que les chaînes ne tracent qu'un seul préfixe, ce qui statistiquement est à peu près résolu en utilisant des Hash suffisamment grands.
Toute ceci était très qualitatif, mais mieux vaut un bon graphique pour mettre les points sur les i.

Je me suis employé à produire un compresseur à recherche complète, sur la base de LZ4. Le résultat est d'ailleurs totalement compatible avec LZ4, la principale différence étant la vitesse de compression, le nouveau programme faisant une recherche exhaustive, qui par conséquent garanti le meilleur résultat possible ... pour un temps beaucoup plus long.

Afin de tester l'impact sur les performances, j'ai mesuré le nombre moyen de comparaisons par recherche, en fonction de la taille de la table de hash. Un graphique valant souvent mieux qu'un long discours, voici les résultats :


Pour une fois, c'est totalement conforme aux prévisions : le nombre de comparaisons par recherche diminue drastiquement en augmentant la taille de la table de hash. Puis, lorsqu'on s'approche de la taille de la fenêtre de recherche (16 bits dans ce cas), les gains deviennent de plus en plus faibles, jusqu'à devenir totalement négligeables.

De fait, on tend vers une limite, qui dépend du fichier à compresser.
Sur des binaires, le nombre moyen de comparaisons reste très important, probablement en raison de l'existence de grandes zones uniformes (telle qu'une longue série de zéros). Même sur un cas favorable comme Enwik8, qui ne contient que du texte, ce nombre de comparaisons reste élevé : 27 par recherche, et ce n'est que 64K ! Pour donner un ordre d'idées, cette version est environ 8 fois plus lente que LZ4. Pour Calgary, c'est pire : 50 fois plus lent !

On converge vers une limite parce qu'il n'y a pratiquement plus de collisions; toutes les comparaisons sont en fait valides, elles ont toutes un bon préfixe.

Poussant l'exercice un peu plus loin, regardons ce que ça donne avec une fenêtre de recherche un peu plus grande : 512Ko.



On constate le même comportement. Les valeurs convergent vers une limite, qui est d'ailleurs atteinte avant les 512K combinaisons (correspondant à 19 bits), sans doute parce qu'il n'y a pas tant de combinaisons différentes que cela.
Toutefois, ce qui doit attirer l'attention, ce sont les valeurs absolues : elles sont gigantesques. Mille comparaisons par recherche, il va de soit que ça pèse extrêmement lourd, et que la vitesse de compression s'en ressent. Ainsi, il faut 26 secondes pour compresser Calgary, qui ne fait pourtant que 3,5 Mo.
C'est très lent, et nous ne sommes qu'à 512 Ko. C'est illustratif de ce qui nous attend pour des recherches sur des profondeurs sérieuses, comme plusieurs dizaines voire centaines de mega octets.

Il faut donc une autre méthode, pour chercher loin, mais vite...