¿Cuál es la diferencia entre `git diff –patience` y` git diff –histogram`?

Esta pregunta anterior preguntaba por las diferencias entre 4 diferentes estrategias de diferencias de Git, pero la única diferencia que se explicó fue la diferencia entre myers y la patience , que está bastante bien explicada en otros lugares .

¿Cómo funciona la estrategia del histogram ? ¿Qué lo diferencia de la patience ? La página de manual de gitdiff solo dice que "amplía el algorithm de paciencia para" admitir elementos comunes de baja ocurrencia ". Otras páginas mencionan que es más rápido, y que proviene de JGit, pero no explican dónde o cómo su algorithm o resultados difieren de la patience .

¿Dónde puedo encontrar una descripción del algorithm de histogram relativo al algorithm de patience , con el mismo nivel de detalle que la descripción original de Bram Cohen del algorithm de patience ?

(Si solo se trata de un performance de implementación sin ningún caso que produzca resultados diferentes, ¿por qué no se acaba de implementar como un nuevo back-end para la patience ?)

Esta estrategia de histogtwig se introdujo en git 1.7.7 (septiembre de 2011) , con la siguiente descripción (según lo mencionado por el OP)

" git diff " aprendió una opción " --histogram " para usar una maquinaria diferente de generación de diff robada de jgit , lo que podría proporcionar un mejor performance.

JGit incluye src/org/eclipse/jgit/diff/HistogramDiff.java y tst/org/eclipse/jgit/diff/HistogramDiffTest.java

La descripción allí es bastante completa:

HistogramDiff

Una forma extendida del algorithm de paciencia de Bram Cohen.

Esta implementación se obtuvo mediante el uso de las 4 reglas que se describen en el blog de Bram Cohen , y luego se amplió para admitir elementos comunes de baja ocurrencia.

La idea básica del algorithm es crear un histogtwig de ocurrencias para cada elemento de la secuencia A. Cada elemento de la secuencia B se considera a continuación. Si el elemento también existe en la secuencia A y tiene un recuento de ocurrencia menor, las posiciones se consideran candidatas para la subsecuencia común más larga (LCS).
Después de completar el escaneo de B, se elige el LCS que tiene el menor número de ocurrencias como punto de split. La región se divide alnetworkingedor del LCS, y el algorithm se aplica recursivamente a las secciones antes y después del LCS.

Al seleccionar siempre una position LCS con el recuento de ocurrencia más bajo, este algorithm se comporta exactamente igual que la paciencia de Bram Cohen cuando hay un elemento común único disponible entre las dos secuencias.
Cuando no existen elementos únicos, se elige el elemento de ocurrencia más baja .
Esto ofrece diferencias más fáciles de leer que simplemente retroceder en el estándar que produciría el algorithm Myers ' O(ND) .

Para evitar que el algorithm tenga un time de ejecución O(N^2) , #setMaxChainLength(int) configura un límite superior en el número de elementos únicos en un #setMaxChainLength(int) de #setMaxChainLength(int) .
Si la secuencia A tiene más elementos que el hash en el mismo cubo hash, el algorithm pasa la región a #setFallbackAlgorithm(DiffAlgorithm) .
Si no se configura ningún algorithm de repliegue, la región se emite como una edición de reemploop.

Durante el escaneo de la secuencia B, cualquier elemento de A que ocurra más que #setMaxChainLength(int) veces nunca se considera para una position de coincidencia de LCS, incluso si es común entre las dos secuencias. Esto limita el número de ubicaciones en la secuencia A que se debe considerar para encontrar el LCS, y ayuda a mantener un límite inferior de time de ejecución.

Siempre que #setMaxChainLength(int) sea ​​una pequeña constante (como 64), el algorithm se ejecuta en O(N * D) time, donde N es la sum de las longitudes de input y D es el número de ediciones en la EditList resultante .
Si el SequenceComparator suministrado tiene una buena function hash, esta implementación suele MyersDiff , aunque su time de ejecución teórico sea el mismo.

Esta implementación tiene una limitación interna que le impide manejar secuencias con más de 268,435,456 (2 ^ 28) elementos


Tenga en count que este tipo de algo ya se utilizó para pack_check, en 2006 (git 1.3) , para git-verify-pack -v . Se reutilizó para el package de índice en git 1.7.7


Commit 8c912ee realmente introducido --histogram a diff:

El algorithm HistogramDiff de Port JGit a C. Los numbers aproximados (TODO) muestran que es más rápido que su primo de --patience , así como el algorithm de Meyers pnetworkingeterminado.

La implementación se ha networkingiseñado para utilizar estructuras y pointers, en lugar de máscaras de bits, eliminando así el límite de línea de 2J28 de JGit .

También usamos la implementación de la tabla hash pnetworkingeterminada de xdl_hash_bits() con XDL_HASHLONG() ) por conveniencia.

commit 8555123 (git 1.7.10, abril de 2012) agregado:

8c912ee (enseñar --histogram to diff , 2011-07-12) afirmó que la diferencia entre histogtwigs fue más rápida que Myers y paciencia.

Desde entonces, hemos incorporado un marco de testing de performance, así que agregue una testing que compare las diversas tareas de diff realizadas en una carga de trabajo real ' log -p '.
De hecho, esto muestra que el histogtwig diff ligeramente supera a Myers, mientras que la paciencia es mucho más lenta que las demás.

Finalmente, cometer 07ab4de (git 1.8.2, marzo de 2013) agregar

config: Introducir la variable diff.algorithm

Algunos usuarios o proyectos prefieren algorithms diferentes a otros, por ejemplo, paciencia sobre myers o similar.
Sin embargo, especificar el argumento apropiado cada vez que se use diff no es práctico. Además, crear un alias no funciona muy bien con otras herramientas basadas en diff ( git-show por ejemplo).

Por lo tanto, se necesita una variable de configuration que sea capaz de establecer un algorithm específico.
Por ahora, estos cuatro valores son aceptados:

  • ' myers ' (que tiene el mismo efecto que no configurar la variable de configuration),
  • ' minimal ',
  • ' patience ' y
  • ' histogram '.

Commit 07924d4 agregado al mismo time la opción de línea de command --diff-algorithm .
Como dice OP Stuart P. Bentley en los comentarios :

puede configurar Git para usar histogtwig de forma pnetworkingeterminada con:

 git config --global diff.algorithm histogram 

Actualización: Git 2.12 (Q1 2017) retirará el "hash rápido" que tuvo problemas de performance desastroso en algunos casos de esquina.

Ver commit 1f7c926 (01 Dec 2016) por Jeff King ( peff ) . (Fusionada por Junio ​​C Hamano – gitster – in commit 731490b , 19 de diciembre de 2016)

xdiff : soltar XDL_FAST_HASH

El código xdiff hash de todas las líneas de ambos lados de un diff, y luego compara esos hashes para encontrar duplicates . El performance general depende de cuán rápido podamos calcular los hash, pero también de la cantidad de colisiones hash que vemos.

La idea de XDL_FAST_HASH es acelerar el cálculo hash.
Pero los hashes generados tienen un peor comportamiento de colisión. Esto significa que en algunos casos aumenta la velocidad (ejecutando " git log -p " en git.git mejora en ~8% con él), pero en otros puede ralentizar las cosas. Un caso patológico vio una ralentización de 100x .

Puede haber una mejor function hash que cubra ambas properties, pero mientras tanto estamos mejor con el hash original. Es un poco más lento en el caso común, pero tiene less casos patológicos sorprendentes.