此直方图策略已在git1.7.7（2011年9月）中引入，并带有以下描述（如OP所述）

“

git diff

”学习了一个“

--histogram

”选项，可以使用从jgit窃取的另一种差异生成机器，这可能会提供更好的性能。

JGit包括

src/org/eclipse/jgit/diff/HistogramDiff.java

tst/org/eclipse/jgit/diff/HistogramDiffTest.java

那里的描述相当完整：

直方图差异

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

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

该算法的基本思想是为 序列A的每个元素创建出现的直方图
。然后依次考虑序列B的每个元素。如果元素也存在于序列A中，并且出现次数较少，则将这些位置视为最长公共子序列（LCS）的候选对象。
扫描完B后，将出现次数最少的LCS选择为分割点。在LCS周围划分区域，并将算法递归应用于LCS之前和之后的部分。

通过始终选择发生次数最少的LCS位置，只要两个序列之间存在唯一的公共元素，该算法的行为就与Bram Cohen的耐心差异完全一样。
如果不存在唯一元素，则选择出现次数最少的元素。
与仅依靠标准Myers

O(ND)

算法产生的差异相比，这提供了更具可读性的差异。

为了防止该算法

O(N^2)

运行时间，直方图桶中唯一元素数量的上限由设置

#setMaxChainLength(int)

。

如果序列A的哈希元素散布到同一个哈希桶中的元素数量超过此数目，则算法会将区域传递给

#setFallbackAlgorithm(DiffAlgorithm)

。
如果未配置回退算法，则该区域将作为替换编辑发出。

在扫描序列B的过程中，

#setMaxChainLength(int)

不会对LCS匹配位置考虑多次出现的A元素，即使这在两个序列之间是相同的。这限制了找到LCS时必须考虑的序列A中的位置数量，并有助于维持较短的运行时间范围。

只要

#setMaxChainLength(int)

是一个小常数（例如64），该算法就会

O(N* D)

及时运行，其中

N

是输入长度的总和，

D

是结果中的编辑次数

EditList

。

如果提供的

SequenceComparator

具有良好的哈希函数

MyersDiff

，则即使其理论运行时间相同，该实现也通常会超出性能。

此实现有一个内部限制，它不能处理包含超过268,435,456（2 ^ 28）个元素的序列

请注意，早在2006年（git1.3）中，这种算法已用于pack_check

git-verify-pack -v

提交8c912ee实际上引入

--histogram

将JGit的HistogramDiff算法移植到C语言上。粗糙数（TODO）表明，它比其

--patience

表亲以及默认的Meyers算法要快。

该实现已被重新设计为 使用结构和指针而不是位掩码，从而消除了JGit的

2^28

line limit。

为了方便起见，我们还使用

xdiff

的默认哈希表实现（

xdl_hash_bits()

和

XDL_HASHLONG()

）。

提交8555123（git1.7.10，2012年4月）添加：

8c912ee（教学时间

--histogram

为

diff

2011-07-12）声称直方图比较比Myers和耐心都要快。

此后，我们已经合并了一个性能测试框架，因此添加一个测试，以比较在实际

log -p

工作负载中执行的各种差异任务。
这确实表明直方图差异略胜于Myers，而耐心则慢得多。

最后，提交07ab4de（git1.8.2，2013年3月）添加

config：引入diff.algorithm变量

与其他算法相比，某些用户或项目更喜欢不同的算法，例如，对myers或类似算法的耐心。
但是，每次使用diff时都指定适当的参数是不切实际的。而且，创建别名不能与其他基于diff的工具配合使用（

git-show

例如）。

因此，需要一种能够设置特定算法的配置变量。
目前，这四个值已被接受：

• ‘

  myers

  ‘（与完全不设置config变量具有相同的效果），
• ‘

  minimal

  ‘
• “

  patience

  ”和
• ‘

  histogram

  ‘。
  

提交07924d4并发添加了

--diff-algorithm

您可以配置Git在默认情况下使用直方图 ：

git config --global diff.algorithm histogram

更新：Git 2.12（2017年第一季度）将淘汰在某些极端情况下具有灾难性性能问题的“快速哈希”。

参见Jeff
King（）提交1f7c926（2016年12月1日）。
（由Junio C
Hamano合并--在731490b号文件中，2016年12月19日）

peff

gitster

xdiff

：掉落

XDL_FAST_HASH

该

xdiff

代码哈希一个diff两侧的每一行，然后比较这些哈希查找重复。总体性能不仅取决于我们能够计算哈希的速度，而且取决于我们看到的哈希冲突数。

的想法

XDL_FAST_HASH

是加快哈希计算。
但是，生成的哈希具有较差的碰撞行为。这意味着在某些情况下，它可以加快扩散速度（通过运行“

git log -p

”

git.git

可以提高速度

~8%

），但在其他情况下，则可以减慢速度。一个病理病例减速了100倍。

可能有一个更好的哈希函数可以同时覆盖这两个属性，但与此同时，我们最好还是使用原始哈希。在一般情况下，它的速度稍慢一些，但在令人惊讶的病理情况下却很少。

注意：“

git diff --histogram

请参阅Stefan
Beller（）的commit
79cb2eb，commit
64c4e8b，commit
c671d4b，commit
2820985（2018年7月19日）。（由Junio
C
Hamano合并--在commit
57fbd8e中，2018年8月15日）

stefanbeller

gitster

xdiff/xhistogram

：将索引分配移入

find_lcs

这修复了递归多次时的内存问题，该问题可以复制为

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

在此补丁之前，

histogram_diff

将在调用之前递归地调用自身

free_index

，这意味着在递归过程中分配了很多内存，然后才释放它们。

通过将内存分配（及其免费调用）移入

find_lcs

，在递归之前内存将被释放，从而在递归的下一步中可以重用内存，而不必使用新的内存。

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