Git

On the controversial topic of Version Control Systems (VCS), and for my own usage, I selected Git a few years ago after a subjective comparison. I would not say that I'm fanatic about it, as I keep an open mind, but undoubtedly, I have this preference. For simple cases, I easily grant that some other tools may be a bit more convenient. However, in complex situations, Git definitely shines, so far that I know.

Some friends are confronted to the same choices, and sometimes told me they are willing to take the chance they'll never need all that power. In my own experience, such situations arise once in a while, often enough that I like being better prepared for them.

One feature of Git picked my curiosity: its capacity to automatically discover almost identical files. One can rename a file and modify it, and Git will likely understand what happened. I found a few hints by reading about the pack compression algorithms. It also was pleasurable to discover a few Git niceties, like for this bisect enthusiasm.

Nowadays, good ideas spread around, and many good things from Git have also been implemented in other VCSes, so the advantages are no so clean-cut as they once were. Bazaar, in particular, went quite a long way improving its compression and speed, and adding features. While still behind Git in my opinion, it is at least usable by now, and that's quite a change!

• Code School - Try Git

From a French email to a friend — at a time I was barely starting with Git and still under the Wow! effect after having successfully used bisect and gitk.

C'est vraiment joli, je te partage ça dans l'enthousiasme. Le problème? J'ai fait une bonne série de modifications dans Pymacs, et je me rends compte que j'ai introduit un bug en cours de route. Un bug difficile, un problème de communication avec plein de compteurs et de références, du genre qu'on ne veut vraiment pas avoir. Mais quand est-ce que j'ai introduit le problème, et où se trouve-t-il?

Un peu de contexte… J'ai une série de versions déjà publiées pour Pymacs, numérotées de 0.0 jusqu'à 0.22. Je décide de passer à Git avant d'aborder le futur 0.23, et je place tout de 0.0 à 0.22 sur une branche master. Voulant être libre d'abandonner certaines modifications que je ne suis pas sûr de vouloir publier au moment futur du 0.23 officiel, je décide de laisser master tranquille pour le moment, dans le but de le refaire tout propre le moment venu. Alors, de 0.22, je bifurque le développement dans une branche combo, que je détruirai une fois 0.23 publié. Ce combo enregistre tout mon développement, dont en particulier, une nouvelle suite de validation — qui elle même est fragile et doit être mise au point. Comme ça commence à marcher assez bien, je retourne aux courriels de mes usagers et en jouant avec leurs suggestions, voilà que, patatras, je découvre qu'une fonctionnalité de base ne fonctionne plus du tout. Tout bloque, ça ne répond plus.

Pour m'aider à comprendre, puisque chaque test est compliqué à répéter, je me fabrique un script ./essai qui tout d'une fripe enlève l'ancien Pymacs, réinstalle le Pymacs courant, reproduit les conditions de l'essai et le déclenche. Si ça bloque, je le vois bien, le bug est là. Sinon, j'aurai les résultats et je saurai que le bug est corrigé.

Je retourne à 0.22, qui devrait fonctionner. Mais il ne fonctionne pas non plus, à cause d'un détail dans Python 2.5 qui brise Pymacs, mais que j'ai corrigé quelque part dans combo. Alors, puisque je ne veux pas toucher 0.22 directement, voilà une nouvelle branche essai à partir de 0.22 que je modifierai à loisir, qui devrait fonctionner rapidement. J'y consigne la correction des détails pour Python 2.5! Bon, enfin! Pymacs fonctionne correctement, au passé. À ce moment, j'ai à peu près:

0.0 - 0.1 - … 0.21 - 0.22 ← master
                      |
                      + o - o - o - o - o … o ← combo
                      |
                      + o ←/ essai

(les o représentent des vracs de corrections sans nom particulier).

Donc en bref, au bout de combo, c'est brisé, au bout de essai ça marche. Il faut trouver dans lequel o j'ai introduit le bug. Une dernière vérification, donc. Je suis sur combo au début des lignes qui suivent:

22:15:14 0 pinard@phenix:pymacs $ ./essai
[…]

[ça bloque]

22:17:54 130 pinard@phenix:pymacs $ git checkout essai && ./essai
[…]

[ça marche]

Et maintenant, la super-magie!

22:21:55 0 pinard@phenix:pymacs $ git checkout combo
Switched to branch "combo"

22:22:01 0 pinard@phenix:pymacs $ git bisect start

22:22:09 0 pinard@phenix:pymacs $ git bisect bad

22:22:12 0 pinard@phenix:pymacs $ git bisect good essai
Bisecting: 17 revisions left to test after this
[527731d45d[…]] Manual now in reST […]

22:22:47 0 pinard@phenix:pymacs $ ./essai
rm -f pymacs.el
[…]

[ça marche]

22:22:56 0 pinard@phenix:pymacs $ git bisect good
Bisecting: 8 revisions left to test after this
[87017fc9df[…]] Implement communication […]
22:23:00 0 pinard@phenix:pymacs $ ./essai
[…]

[ça marche]

22:23:04 0 pinard@phenix:pymacs $ git bisect good
Bisecting: 4 revisions left to test after this
[fc79f972e7[…]] Manual: Document the date […]

22:23:08 0 pinard@phenix:pymacs $ ./essai
[…]

[ça marche]

22:23:12 0 pinard@phenix:pymacs $ git bisect good
Bisecting: 2 revisions left to test after this
[63e71f222c[…]] pymacs.py: Changes to […]

22:23:15 0 pinard@phenix:pymacs $ ./essai
[…]

[ça bloque]

22:23:22 130 pinard@phenix:pymacs $ git bisect bad
Bisecting: 0 revisions left to test after this
[2c3c500044[…]] Tests: In the works

22:23:26 0 pinard@phenix:pymacs $ ./essai
[…]

[ça marche]

22:23:43 0 pinard@phenix:pymacs $ git bisect good
63e71f222c[…] is first bad commit
commit 63e71f222c[…]
Author: François Pinard <pinard@iro.umontreal.ca>
Date:   Thu Jan 31 20:47:23 2008 -0500

     pymacs.py: Changes to help tests, hopefully innocuous.

     Print strings the same way Emacs does.
     Quote generated expressions if asked to […]

040000 040000 ef4ec48f0d[…] 58836ba928[…] M      Pymacs

Tu vois, j'informe git bisect du résultat de mes tests, et lui, en conséquence, transforme automatiquement tous mes fichiers et mes répertoires en préparation du prochain test logique à faire. En bout du compte, j'obtiens le moment de la modification introduisant l'erreur, et ma propre description de ce que j'ai fait à ce moment-là. git diff peut me donner le grand détail pour exactement cette modification.

Remarque que le tout m'a pris un peu moins que deux minutes.

Imagine la puissance d'un tel outil lorsque, six mois ou un an après une publication, un usager me sort un bug non-trivial en disant: Pourtant, ça marchait dans telle version!.

Tout ce qui me reste à faire maintenant, c'est un git bisect reset pour faire un peu de ménage, parce pendant qu'il travaille, il ajoute une branche bisect et quelques o supplémentaires. Mais avant de faire ce ménage, je joins deux images provenant de gitk. La première image donne la structure des révisions, avec les annotations en gris qui montrent les endroits choisis par Git pour les essais de bisect:

L'image suivante est obtenue en cliquant sur le bisect/bad juste au-dessus de la branche bisect (en vert). Git me montre alors exactement ces modifications qui ont introduit l'erreur.

gitk m'impressionne, qui permet de voir l'état des fichiers, modifications et des diffs à tout moment, et instantanément.

Ça n'est pas mignon, tout ça? !! ☺ Et une petite chose que je ne t'ai pas dite. J'ai dû faire les tests à bras, parce que mon essai bloque quand il ne fonctionne pas, il faut que je tapoche dessus avec des Ctrl-C pour l'interrompre. Mais si le test terminait en détectant l'erreur, ça serait différent. Par exemple, je pourrais écrire mon petit script ./essai ainsi:

#!/bin/bash
pytest -k test_41

pour exécuter la batterie de tests nº 41, qui retourne un statut zéro seulement si tous ces tests réussissent. Alors, je peux faire:

git bisect run ./essai

et à ce moment, automatiquement, sans intervention de ma part, Git va m'identifier la correction introduisant une erreur dans ce test. Pour Pymacs, cela voudrait dire, j'imagine, une douzaine de secondes. En fait, Git est fulgurant de vitesse, au moment de ramener un répertoire ou un ensemble de fichiers à un moment précis de leur histoire. (Git est particulièrement habile à détecter un fichier qui tu as déplacé ou renommé, avant de le modifier — tout un défi en soi, si tu y penses.)

Je n'ai rien fait que de suivre des modèles établis par d'autres, et encore, bien timidement. Ils se promènent là-dedans comme des poissons dans l'eau, que j'en suis jaloux ☺. Bon sang, ce que j'aurais aimé connaître des outils comme ceux-là bien plus tôt dans ma vie. Tout le temps que j'aurais économisé!

[2011-08-30 mar] Here is an amusing article from a Git user discovering Subversion. No religious feelings here of course, besides the healthy fear of hell… ☺

Why did I want to know more about object access in packs?

La compression de Git exige qu'il découvre des fichiers très semblables quoique différents, il est probable que les algorithmes de compression et les algorithmes de recherche de similitude ont du code en commun. Git construit optionnellement un pack qui, dans un fichier unique, contient une foule d'objets originalement dans des fichiers séparés.

J'avais lu que les objets de Git (fichiers, répertoires, tags, commits) étaient comprimés avec zlib dans un pack. Hors, zlib utilise un algorithme adaptatif (en clair: les tables de décompression sont construites dynamiquement pendant la décompression séquentielle, à partir même du contenu du fichier — et donc, il n'est pas possible de commencer à décomprimer sans avoir tout lu depuis le début). Comme Git est super-efficace pour aller chercher n'importe quel objet d'un pack, je ne comprenais pas comment ça pouvait marcher…

For creating a pack, all objects are first sorted, using the object type as the first key, some of its basename as the second key, and decreasing size as the third key. Then a sliding window is created over these, and (using efficient trickery) all deltas between all objects within the sliding window are computed, and smallest deltas are retained for each object, as well as the object with which this delta is possible (this relation is bidirectional). Deltas too big for being efficient are discarded.

Then, the directionality is decided in such a way that most recent objects (that is, those likely to be needed first in other algorithms) are output first and whole, and deltas are used for deriving other objects. All objects are compressed separately, there is no zlib adaptation from an object to another. There are trickeries within the index as well, but deep down, the index directly points to objects and decompression starts from there. In a word, Git deltas do part of the compression, as zlib is not meant to be especially good on short files. The set of chosen packing algorithms is robust to wrong decisions, it will work anyway, just slower and bigger. There are a lot of heuristics built-in and, on the wide average, it all appears to work pretty well.

git: is so superior to http: because the algorithm is bidirectional at start, the on-the-fly packing which occurs at the server spares the retaining of information that it knows the receiver already has.

Jim Meyering got me started with his comparison of Git and Mercurial. Wikipedia offers a list and a comparison of VCSes. For the three main distributed ones (Bazaar, Git, Mercurial), I liked this comparison. Here are a few own subjective opinions on the matter.

An English summary

Surely, I did use CVS a few times, from a long time ago, and hated it for a lot of reasons. Subversion is much cleaner and bearable, yet the mentality did not evolve much beyond CVS concepts. PRCS was kind of clean, but too toyish to be taken seriously, and it just disappeared. Bazaar was part of the wave trying to break out of these patterns. Some say that Arch has been a turning point, yet I once tried to look at Arch and soon ran away, screaming, completely terrorized☺. DARCS has many good ideas, but installation is nightmarish. And a few others. It seems that nowadays, Mercurial and Git are the best ones — something which Bazaar at least recognises, as it lists these two as being the main competition.

In French, some more details (email to a friend)

Tu as probablement déjà utilisé RCS ou SCCS, qui s'occupent de conserver l'histoire d'un seul fichier à la fois. CVS étend la notion de RCS à une collection de fichiers, et quoiqu'il soit encore très populaire, pour avoir vécu très longtemps, j'ai toujours trouvé ennuyeux de configurer et entretenir ses reposoirs, en plus de souffrir le manque de collaboration et l'attitude hautaine de ceux qui entretiennent CVS lui-même — les gens ont changé depuis, mais j'ai la mémoire longue ☺.

Subversion (SVN), que j'ai d'ailleurs introduit chez un client il y a quelques années, est une implantation de CVS repensée, beaucoup plus propre et homogène, plus solide aussi (mais seulement une fois bsddb remplacé par fsfs — un système de fichiers dans le système de fichiers). Par contre, très fondamentalement, SVN n'apporte pas de gros concept nouveau par rapport à CVS, certaines lourdeurs s'y retrouvent inchangées.

La révolution commence ensuite, et je me rends compte que je l'ai suivie un peu, quand même, malgré tout, même si je ne connaissais pas Git…

Avant de choisir SVN pour mon client, j'avais regardé les alternatives, autour. J'ai essayé Arch (ou tla), mais je suis vite enfui, horrifié, complètement terrorisé. Pourtant, plusieurs semblent s'en contenter: il doit y avoir un masochisme informatique! J'ai étudié Monotone, que m'a suggéré le responsable de GNU libc, qui ne jurait que par lui. Tout en comprenant qu'il était adéquat pour un projet de portée planétaire, il m'est apparu complexe et surabondant pour les besoins de mon client qui est, dans le fond, une très petite planète ☺. On parlait un petit peu de Bazaar, qui était encore trop instable pour être sérieusement considéré.

J'ai regardé PRCS, très élégant, très pur, mais trop loin de la vraie vie pour être utilisé par des non-idéalistes; il n'est même pas listé à l'URL que je t'ai fourni plus haut. J'ai regardé DARCS aussi, mais l'installation de Haskell a été un cauchemard (à cause d'un bootstrapping difficile, compliqué) que je n'imposerais ni aux autres ni à moi-même.

Mercurial (ou hg) m'a semblé au moins intéressant par le fait que c'est un système de facture moderne, essentiellement écrit en Python. On considère de nos jours que c'est l'un des meilleurs, et il est utilisé par un confrère montréalais avec lequel je collabore à l'occasion. Mais finalement, je suis en train de me concentrer sur Git, très comparable à Mercurial, mais fulgurant de vitesse, dont la maturité est reconnue, et dont le développement est très actif. On dit qu'un port Windows est imminent, ainsi qu'une implantation alternative entièrement en Java.

Git possède environ 150 commandes, mais une dizaine devrait suffire pour les opérations habituelles, l'usage me semble facile, en pratique. J'ai une demi-douzaine d'interfaces graphiques pour Git ici, et les deux que j'ai regardés me semblent bien faits, et utiles (et très rapides). Mais l'apprentissage plus complet des 150 commandes sera plutôt exigeant…