commit-graph:git log 为什么变快

没有 commit-graph

实测 · 本机执行输出

  $ git rev-list --count HEAD; git rev-list --merges --count HEAD; ls .git/objects/info 2>&1
  30300
  300

遍历历史时 git 要从对象库里逐个读出 commit 对象、解压、解析 parent 行。3 万个提交的历史上,一次 rev-list --count 就要约 100 ms。

文件结构

实测 · 本机执行输出

  数全部提交                            99.0 ms
  log --topo-order -1              98.1 ms
  is-ancestor(25000 步之前)           82.0 ms
  merge-base                       67.7 ms

.git/objects/info/commit-graph 以 8 字节头(签名 CGPH、版本、哈希版本、块数、基础图数)开头,然后是块表。OIDF 与 OIDL 是提交 hash 的 fanout 和升序表,CDAT 每个提交 36 字节,GDA2 是修正世代数(提交时间的偏移)。

一条记录

实测 · 本机执行输出

  $ git commit-graph write --reachable; ls -l .git/objects/info/commit-graph | awk '{print $5, $9}'
  1819112 .git/objects/info/commit-graph
  签名 b'CGPH'  版本 1  哈希版本 1  块数 4  基础图数 0
  0000  43 47 50 48 01 01 04 00 4f 49 44 46 00 00 00 00  CGPH....OIDF....
  …(共 1819112 字节)
  块 OIDF  偏移       68  长度     1024
  块 OIDL  偏移     1092  长度   606000
  块 CDAT  偏移   607092  长度  1090800
  块 GDA2  偏移  1697892  长度   121200
  OIDF 末项 = 30,300 个提交(= git rev-list --all --count: 30300)

根 tree 的 hash、第一个 parent 和第二个 parent 的下标(指向 OIDL,不重复存 hash),以及合并在一起的世代数和提交时间。没有第二个 parent 时用占位值 0x70000000。多于两个 parent 的章鱼合并走另一个 EDGE 块(本例没有)。

世代数

实测 · 本机执行输出

  HEAD=efe5e65458…  下标 28418
  tree   9c3de550eb…(git 里是 9c3de550eb…)
  parent1 下标 11019 → 5c5c393a24…(git: 5c5c393a24…)
  parent2 下标 16529 → 8b7a5ffb26…(git: 8b7a5ffb26…)  HEAD 是合并提交
  对一个普通提交(HEAD^1~1)取 parent2 字段: 0x70000000(没有第二个 parent 时的占位值)
  提交时间 1767291900(git: 1767291900);世代数 30300
  世代数范围 1 ~ 30300;根提交的世代数 = 1

世代数是“比所有 parent 的最大世代数大 1”,根提交为 1。判断 A 是不是 B 的祖先时,如果 A 的世代数不比 B 小,就可以立刻判定不是,不必一路走到根。

快多少

实测 · 本机执行输出

  数全部提交                            99.0 →     15.3 ms   快 6.5 倍
  log --topo-order -1              98.1 →     11.6 ms   快 8.5 倍
  is-ancestor(25000 步之前)           82.0 →     14.5 ms   快 5.6 倍
  merge-base                       67.7 →     13.6 ms   快 5.0 倍

本例四个命令都快了 5.0~8.5 倍,剩下的 11~15 ms 大部分是进程启动。git gc 默认会写 commit-graph,也可以手动 git commit-graph write --reachable。

自动写

实测 · 本机执行输出

  $ ls .git/objects/info/; git gc -q; ls .git/objects/info/
  commit-graph
  packs
  $ git config gc.writeCommitGraph || echo "gc.writeCommitGraph 未显式设置(默认 true)"
  gc.writeCommitGraph 未显式设置(默认 true)

新仓库 git gc 之后目录里就有 commit-graph,说明 gc.writeCommitGraph 默认开启。

分步演示

commit-graph

本步的对象

本文用到的工具与边界

本机 macOS 27 arm64 / git 2.54.0(Apple Git-157);每个实验在临时目录里新建仓库,HOME 和全局配置指向实验专用的空目录(不读用户自己的 git 配置),提交的作者与时间固定以便复现;需要网络协议的实验用本机的 file:// 或 git daemon 回环端口(9800 以上),不碰任何远程仓库;计时用 time.perf_counter,数字每次运行会有小幅抖动。历史由 git fast-import 造出(每次提交只改 f.txt 一个文件,每 100 个提交一次合并);耗时是 5 次中位数,包含进程启动;commit-graph 文件由我按字节解析,对照 git rev-parse 与 git log;maintenance.auto 在实验环境里关闭
没有验证:增量 commit-graph(分层链,.git/objects/info/commit-graphs/);Bloom filter 块(git log -- path 的加速,commit-graph write --changed-paths);章鱼合并的 EDGE 块;fetch.writeCommitGraph 的行为;几十万以上提交的仓库;git log 带路径时的耗时

下一篇 · GIT 22

reachability bitmap