Git 中不同 diff 算法有多大差异？

导读

这篇论文（发表于 Empirical Software Engineering）实证比较了 Git 中常用的两种 diff 算法——Myers 与 Histogram——在真实代码变更上的差异：既做定量统计（如 diff 输出大小），也由两位作者人工标注 377 个文件的 diff 结果来评估可读性等质量差异，并以 kappa 一致性系数检验标注可靠性。结论大致是两种算法在多数情况下输出相近，但在部分场景下质量差异明显。

HN 关注点：HN 读者日常依赖 git diff 做代码审查和合并，讨论焦点是：不同 diff 算法的输出可读性差异有多大、论文的定性评估方法是否站得住脚，以及能否用结构化/更根本的方式做 diff 与合并。

关键词　Gitdiff 算法Myers vs Histogrammerge driver

HN 评论精选

这几条评论里：质疑 1　补充 2　亲历 1

质疑批评论文的定性评估样本仅两位作者、无盲法、抽样方法不明，方法学薄弱。

论文在说明如何发现两种算法定性差异时写道：第二步由 Myers 和 Histogram 对样本中所有文件生成 diff，前两位作者独立标注，再计算两人对 377 个文件比较结果的 kappa 一致性，得到 70.82%，属于『高度一致』（Viera 和 Garrett 2005），因此人工研究的统计结果可接受。我倾向于认同论文给的例子、也看得出做了很多工作，但这种定性分析方式太弱了：样本只有两位合写这篇 diff 算法论文的作者，样本极小且高度偏斜；标注过程完全没有提到盲法，对算法质量的先入之见可能影响评分，也可能没有，我们根本不知道；也没有清楚说明代表性样本如何选取、考虑了哪些因素……

wcarss查看英文原文

From the section about how the qualitative difference between the two algorithms was found: "In the second step, we conducted a manual comparison between two diff outputs produced by Myers and Histogram algorithms from all files in the sample. The first two authors of this paper were involved to independently annotate the diff outputs that makes the result is expected to be more reliable. ... The comparison results between two authors from 377 files were subsequently computed to find the kappa agreement.Footnote16 We obtained 70.82%, which is categorized into ‘substantial agreement’ (Viera and Garrett 2005). This means, the statistic result of our manual study is acceptable." Even though I'm inclined to agree with the example given in the paper and a lot of work clearly went into the qualitative evaluation, this feels like a very weak way to perform a qualitative analysis. Specifically: - this is a sample size of two academic authors who chose to write a paper together about the quality of different diffing algorithms, ie, a very skewed and small sample. - there is no mention of any blinding in the labeling process, so any preconceptions about the quality of different diffing may have been present in qualitative grading -- or it may not have! We don't even know. - there does not seem to be a clear mention of how the representative sample was chosen, or of what factors were taken into consideration for determining a representative sample of changes, so that reviewers/other researchers could potentially make different choices in the future and draw informed comparisons with this work. To sum up: in my admittedly not at all authoritative opinion this portion of the paper cannot conclude more than something like, "further study is warranted on this topic, with a far better controlled and far larger sample size, and clearer explications of the methodological choices". Regardless of that, it was an interesting read and not something previously on my radar as worth experimenting with at all! Kudos to the authors for drawing attention to it and for the other more quantitative aspects of the paper (which I examined less and charitably assume are top notch).

亲历亲历对比：myers 把大幅改写的函数呈现为编辑、histogram 呈现为删除+新增，孰优取决于任务。

diff 的可用性——用来完成真正有用的任务——是个很好的研究课题，但也是很难的领域。补充我的主观经验：我刚在自己的最新提交上比较了 myers 和 histogram。myers 把一个我删掉了 90% 的函数显示为同一个函数被编辑（其余内容被移到文件别处，任何 LCS 算法都找不到），有点像 word-diff 常干的事，我觉得挺聪明；histogram 则显示为一个函数被删除、一个全新函数被添加，更干净。但我也不确定哪个更可用，甚至可能随任务而变，比如看函数演化还是看函数可读性。真是个困难的领域！

hyperpallium查看英文原文

Usability of diffs, to do actual useful tasks, is an excellent research topic. But a very difficult area. To add my subjective expt: I just compared myers vs histogram on my latest commit. - myers presented a function I'd 90% gutted as the the same function, edited (the rest was moved in the file, so no LCS algo could find it), like word-diff often does. I thought this was clever. - histogram presented it as one function deleted, and a completely new function added. This was cleaner. But I'm not even sure which is more usable. Might even vary with the specific task, e.g. function evolution vs function readability. Difficult area!

补充提出把文件原生存储为 WAL 式增删序列，使 diff 完全精确，代价是空间和算力。

diff 本质上是在逆向一个多对一的函数：对字符串 X 施加多种不同的插入/删除序列都能得到同一个字符串 Y。如果反过来，原生就把文件存成插入/删除序列会怎样？也就是不要文件系统加 diff，而是 DIFF 系统加文件，类似 WAL：文件是 WAL 中的检查点（为了效率），两个检查点之间的 diff 就是 100% 精确的。不过大概会消耗多得多的空间和 CPU……

zaptheimpaler查看英文原文

Diff is reverse engineering a many to one function - many possible insert/delete sequences applied to string X map to the same string Y. What would it look like to store files natively as insert/delete sequences instead? So instead of filesystems and diffs on top, we could have DIFFsystems and files on top. Kind of like a WAL. Files would be checkpoints in the WAL for efficiency, and diffs would be 100% accurate between two checkpoints. Probably takes a hell of a lot more space & CPU though..

补充补充：结构化感知的 diff/merge 与 git merge driver 扩展点，附游戏引擎数据合并的实践链接。

实践中，如果你想合并的文件比纯文本更有结构（比如某编程语言的代码、JSON、某应用的某种数据格式），如果你的 diff/merge 工具能感知文件结构，就能做得更好。Git 提供的基于文本的工具在某种程度上是最大公约数，原则上可以为特定格式/场景构建更好的定制工具。Git 提供的一个扩展点是『merge driver』：你可以定义外部脚本/程序，当某个特定文件（按路径或模式匹配）出现合并冲突时由 Git 调用。这篇旧博客介绍了为游戏引擎数据文件定制的 git merge driver：http://bitsquid.blogspot.com/2010/06/avoiding-content-locks-and-conflicts-3.html 。在游戏开发场景下合并游戏数据文件，生成『正确』的合并结果没有生成一个格式合法的结果重要，这样非技术用户可以在带 UI 的编辑器里修正糟糕的合并决策，而不必在原始序列化格式层面解决冲突（那可能损坏数据文件、导致编辑器打不开）。

shoo查看英文原文

in practice, suppose you want to do a merge of files that have more structure than plain text. e.g. code belonging to specific a programming language, json, some data format for an application, etc. This all has a lot more structure than just plain text. You can do a better job of diffing and merging if your difftool and mergetool is aware of the structure of your file. text-based tooling that git offers is to some extent a lowest-common denominator. in principle you can build custom tooling for your format / context that does a better job. one extension point that git offers for this is the "merge driver". you can define an external script/application that will be called by git whenever a merge conflict needs to be resolved for some particular file (based on path or a pattern). Here's an older blog post describing a custom git merge driver for merging data files in a game engine: http://bitsquid.blogspot.com/2010/06/avoiding-content-locks-and-conflicts-3.html In this gamedev context of merging game data files, it was less important to produce the "correct" merge result than it was to produce some result that had a valid file format. Less technical users could then fix up bad mergetool decisions in an editor with a UI instead of trying to resolve the merge conflicts at the level of the raw serialisation format itself (which could corrupt the data file and make it not possible to load into the editor). In other situations where there is a large cost to automatically producing the wrong merge result, it would be a better tradeoff to "halt the line" if there is ambiguity about how a merge should be resolved, and escalate to a human to decide what to do. Further reading: How to wire a custom merge driver in to git: https://git-scm.com/docs/gitattributes#_defining_a_custom_merge_driver What values you can pass in to a merge driver on the command line: https://github.com/git/git/blob/f1d4a28250629ae469fc5dd59ab843cb2fd68e12/ll-merge.c Simple example of the plumbing to wire in a merge driver, with a trivial dumb driver script: https://github.com/Praqma/git-merge-driver

历次讨论

2020Hacker News 讨论帖152 分 · 38 评

HN 二十年，最值得读的论文。

朋友分享的书单

专题阅读路线

本周最多人读

我的书单

必读 30 篇

论文库

这些论文是怎么挑出来的

全量扫一遍

只留论文本身

写导读、译评论

Git 中不同 diff 算法有多大差异？

导读

HN 评论精选

相关资源

历次讨论

同领域还值得读

Google 的软件工程（2017）

Peter Naur：编程作为理论构建 (1985)

SciPy 1.0：Python 科学计算的基础算法

Lisp 的历史（1979）

使用 NumPy 进行数组编程

打赏支持

关注向阳乔木