不存 diff，怎么给你看 diff
全书从「Git 不存 diff」开始。那个说法留下了一个欠着的问题：那 git log -p 里那些红红绿绿是哪来的？答案是当场算的。这一章跑一台真的 Myers 算法引擎，你会看到那个「当场算」到底有多便宜——便宜到让「不存」成了显而易见的选择。
先确认一件事：diff 不是数据
把第 1 章那个实验再做一次，这次盯着一个具体的问题看：diff 存在哪儿？
$ git cat-file -p HEAD
tree fe7944f85150c68ee7948bfe6f5449cb57ed591f parent 06b431f5f556d4b4d9b2f2fa4240e4d12fc6c975 author Sakura <sakura@example.com> 1700000060 +0800 committer Sakura <sakura@example.com> 1700000060 +0800 second
提交里没有。树里也没有（第 3 章：树只有文件名和哈希）。blob 里更没有（第 2 章：blob 就是文件内容本身）。
整个对象库里，一条 diff 都不存在。
当你敲 git diff A B，Git 做的是：
- 取出 A 的树和 B 的树
- 用 Merkle 剪枝找出哪些路径的哈希不一样（第 3 章）
- 对每个不一样的路径，取出两个 blob 的完整内容
- 现场跑一遍差分算法，把结果打印出来
- 算完就扔
下次你再看同一个 diff，它再算一遍。
这听起来很浪费。但你待会儿会看到，第 4 步便宜得离谱——而它换来的好处（取任何版本都是 O(1)、历史不可变、天然去重）大得多。
差分算法要解决什么
问题看起来很朴素：给两段文本，找出「改了哪些行」。
但「改了哪些行」这个说法本身是含糊的。看这个例子：
旧： A B C A B B A 新： C B A B A C
你可以说「全删了再全加一遍」——那是 7 删 6 加，一共 13 处改动。正确，但没用。
也可以找出尽量多的「没变的行」，只标记真正的增删。这才是我们想要的。
找一个最短的编辑脚本（Shortest Edit Script），把旧的变成新的。
编辑操作只有两种：删一行、加一行。（「改一行」不是基本操作，它等于「删一行 + 加一行」。）
而「最短」的长度，就是这两段文本的编辑距离，记作 D。
换个角度看，这等价于找最长公共子序列（LCS）——保留的行越多，要改的就越少。两个说法是同一件事的两面。
Myers 算法：把它变成走迷宫
Eugene Myers 在 1986 年那篇论文里的想法，漂亮得值得说一说。
把两段文本摆成一个网格：横轴是旧文本的行，纵轴是新文本的行。你要从左上角 (0,0) 走到右下角 (N,M)，只能三种走法：
| 走法 | 意思 | 代价 |
|---|---|---|
| 向右 → | 删掉旧文本的一行 | 1 |
| 向下 ↓ | 加入新文本的一行 | 1 |
| 斜着 ↘ | 这一行两边一样，直接跳过 | 0 —— 免费 |
于是「找最短编辑脚本」变成了「找一条代价最小的路径」。而斜着走是免费的，所以算法的目标就是：尽可能多地走对角线。
Myers 的关键洞察是反过来搜索：不问「这条路径要花多少代价」，而是问——
花 0 步能走多远？花 1 步能走多远？花 2 步能走多远？……
每一轮 d，算法记录「用 d 步能到达的最远位置」，并且每次都贪心地把能走的对角线全部走完。第一次走到右下角时，那个 d 就是答案。
因为是按 d 从小到大搜的，第一次到达一定就是最短的。
这台引擎跑的就是那篇论文里的贪心算法（走对角线 + 回溯还原编辑脚本），和 git diff 默认用的是同一个。
先点「Myers 论文原例」——就是上面那组 ABCABBA / CBABAC，答案是 D = 5，和论文里印的一样。
然后两边随便改。盯着 D 那个数字：改得越少，D 越小。
那个 D，就是全部的答案
Myers 算法的复杂度是 O((N+M)·D)。
注意 D 在里面。这个复杂度看起来吓人，但它有个非常好的性质：
如果两个文件完全一样，D = 0，算法一轮就结束——线性时间。
如果只改了三行，D = 6（三删三加），算法跑 6 轮——几乎还是线性。
只有当两个文件面目全非时，D 才会接近 N+M，退化成 O(N²)。
而现实中的提交，恰恰全都是小改动。
一个 3000 行的源文件，你改了 5 行。N+M ≈ 6000，D = 10。运算量大约 6 万次比较——在现代 CPU 上不到一毫秒。
这就是整件事的收尾：
Git 敢于「不存 diff」，是因为需要的时候算一次几乎不要钱。
而它换来的是什么？回顾第 1 章那四个推论：取任何版本都是一步到位、判断版本相同只要比一个字符串、历史只增不改、以及内容寻址带来的天然去重。
用「每次显示时花不到一毫秒」，换掉「取版本要叠加一千层」。这笔账怎么算都划算。
Git 实际用的算法不止一个
Myers 是默认，但 Git 提供了几种，各有脾气：
| 算法 | 特点 | 什么时候用 |
|---|---|---|
myers | 默认。最短编辑脚本 | 绝大多数情况 |
minimal | Myers 加上额外搜索，保证真正最小 | 很少需要，慢 |
patience | 先锚定只出现一次的行，再分段递归 | 大块代码移动时结果好看得多 |
histogram | patience 的改进版，更快 | 综合最优，很多人会设成默认 |
为什么需要 patience？因为「最短」不等于「最好读」。
看这个经典的翻车案例——给一个函数前面插入另一个函数：
function a() {
+ return 1
+ }
+
+ function b() {
return 2
}
Myers 给出的是最短的编辑脚本（4 行新增），但它把两个函数的花括号错位匹配了——读起来像是「给 a 加了个 return，然后开了个 b」，而实际发生的是「在前面插入了一个完整的函数 a」。
patience 算法优先锚定在两边都只出现一次的行（比如 function b() {），所以不会犯这种错。代价是有时候脚本会长一两行。
$ git config --global diff.algorithm histogram # 一次设好，一劳永逸
另外一个常被忽略、但改善巨大的选项：
$ git config --global diff.colorMoved zebra # 把「移动的代码」和「新增的代码」用不同颜色区分
大重构时它能救你的命——一眼看出「这段是挪过来的」而不是「这段是新写的」。
验证「diff 是算出来的，不是存的」——直接对两个任意的 blob 做 diff，它们之间根本没有任何历史关系：
# 随便找两个 blob，它们可能来自完全不相干的提交 $ git diff 3b18e51 533ba6a
diff --git a/3b18e51 b/533ba6a index 3b18e51..533ba6a 100644 --- a/3b18e51 +++ b/533ba6a @@ -1 +1 @@ -hello world +hello world v2
Git 毫不犹豫地算了出来。它甚至不需要知道这两个 blob 有没有关系、谁在前谁在后——因为 diff 只是一个纯函数：输入两坨字节，输出一个编辑脚本。
你甚至可以对两个从来没在同一个仓库出现过的东西做 diff：
$ git diff --no-index 文件A 文件B # 完全脱离 Git 仓库用它的 diff
再看看 diff 头部那行 index：
index 3b18e51..533ba6a 100644
那两个短哈希就是前后两个 blob 的名字。所以一个 patch 文件其实自带「我是基于哪两个对象算出来的」这个信息——git apply 就靠它来验证你打补丁的位置对不对。
git blame 呢，那也是算的？是的，而且贵得多。
blame 要回答「这一行是谁在哪个提交写的」，做法是：从当前版本开始，一个提交一个提交地往回算 diff，追踪每一行的来源，直到找到它第一次出现的地方。
所以：
- 历史越长、文件越大，
blame越慢——它可能要算几百次 diff。 - 它同样没有任何存储。GitHub 上 blame 页面加载慢，就是在算这个（他们会缓存结果）。
一个很实用的技巧：如果某一行的 blame 结果指向一个「格式化整个文件」的提交，那基本没用。可以让 blame 跳过这类提交：
# 把那些纯格式化的提交号写进一个文件 $ echo "a3f21c9e77b0d4c8135e6a9f02b4d7e8c1a5b3d6" >> .git-blame-ignore-revs $ git config blame.ignoreRevsFile .git-blame-ignore-revs
GitHub 也认这个文件。大规模改格式化规则之后，加上它是对同事的一份体贴。
「为什么我调整了缩进，diff 里整个文件都变红变绿了？」
因为 diff 是逐行比较的，而缩进变了就是这一行的字节变了——Git 眼里没有「只是缩进而已」这回事（第 2 章：它只认字节）。
几个能救命的选项：
$ git diff -w # 忽略所有空白差异 $ git diff --ignore-space-change # 忽略空白数量的变化，但不忽略「有没有空白」 $ git diff --word-diff # 按词而不是按行显示 —— 改文档时特别有用
review 别人那种「顺手格式化了整个文件」的 PR 时，git diff -w 常常能把 800 行的 diff 变成 12 行的真实改动。
更根本的解法是从源头避免：
- 项目里放
.editorconfig，统一缩进和换行 - 用
.gitattributes规定换行符处理（比全局core.autocrlf可靠得多，因为它跟着仓库走） - 格式化改动单独一个提交，别和逻辑改动混在一起——然后把它加进
.git-blame-ignore-revs
最后一条尤其值得坚持。它的成本是多敲一次 commit，收益是所有人未来看这个文件的 blame 和 diff 都清爽。
这一章的一句话
对象库里没有 diff，git diff 是拿两个完整的 blob 现场跑 Myers 算法算出来的。它的复杂度 O((N+M)·D) 里那个 D 是编辑距离——两个文件越像算得越快，而现实中的提交全是小改动，所以「算一次」不到一毫秒。用这个代价，换来了取任何版本都一步到位、历史不可变、天然去重。
卷 III 结束。你现在能解释掉日常操作里的绝大部分困惑了。
下一卷进入最后一块硬骨头：当历史不再是一条直线的时候。merge、rebase、cherry-pick、那些吓人的冲突——它们全都是同一张图上的演算，而这一章的 diff 引擎会在那里再次登场，因为合并的本质就是「三个版本之间的差分」。