`git diff --patience`和`git diff --histogram`有什么区别？

Question

这个早期的问题要求4种不同的Git差异策略之间存在差异,但唯一的区别就是myers和之间的区别patience,这在其他地方得到了很好的解释.

该histogram战略如何运作？有什么区别patience？在GIT-DIFF手册页只能说,它"伸出耐心算法'支持低发生共同的元素’." 其他页面提到它更快,它来自JGit,但它们没有解释其算法或结果的不同之处或方式patience.

我在哪里可以找到与histogram算法相关的patience算法描述,其详细程度与Bram Cohen对patience算法的原始描述相同？

(如果只是实现性能的问题,没有会产生不同结果的情况,为什么它不仅仅作为新的后端实现patience？)

Answer 1

该直方图策略在git 1.7.7(2011年9月)中引入,具有以下描述(如OP所述)

" git diff"学会了一个" --histogram选项"来使用从jgit中窃取的不同差异生成机器,这可能会提供更好的性能.

JGit包括src/org/eclipse/jgit/diff/HistogramDiff.java和tst/org/eclipse/jgit/diff/HistogramDiffTest.java

那里的描述相当完整:

HistogramDiff

Bram Cohen的耐心差异算法的扩展形式.

此实现是通过使用Bram Cohen博客中概述的4条规则得出 的,然后进一步扩展为支持低发生的常见元素.

该算法的基本思想是为序列A的每个元素创建出现的直方图.然后依次考虑序列B的每个元素.如果元素也存在于序列A中,并且具有较低的出现次数,则将这些位置视为最长公共子序列(LCS)的候选者.
在B的扫描完成之后,选择具有最低出现次数的LCS作为分割点.该区域围绕LCS分割,并且该算法递归地应用于LCS之前和之后的部分.

通过始终选择具有最低出现次数的LCS位置,只要在两个序列之间存在唯一的公共元素,该算法就像Bram Cohen的耐心差异一样.
如果不存在唯一元素,则选择最低出现元素.
这提供了更多可读的差异,而不是简单地回到迈尔斯的标准O(ND)算法会产生的差异.

为了防止算法具有O(N^2)运行时间,配置直方图桶中的唯一元素数量的上限#setMaxChainLength(int).
如果序列A具有多个散列到相同散列桶中的元素,则算法将该区域传递给#setFallbackAlgorithm(DiffAlgorithm).
如果未配置回退算法,则将该区域作为替换编辑发出.

在扫描序列B期间,任何出现#setMaxChainLength(int)次数多次的A元素都不会被认为是LCS匹配位置,即使它在两个序列之间是共同的.这限制了序列A中必须考虑查找LCS的位置数,并有助于维持较低的运行时间限制.

只要#setMaxChainLength(int)是一个小常量(例如64),算法就会O(N * D)及时运行,其中N输入长度的总和D是结果中的编辑数EditList.
如果提供的SequenceComparator具有良好的散列函数,则该实现通常优于执行MyersDiff,即使其理论运行时间相同.

此实现具有内部限制,使其无法处理具有超过268,435,456(2 ^ 28)个元素的序列

请注意,这种算法已经用于pack_check,早在2006年(git 1.3),for git-verify-pack -v.它在git 1.7.7中被重用于index-pack

提交8c912ee实际上引入--histogram了diff:

端口JGit的HistogramDiff算法到C.粗略数字(TODO)表明它比它的--patience堂兄快,以及默认的Meyers算法.

该实现已被重新设计为使用结构和指针而不是位掩码,从而消除了JGit的2^28行限制.

为方便起见,我们还使用了xdiff默认的哈希表实现(xdl_hash_bits() with XDL_HASHLONG()).

commit 8555123(git 1.7.10,2012年4月)补充道:

8c912ee(教--histogram到diff,2011-07-12)声称直方图差异比两者迈尔斯和耐心更快.

我们已经合并了一个性能测试框架,因此添加一个测试,比较在真实log -p工作负载中执行的各种差异任务.
这确实表明直方图差异略微超过迈尔斯,而耐心比其他人慢得多.

最后,提交07ab4de(git 1.8.2,2013年3月)添加

config:引入diff.algorithm变量

一些用户或项目比其他用户或项目更喜欢不同的算法,例如对迈尔斯或类似的耐心.
但是,每次使用diff时指定适当的参数是不切实际的.此外,创建别名与基于diff(git-show例如)的其他工具不能很好地协作.

因此,需要能够设置特定算法的配置变量.
目前,接受这四个值:

• ' myers'(与完全不设置配置变量的效果相同),
• ' minimal',
• " patience"和
• ' histogram'.

提交07924d4同时添加了--diff-algorithm命令行选项.
正如OP Stuart P. Bentley 在评论中提到的那样:

你可以配置Git默认使用直方图:

git config --global diff.algorithm histogram

更新:Git 2.12(2017年第一季度)将淘汰在某些极端情况下具有灾难性性能问题的"快速哈希".

请参阅Jeff King()提交1f7c926(2016年12月1日). ^{(通过合并JUNIOÇ滨野- -在提交731490b,2016年12月19日)}peffgitster

xdiff:下降 XDL_FAST_HASH

该xdiff代码哈希一个diff两侧的每一行,然后比较这些哈希查找重复.整体性能取决于我们计算哈希值的速度,以及我们看到的哈希冲突次数.

想法XDL_FAST_HASH是加快哈希计算.
但是生成的哈希值具有更差的碰撞行为.这意味着在某些情况下它的速度变差(运行" git log -p"会随之git.git改善~8%),但在其他情况下,它可以减慢速度.一个病理案例发生了超过100倍的减速.

可能有一个更好的哈希函数覆盖了这两个属性,但与此同时我们最好使用原始哈希.在常见情况下,它稍微慢一点,但它的病理情况较少.

注意:" git diff --histogram"有一个糟糕的内存使用模式,已经重新安排以减少峰值使用,使用Git 2.19(Q3 2018).

请参阅提交79cb2eb,提交64c4e8b,提交c671d4b,提交2820985(2018年7月19日)作者:Stefan Beller(stefanbeller).
^{(由Junio C gitsterHamano合并- -在提交57fbd8e,2018年8月15日)}

xdiff/xhistogram:将索引分配到 find_lcs

这可以在递归批次时修复内存问题,可以将其重现为

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

在此补丁之前,histogram_diff会在调用之前递归调用自身free_index,这意味着在递归期间会分配大量内存,之后才会释放.

通过将内存分配(及其空闲调用)移入find_lcs,在我们递归之前内存是空闲的,这样在递归的下一步中重用内存而不是使用新内存.

这仅解决了内存压力,而不是运行时复杂性,这对于上面概述的极端情况也很糟糕.