Exporter directement au format Git-pack

Seb35 commented 6 years ago

Sur le conseil d’Emmanuel Raviart, il serait intéressant d’enregistrer directement au format Git-pack sans passer par le binaire Git. Cf la librairie Dulwich qui document le format Git-pack.

Seb35 commented 6 years ago

Cf aussi les commentaires de @fgallaire et @Changaco sur #32.

Seb35 commented 6 years ago

Je viens d’explorer les packfiles et de réussir à en créer un avec son index, avec dulwich. Voici mon exemple jouet :

import dulwich.objects, dulwich.pack
with open( '/bin/sh', 'rb' ) as f:
    t1 = f.read()
t2 = t1 + b'1984'
o1 = dulwich.objects.ShaFile.from_raw_string(3, t1)
o2 = dulwich.objects.ShaFile.from_raw_string(3, t2)
deltas = list(dulwich.pack.deltify_pack_objects([(o1, ''), (o2, '')]))
with open('sh.pack', 'wb') as pack:
    entries, shapack = dulwich.pack.write_pack_data(pack, len(deltas), deltas)
entries = sorted([(k, v[0], v[1]) for (k, v) in entries.items()])
with open('sh.idx', 'wb') as idx:
    dulwich.pack.write_pack_index_v2(idx, entries, shapack)

La création de l’index peut aussi se faire en shell avec

git index-pack -o sh.idx sh.pack
git verify-pack -f sh.idx

Outre les trois fonctions de deltification et d’écriture des pack et index, la ligne intermédiaire de tri des entrées avant l’écriture de l’index provient de dulwich.pack.write_pack ~~mais celle-ci trie dans l’ordre naturel (lexicographique) alors qu’il faut trier selon l’offset du fichier pack (la 2e colonne)~~ [EDIT: erreur de ma part, j’ai dû me mélanger]. Si cet ordre est mauvais, le binaire git-verify-pack renvoit error: non-monotonic index test.idx et refuse d’afficher le contenu de l’index, ou bien affiche le contenu et affiche une erreur sur le checksum de l’index fatal: sha1 file 'sh.idx' validation error (je ne comprend pas pourquoi plusieurs erreurs différentes).

Seb35 commented 6 years ago

En revanche, au niveau de la vitesse, c’est pas extraordinaire avec l’exemple ci-dessus (le binaire /bin/sh qui pèse 125 Kio chez moi, et le même auquel on rajoute 2 octets), ça a mis 24 secondes en Python (IO non-compris car tout reste en mémoire) – proc bicœur à 1,7 GHz, 4 Gio de RAM, disque mécanique – alors que le binaire Git a mis 2,3 secondes (en utilisant 4 threads, IO compris). Ultimement, c’est difflib.SequenceMatcher qui fait le job avec dulwich, et je pense pas qu’on puisse réellement optimiser autre chose, le code autour est du traitement.

Ce test de performance me rend assez pessimiste sur le réel gain de performance possible, du moins dans une approche simpliste de remplacer le binaire Git par une librairie Python ou même C. Le seul endroit où je vois une possible optimisation technique est de conserver en mémoire les objets Git, de périodiquement les deltifier pour conserver une faible empreinte mémoire (d’ailleurs je ferais un peu différemment dans l’algo dulwich.pack.deltify_pack_objects (*), du moins dans le cas particulier d’Archéo Lex) et de n’écrire le pack et son index qu’à la fin.

Cette optimisation technique me semble être un pré-requis pour (avoir une chance d’) améliorer la performance. En plus de cela, et étant donné que ce qui prend le plus de complexité est l’algo de différences, je pense qu’il serait judicieux de tirer parti du cache de sections (#32) qui est en soit du travail prémâché pour cet algo de différences dans le cas particulier de 2 versions consécutives : cela donne de larges parts de texte qui sont structurellement identiques jusqu’au niveau de l’article. On peut ensuite faire tourner l’algo de différences sur les parties restantes pour compresser au niveau sub-article. Quoique la complexité intrinsèque ne va pas diminuer, on exécutera cet algo au niveau des articles au lieu du texte, ce qui est l’ordre de grandeur en-dessous, et vu la complexité de l’algo (quadratique en moyenne et cubique au pire d’après https://docs.python.org/3/library/difflib.html) ça me semble valable d’essayer. Avec les mains je fais l’hypothèse que (gros texte)^2 << n * (petits textes)^2 où n est le nombre d’articles modifiés. J’avoue, je n’ai pas tout de suite réalisé que ceci n’est valable que pour 2 versions consécutives, et plus les versions sont distantes plus le nombre de sections identiques diminuent et fragmente les deux textes, du coup à voir comment tirer parti de l’avantage sur 2 versions consécutives versus l’algorithme général.

(*) Optimisations/changments possibles (amha) de dulwich.pack.deltify_pack_objects, au moins dans le cas d’Archéo Lex (nombreux gros textes similaires) :

ne pas tenter de deltifier autre chose que les blobs, il n’y a quasiment pas de place à gagner et ça pollue la fenêtre des "bases possibles",
dans le cas d’articles dans des fichiers séparés, il faudrait configurer la fenêtre en tenant compte du nombre d’articles et idéalement avoir une fenêtre au moins du nombre d’articles. Par défaut git-gc a une fenêtre de 10 (clairement insuffisant au moins dans ce cas) et git-gc-aggressive 250 (ce que Archéo Lex appelle à la fin du calcul),
dans le cas d’un seul fichier, une fenêtre de grande dimension comme 250 me semble bien,
éventuellement tester d’autres algorithmes pour la fenêtre (actuellement FIFO) : LRU, LFU, LFU avec ancienneté (voir Wikipédia).

RouxRC commented 6 years ago

Juste au cas où, tu as testé avec pypy? On a des sacrées différences de perfs liées aux calculs de diff quand on l'utilise sur lawfactory-parser

Seb35 commented 6 years ago

Indeed, merci pour le conseil : 6 secondes pour l’exemple ci-dessus avec Pypy 2.4.0 (équivaut à Python 2.7.9), au lieu de 25 avec CPython et 2,3 avec le git officiel. Du coup ça ouvre la possibilité de réellement utiliser Python pour cette tâche.

Aussi, je corrige un truc que je disais plus haut (corrigé dans le post original), il ne semble finalement pas y avoir d’erreur dans write_pack, ça semble bien être juste une fonction sorted par ordre lexicographique, j’ai dû me planter dans mes expériences.

Legilibre / Archeo-Lex

Exporter directement au format Git-pack #51