Quelle est la différence entre "git diff --patience" et " git diff --histogramme`?

Cet histogramme stratégie a été introduit dans git 1.7.7 (Sept 2011), avec la description suivante (comme mentionné par l'OP)

"git diff" appris "--histogram" option pour utiliser un autre diff génération de machines volées de jgit, ce qui pourrait donner une meilleure performance.

JGit comprend src/org/eclipse/jgit/diff/HistogramDiff.java et tst/org/eclipse/jgit/diff/HistogramDiffTest.java

La description, il est assez complet:

HistogramDiff

Une forme élargie de Bram Cohen patience algorithme de comparaison.

Cette mise en œuvre a été dérivé en utilisant les 4 règles décrites dans la
Bram Cohen blog, puis a été étendu à l'appui de faible occurrence d'éléments communs.

L'idée de base de l'algorithme est d' créer un histogramme des occurrences pour chaque élément de la séquence d'Un. Chaque élément de la séquence B est alors considéré à son tour. Si l'élément existe également dans Une séquence, et a une baisse du nombre d'événements, les positions sont considérées comme un candidat pour la plus longue sous-suite commune (LCS).

Après la numérisation est terminée le CL qui a le plus faible nombre d'occurrences est choisi comme point de split. La région est divisée autour de la LCS, et l'algorithme est appliquée de manière récursive pour les sections avant et après les LCS.

Par toujours de la sélection d'un LCS position avec le plus faible nombre d'événements, cet algorithme se comporte exactement comme Bram Cohen patience diff chaque fois qu'il existe un unique élément commun entre les deux séquences.

Lorsque aucun des éléments uniques existent, la plus faible occurrence de l'élément est choisi à la place.

Cela offre plus lisible diffs que de simplement revenir à la norme Myers O(ND) algorithme produire.

Pour empêcher l'algorithme d'avoir un O(N^2) temps d'exécution, une limite supérieure sur le nombre d'éléments uniques dans un histogramme seau est configuré par #setMaxChainLength(int).

Si la séquence a plus que cela de nombreux éléments qui hachage dans le même compartiment de hachage, l'algorithme passe à la région de #setFallbackAlgorithm(DiffAlgorithm).

Si aucun secours algorithme est configuré, la région est émis comme remplacer les modifier.

Pendant la lecture de la séquence B, tout élément de A qui arrive à plus de #setMaxChainLength(int) fois n'est jamais considéré comme un LCS correspondre à la position, même si elle est commune entre les deux séquences. Cela limite le nombre d'emplacements dans Une séquence qui doivent être considérés pour trouver la CL,et aide à maintenir un faible temps de fonctionnement liés.

Tant que #setMaxChainLength(int) est une petite constante (64), l'algorithme s'exécute en O(N * D) temps, où N est la somme des longueurs d'entrée et D est le nombre de modifications dans la EditList.

Si l'fournis SequenceComparator a une bonne fonction de hachage, cette mise en œuvre généralement hors-effectue MyersDiff, même si sa théorie, temps de fonctionnement est le même.

Cette mise en place a une limitation interne qui l'empêche de manipulation de séquences avec plus de 268,435,456 (2^28) éléments

---

Noter que ce type d'algo a été déjà utilisé pour pack_check, en 2006 git (1.3), pour git-verify-pack -v. Il a été réutilisé pour l'index-pack dans git 1.7.7

---

S'engager 8c912ee en fait introduit --histogram diff:

Port JGit de HistogramDiff algorithme à C. de gros (TODO) montrer
qu'il est plus rapide que son --patience cousin, ainsi que la valeur par défaut Meyers algorithme.

La mise en œuvre a été retravaillée pour utiliser les structures et pointeurs,
au lieu de masques de bits, faisant ainsi de suite avec JGit de 2^28 de la ligne de limite.

Nous utilisons également xdiffpar défaut de la table de hachage de mise en œuvre (xdl_hash_bits()
avec XDL_HASHLONG()) pour des raisons de commodité.

s'engager 8555123 (git 1.7.10, avril 2012) ajouté:

8c912ee (enseigner --histogram à diff, 2011-07-12) a revendiqué l'histogramme diff
a été plus rapide que celle de Myers et de la patience.

Depuis, nous avons incorporé un test de performance du cadre, il faut donc ajouter un
test qui compare les différentes diff tâches effectuées dans un vrailog -p'
la charge de travail.

Cela ne montrent, en effet, que l'histogramme diff légèrement beats Myers, tandis que la patience est beaucoup plus lent que les autres.

Enfin, s'engager 07ab4de (git 1.8.2, Mars 2013) ajouter

config: Introduire diff.algorithme variable

Certains utilisateurs ou des projets préfèrent les différents algorithmes sur les autres, par exemple, de la patience plus de myers ou similaire.

Cependant, la spécification appropriée argument à chaque fois diff est à utiliser est impraticable. En outre, la création d'un alias ne joue pas bien avec d'autres outils basés sur diff (git-show par exemple).

Par conséquent, une variable de configuration qui est en mesure de définir algorithme spécifique est nécessaire.

Pour l'instant, ces quatre valeurs sont acceptées:

• 'myers"(qui a le même effet que de ne pas définir la variable de config à tous),
• 'minimal',
• 'patience"et
• 'histogram'.

S'engager 07924d4 ajoutées en même temps que la --diff-algorithm option de ligne de commande.

Comme l'OP Stuart P. Bentley mentionne dans les commentaires:

vous pouvez configurer Git à l'utilisation de l'histogramme par défaut avec:

git config --global diff.algorithm histogram

---

Mise à jour: Git 2.12 (T1 2017) vont partir à la retraite le "fast hash" qui avait désastreux des problèmes de performances dans certains cas de coin.

Voir s'engager 1f7c926 (01 Dec 2016) par Jeff King (peff).
^{(Fusionnés par Junio C Hamano -- gitster -- dans s'engager 731490b, 19 Dec 2016)}

xdiff: drop XDL_FAST_HASH

La xdiff code de hachages de chaque ligne de deux côtés d'un diff, puis les compare à ceux des hachages de trouver les doublons. La performance globale dépend à quelle vitesse nous pouvons calculer les hachages, mais aussi sur le nombre de collisions de hachage nous voir.

L'idée de XDL_FAST_HASH est d'accélérer le calcul de hachage.

La génération de hachages ont pire comportement de collision. Cela signifie que dans certains cas, les vitesses de diff en place (en cours d'exécution "git log -p" sur git.git améliore par ~8% avec elle), mais dans d'autres, il peut ralentir les choses. Un cas pathologique vu sur une 100x ralentissement.

Il y a peut être une meilleure fonction de hachage qui couvre à la fois les propriétés, mais en attendant, nous sommes mieux avec le hachage d'origine. C'est un peu plus lent dans le cas le plus courant, mais il a moins surprenant cas pathologiques.

---

Remarque: "git diff --histogram" avait une mauvaise utilisation de la mémoire de modèle, qui a
été réorganisée afin de réduire l'utilisation de pointe, avec Git 2.19 (T3 2018).

Voir s'engager 79cb2eb, s'engager 64c4e8b, s'engager c671d4b, s'engager 2820985 (19 Juillet 2018) par Stefan Beller (stefanbeller).

^{(Fusionnés par Junio C Hamano -- gitster -- dans s'engager 57fbd8e, le 15 Août 2018)}

xdiff/xhistogram: déplacer la répartition des indices dans find_lcs

Cette mise à jour corrige un problème de mémoire lorsque recursing beaucoup, qui peut être reproduit que

seq 1   100000 >one
seq 1 4 100000 >two
git diff --no-index --histogram one two

Avant ce patch, histogram_diff pourrait appeler récursivement avant
l'appel de free_index, ce qui voudrait dire beaucoup de mémoire est allouée au
la récursivité et seulement libéré par la suite.

Par le déplacement de l'allocation de mémoire (et son appel gratuit) dans find_lcs, la mémoire est libre avais avant de nous répéter, tels que la mémoire est réutilisé dans la prochaine étape de la récursion au lieu d'utiliser une nouvelle mémoire.

Ce que les adresses de la mémoire de pression, pas le temps d'exécution de la complexité,
c'est aussi terrible pour le coin des cas décrits ci-dessus.