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

git view diff in file

Question

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 elsewhere .

¿Cómo funciona la estrategia del histogram ? ¿Qué lo diferencia de la patience ? La página de manual de git-diff solo dice que "amplía el algoritmo 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 algoritmo o resultados difieren de la patience .

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

(Si solo se trata de un rendimiento 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 ?)

Answer 1

Esta estrategia de histograma 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 dar un mejor rendimiento.

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 algoritmo 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 algoritmo es crear un histograma 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 división. La región se divide alrededor del LCS, y el algoritmo se aplica recursivamente a las secciones antes y después del LCS.

Al seleccionar siempre una posición LCS con el recuento de ocurrencia más bajo, este algoritmo 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 algoritmo Myers '' O(ND) .

Para evitar que el algoritmo tenga un tiempo 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 algoritmo pasa la región a #setFallbackAlgorithm(DiffAlgorithm) .
Si no se configura ningún algoritmo de repliegue, la región se emite como una edición de reemplazo.

Durante el escaneo de la secuencia B, ningún elemento de A que ocurra más que #setMaxChainLength(int) veces nunca se considera para una posición 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 tiempo de ejecución.

Siempre que #setMaxChainLength(int) sea ​​una pequeña constante (como 64), el algoritmo se ejecuta en O(N * D) tiempo, donde N es la suma de las longitudes de entrada y D es el número de ediciones en la EditList resultante .
Si el SequenceComparator suministrado tiene una buena función hash, esta implementación suele MyersDiff , aunque su tiempo 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 cuenta 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 paquete de índice en git 1.7.7

Commit 8c912ee realmente introducido --histogram a diff:

El algoritmo HistogramDiff de Port JGit a C. Los números aproximados (TODO) muestran que es más rápido que su primo de --patience , así como el algoritmo de Meyers predeterminado.

La implementación se ha rediseñado para usar estructuras y punteros, 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 predeterminada 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 el histograma diff fue más rápido que Myersers y paciencia.

Desde entonces, hemos incorporado un marco de prueba de rendimiento, así que agregue una prueba que compare las diversas tareas de diff realizadas en una carga de trabajo real '' log -p ''.
De hecho, esto muestra que el histograma 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 algoritmos 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 configuración que sea capaz de establecer un algoritmo específico.
Por ahora, estos cuatro valores son aceptados:

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

Commit 07924d4 agregado al mismo tiempo la opción de línea de comando --diff-algorithm .
Como dice OP en los comentarios :

puede configurar Git para usar histograma de forma predeterminada con:

git config --global diff.algorithm histogram

Actualización: Git 2.12 (Q1 2017) retirará el "hash rápido" que tuvo problemas de rendimiento 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 duplicados . El rendimiento general depende de cuán rápido podamos calcular los hashes, 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 función hash que cubra ambas propiedades, pero mientras tanto estamos mejor con el hash original. Es un poco más lento en el caso común, pero tiene menos casos patológicos sorprendentes.

Nota: " git diff --histogram " tenía un patrón de uso de memoria incorrecto, que se ha reorganizado para reducir el uso máximo, con Git 2.19 (Q3 2018).

Consulte commit 79cb2eb , commit 64c4e8b , commit c671d4b , commit 2820985 (19 de julio de 2018) por Stefan Beller ( stefanbeller ) .
^{(Fusionada por Junio ​​C Hamano - gitster - in commit 57fbd8e , 15 Ago 2018)}

xdiff/xhistogram : mueve la asignación de índice a find_lcs

Esto soluciona un problema de memoria cuando se repite mucho, que se puede reproducir como

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

Antes de este parche, histogram_diff se llamaría recursivamente antes de llamar a free_index , lo que significaría que se asigna mucha memoria durante la recursión y solo se liberará después.

Al mover la asignación de memoria (y su llamada gratuita) a find_lcs , la memoria se libera antes de recurse, de modo que la memoria se reutiliza en el siguiente paso de la recursión en lugar de usar memoria nueva.

Esto solo aborda la presión de la memoria, no la complejidad del tiempo de ejecución, que también es horrible para el caso de esquina descrito anteriormente.