服务器安全防护_ddos防御套餐_解决方案

优化git的合并机制，#2PalantirFollowMar 8.9分钟阅读

编者注：这是Palantir软件工程师关于优化git的合并和重命名检测机制的系列文章中的第二篇。点击阅读第一篇文章。

在本系列的第一篇文章中，我提供了一些关于git merge机制如何工作的背景知识，为什么我要改进它，并展示了一个简单的优化，以加速它，更好地利用精确重命名。

我们将以最简单的方式对以下三个文件进行合并：

我们将以最简单的方式对这些文件进行合并：

我们将以最简单的方式对它们进行更新；上一篇博文中的两句话：

合并不是一个双向操作，而是一个三向操作，git在其中查阅合并基础、当前提交和另一个分支顶端的提交。[…]因此，合并算法背后的基本思想是使用来自这三次提交的每个文件的版本，对存储库中的每个文件进行三向内容合并。

和

重命名检测是一种二次算法。它涉及到首先获取合并基唯一的所有N个文件名的集合，然后获取给定端唯一的所有M个文件名，然后在所有N x M文件的内容之间进行相似性比较，并将充分相似的最佳匹配标记为重命名。即使是少量的重命名也足以使重命名检测成为合并过程中最慢的部分。

上面第二句话中很容易漏掉的一件有趣的事情是，git将合并基和给定端中具有相同名称的文件视为相关文件，并因此自动对它们进行三向内容合并，不考虑文件内容的实际相似性。Git允许使用命令行标志（--break rewrites或-B）关闭某些命令（如Git diff或Git log）的自动配对；这被称为"中断检测"。当打开"中断检测"时，git将检查同名文件的相似性，如果它们不够相似，则将它们视为单独的文件，并将两者放入桶中进行重命名检测。

合并机制不会打开中断检测；如果是这样的话，速度会慢很多。这本质上意味着git说文件名是匹配三方内容合并文件的好指南，但前提是文件名完全匹配。如果文件名不完全匹配，它会说唯一重要的是两个文件的内容相似性。简言之，可以参考文件名相似性和内容相似性来确定哪些文件应该配对以进行三向内容合并。我们将回到这里，但现在我们将集中于内容相似性比较。

好的，那么这对文件意味着什么？

从图片上看，我们可以将其视为一个矩阵。左侧列出合并基的唯一文件名，顶部列出给定端的唯一文件名，例如，我们可以看到如下视图：

然后，对于每个单元格，我们计算两个文件的相似性百分比并存储。完成后，我们会为每个文件寻找最佳匹配，如果最佳匹配足够好，我们会将文件标记为重命名。在上一篇博文中，我们注意到我们可以利用git对所有内容的哈希存储来提供一种快速检测某些重命名的方法。但如果没有精确匹配，或者精确匹配后仍有大量文件，该怎么办？我们还能做些什么吗？好吧，如果我用稍微不同的方式展示同一个矩阵会怎么样：

以一个五岁孩子可以解决的方式重新构造它

在看了一长串文件之后（比这里的列表长得多），我注意到一些关于匹配文件的明显的东西。让我们以稍微不同的方式重新展示这个矩阵：

在不查看实际文件内容的情况下，是否更容易注意到可能的重命名对？我刚问了我五岁的女儿，她认出了四对可能的情侣。当然，我们不能对内容进行颜色编码，但这只是一种简单的方法，可以强调这样一个事实：重命名通常涉及将文件移动到不同的目录中，同时保持文件的基本名称（最后一个目录分隔符之后的所有内容，包括扩展名）不变。这是作弊吗？这是否有助于实践中的许多案例？这是只适用于某些存储库的特殊情况吗？所以最大的问题是…

这有多普遍？

我查看了一些真实世界的存储库，并查看了每个存储库中的历史重命名。我查找了没有更改相关文件的basename的重命名百分比。以下是我的发现：

linux:76%gcc:64%gecko:79%webkit:89%git.git:16%