performance - git rev-list 有什么替代品，因为这有时很慢？

Question

我有一个生产工具，它每分钟在一个大型 repo 上调用 git rev-list 10-30 次。我看到 git 响应时间变化很大，从大约 1 秒到多达 50 秒（在超时机制放弃 git 请求之前）。

git rev-list --pretty=raw 2ef9fa0d0fa4c34d57103a0545b3cc96c2552e6f..f5daa48ebcd3cc95a0df683f8c3a3ad64def4a6e

目标是查看这两个提交是否是祖先/后代，如果是，则两者中的哪一个是祖先。我打了一次这个电话，如果我得到输出我有我的答案，如果没有输出，我交换提交位置并再次运行。如果这次没有输出，那么他们就不是彼此的祖先/后代。

是否有另一种更有效的方法来查找此信息？如果涉及到它，即使是在 git 之外的某些结构中对提交树进行建模的建议也会受到赞赏。

谢谢。

score 1 · Accepted Answer

看git merge-base first-sha1 second-sha1。如果结果是第三个 sha1，则它们不是后代。否则，结果是老祖先。

但是，如果您可以在更高级别上描述一些工作流程，那么可能有一种更简单的方法，您可能不必依赖它。我写了这篇关于每个功能分支的文章：http: //dymitruk.com/blog/2012/02/05/branch-per-feature/它可能会给你一些想法。

score 0 · Accepted Answer

git merge-base（甚至git rev-list）会更快：

提交图（这里提到）
Git 2.20（2018 年第四季度）

那是因为两者都基于“提交可达”的概念。

当涉及指向未提交对象的引用（例如标签）时，最近的更新破坏了可达性算法，该问题已得到修复。

请参阅Derrick Stolee ( ) 的提交 4067a64、提交 b67f6b2（2018 年 9 月 21 日）、提交 6621c83（2018 年 8 月 28 日）和提交 6cc01743 （derrickstolee 2018 年 7 月 20 日）。
^{（由Junio C Hamano 合并 -- gitster--在提交 0f7ac90中，2018 年 9 月 24 日）}

commit-reach：采用can_all_from_reach

is_descendant_of以前用于in_merge_bases()检查提交是否可以到达提供列表中的任何提交的方法。这有两个性能问题：

在最坏的情况下，性能是二次的。

单个in_merge_bases()调用需要超越目标提交才能找到可能是合并基础的完整边界提交集。

该can_all_from_reach方法避免了这种二次行为，并且可以使用代数将搜索限制在目标提交之外。它需要对原型进行小的调整才能停止commit-date用作截止值，因为这种优化在这里不再合适。

由于in_merge_bases()使用paint_down_to_common()，is_descendant_of()自然会找到截止点以避免遍历整个提交图。由于我们希望始终返回正确的结果，因此我们不能min_commit_date使用can_all_from_reach. 然后，我们依靠代数来提供截止值。

由于不是所有的 repos 都会有一个提交图文件，我们也不会总是为一个提交图文件计算代数，所以创建一个新方法，generation_numbers_enabled()它检查提交图文件并查看文件中的第一个提交具有非零代数。如果我们没有代号，请使用旧的逻辑is_descendant_of()。

test-tool reach is_descendant_of使用以下输入的“”命令在 Linux 存储库的副本上测量性能：
A:v4.9
X:v4.10 X:v4.11 X:v4.12 X:v4.13 X:v4.14 X:v4.15 X:v4.16 X:v4.17 X.v3.0

请注意，此输入是为演示先前方法的二次性质而量身定制的，因为它将在检查 v4.1 之前计算 v4.9 与所有更高版本的合并基础。
Before: 0.26 s
After: 0.21 s
由于我们之前在该方法中使用了 is_descendant_of 方法ref_newer，因此我们还使用test-tool reach ref_newer带有此输入的 ' ' 测量了那里的性能：
A:v4.9
B:v3.19

Before: 0.10 s
After: 0.08 s
通过使用父 v3.19 添加新提交，我们测试了 ref_newer 的不可访问情况：
Before: 0.09 s
After: 0.08 s

在 Git 2.20（2018 年第四季度）之前，（实验性）提交图文件的生成迄今为止相当安静，尽管在一个有意义的大型存储库中需要相当长的时间。
用户现在将看到进度输出。

请参阅Ævar Arnfjörð Bjarmason ( ) 的提交 6b89a34（2018 年 9 月 19 日）和提交 1f7f557、提交 7b0f229 （avar 2018 年 9 月 17 日）。
帮助者：Martin Ågren martin.agren@gmail.com。
^{（由Junio C Hamano 合并gitster——在提交 36d767d中，2018 年 10 月 16 日）}

使用 Git 2.21（2019 年第一季度），进展将更加准确：

请参阅Ævar Arnfjörð Bjarmason ( ) 的提交 01ca387（2018 年 11 月 19 日）。帮助者：Derrick Stolee ( )。^（由^{Junio C Hamano 合并 --}^--^在^{d4c9027 提交中}^{，2019 年 1 月 14 日）}avar
derrickstolee
^gitster

commit-graph: 拆分close_reachable()进度输出

修改7b0f229 (" commit-graph write: add progress output", 2018-09-17) 中添加的进度输出，使其报告的总数不再高于提交总数。有关指出这一点的错误报告，
请参阅此线程。

当我添加这个时，我并不打算提供准确的计数，而只是有一些进度输出来向用户显示命令没有挂起。但由于我们显示的是数字，所以让它们准确无误。进度描述由 Derrick Stolee 提出。

如原始线程中所述，即使在相当大的存储库（例如 linux.git.
在我拥有超过 700 万次提交的测试存储库中，所有这些都显示出来。其中两个不会出现很长时间，但正如在未来证明中所指出的那样

并且（仍然是 Git 2.21，2019 年第一季度），在写出提交图文件时显示进度表的代码路径得到了改进。

请参阅Ævar Arnfjörð Bjarmason ( ) 的提交 49bbc57 、提交890226c、提交 e59c615、提交 7c7b8a7、提交 d9b1b30、提交 2894473、提交 53035c4（2019 年 1 月 19 日）。请参阅SZEDER Gábor ( ) 的 commit 857ba92 （ 2019 年 1 月 23 日）和commit 5af7417（2019 年 1 月 19 日）。^（由^{Junio C Hamano 合并 --}^--^在^{提交 e5eac57}^{中，2019 年 2 月 5 日）}avar
szeder
^gitster

commit-graph写：添加中间进度

Annotating[...]将进度输出添加到“ ”和“ ”之间的代码部分Computing[...]generation numbers。
在足够大的存储库上，这可能需要 5-10 秒。

在我拥有的测试存储库中，大约 700 万次提交和大约 5000 万个对象，我们现在将发出：
$ ~/g/git/git --exec-path=$HOME/g/git commit-graph write
Finding commits for commit graph among packed objects: 100% (124763727/124763727), done.
Loading known commits in commit graph: 100% (18989461/18989461), done.
Expanding reachable commits in commit graph: 100% (18989507/18989461), done.
Clearing commit marks in commit graph: 100% (18989507/18989507), done.
Counting distinct commits in commit graph: 100% (18989507/18989507), done.
Finding extra edges in commit graph: 100% (18989507/18989507), done.
Computing commit graph generation numbers: 100% (7250302/7250302), done.
Writing out commit graph in 4 passes: 100% (29001208/29001208), done.
而在中型存储库（linux.git例如

$ ~/g/git/git --exec-path=$HOME/g/git commit-graph write
Finding commits for commit graph among packed objects: 100% (6529159/6529159), done.
Expanding reachable commits in commit graph: 815990, done.
Computing commit graph generation numbers: 100% (815983/815983), done.
Writing out commit graph in 4 passes: 100% (3263932/3263932), done.

Git 2.24（2019 年第四季度）添加了一些修复程序以使其更快。

请参阅Jeff King ( ) 的提交 dd2e50a（2019 年 9 月 7 日）。请参阅SZEDER Gábor ( ) 的提交 67fa6aa（2019 年 9 月 7 日）。^（由^{Junio C Hamano 合并 --}^--^在^{提交 cda8faa}^{中，2019 年 10 月 7 日）}peff
szeder
^gitster

commit-graph：关掉save_commit_buffer

提交图工具可能会读取大量提交，但它只关心解析它们的元数据（父母、树等），而不会向用户显示消息。
所以它不应该需要save_commit_buffer，这是为了保存已解析提交的对象数据，以便我们稍后显示它们。事实上，这样做是非常有害的。
根据地块，在此补丁之前/之后（删除其间的提交图文件）中“ git commit-graph write --reachable”的最大堆linux.git从~1.1GB到~270MB.

这并不奇怪，因为差异是关于存储库中所有提交的未压缩大小的总和，这相当于泄漏它们。

如果您承受内存压力，这显然会有所帮助，但即使没有它，事情也会变得更快。
我对该命令（没有地块）的之前/之后时间从12.521s到11.874s，加速了~5%.

和：

commit-graph：在扩展可达提交时不显示进度百分比

提交49bbc57（提交图写入：为所有进度发出百分比，2019-01-19，Git v2.21.0-rc0）在“扩展提交图中的可访问提交”阶段添加进度百分比时有点过于急切了，因为在大多数情况下，该阶段必须迭代的提交数量是事先不知道的并且会显着增长，因此，我们最终会得到无意义的数字：
$ git commit-graph write --reachable
Expanding reachable commits in commit graph: 138606% (824706/595), done.
[...]

$ git rev-parse v5.0 | git commit-graph write --stdin-commits
Expanding reachable commits in commit graph: 81264400% (812644/1), done.
[...]
更糟糕的是，由于百分比增长得如此之快，进度代码输出的频率比它应该的要高得多（因为它每秒或每 1% 滴答一次），从而减慢了整个过程。
我在“ git commit-graph write --reachable”上的时间linux.git从这个补丁开始，13.463s节省了。12.521s~7%

因此，不要在“Expanding reachable commits in commit graph”阶段显示进度百分比。

Git 2.24（2019 年第四季度）增加了另一项优化。

请参阅Garima Singh ( ) 的提交 7371612（2019 年 8 月 26 日）。^（由^{Junio C Hamano 合并}^——^在^{提交 caf150c}^{中，2019 年 10 月 7 日）}singhgarima
^gitster

commit-graph: 添加--[no-]progress写入和验证

添加--[no-]progress到git commit-graph write和verify。
进度功能是在7b0f229 （“ commit-graph write：添加进度输出”，2018-09-17，Git v2.20.0-rc0）中引入的，但忽略了选择退出的能力。

在 Git 2.28（2020 年第三季度）中，“ git merge-base --is-ancestor”被教导利用提交图。

请参阅Derrick Stolee ( ) 的 commit 80b8ada和commit d91d6fb（2020 年 6 月 17 日）。^（由^{Junio C Hamano 合并 --}^--^在^{dc4b3cf 提交中}^{，2020 年 6 月 25 日）}derrickstolee
^gitster

commit-reach: 使用快速逻辑repo_in_merge_base

^{报告人：Ævar Arnfjörð Bjarmason}
^{报告人：SZEDER Gábor}
^{签字人：Derrick Stolee}

该repo_is_descendant_of()方法知道提交图文件的存在。它generation_numbers_enabled()在决定使用之前can_all_from_reach()或repo_in_merge_bases()根据情况进行检查。这里的原因是can_all_from_reach()使用深度优先搜索，该搜索受目标提交的最小代数限制，并且当代数不存在时，该算法可能会非常慢。替代用途paint_down_to_common()将遍历整个合并基础边界，这通常较慢。

当存在提交图文件时，此方法由“ git tag --contains”和“ ”等命令使用，以获得非常快的结果。不幸的是，它没有用在像“ ”这样的命令中，它正在执行一个更简单的请求。git branch --contains
git merge-base --is-ancestor

这个问题最近提出了关于如何存储代号的更改，但也早在存在之前就已报告过 commit-reach.c，以简化这些可达性查询。

根本原因是builtin/merge-base.c有一个方法handle_is_ancestor()调用in_merge_bases()，旧版本的repo_in_merge_bases(). 如果我们让每个调用者尽可能使用其中的逻辑，
那就更好了。in_merge_bases()can_all_from_reach()

这就是事情变得有点棘手的地方：在启用非代号的情况下repo_is_descendant_of()调用！repo_in_merge_bases()如果我们简单地更新repo_in_merge_bases()为 callrepo_is_descendant_of()而不是repo_in_merge_bases_many()，那么我们将得到一个递归调用循环。值得庆幸的是，测试套件在默认模式下（即GIT_TEST_COMMIT_GRAPH=0）捕获了这一点。

那么，诀窍是直接将非代号的大小写为repo_is_descendant_of()call repo_in_merge_bases_many()，跳过non-_many版本。这使我们能够在可能的情况下利用这种更快的代码路径。

衡量性能影响的最简单方法是在 Linux 内核存储库上测试以下命令：
git merge-base --is-ancestor <A> <B>

| A    | B    | Time Before | Time After |
|------|------|-------------|------------|
| v3.0 | v5.7 | 0.459s      | 0.028s     |
| v4.0 | v5.7 | 0.267s      | 0.021s     |
| v5.0 | v5.7 | 0.074s      | 0.013s     |
请注意，这些示例中的每一个都返回成功。旧代码在交换<A>和时执行相同的操作。但是，如果代号显示的代号大于，将立即返回。因此，在每种情况下，交换案例的时间普遍为 0.004 秒。<B>
can_all_from_reach()<A><B>

使用 Git 2.28（2020 年第三季度），is_descendant_of()不再使用：

请参阅Carlo Marcelo Arenas Belón ( ) 的提交 c1ea625（2020 年 6 月 23 日）。^（由^{Junio C Hamano 合并 --}^--^在^{提交 0258ed1}^{中，2020 年 7 月 6 日）}carenas
^gitster

commit-reach: 避免is_descendant_of()垫片

^{帮助者：Derrick Stolee}
^{签名者：Carlo Marcelo Arenas Belón}
^{审核者：Derrick Stolee}

d91d6fbf26 (" commit-reach: create repo_is_descendant_of()", 2020-06-17, Git v2.28.0-rc0 --批次 #5中列出的合并) 添加了一个存储库感知版本和一个几乎不使用的向后兼容性填充程序。is_descendant_of()

更新所有调用者以直接使用新repo_is_descendant_of()函数；使代码库更简单，并将更多the_repository引用推向更高的堆栈。

此外，在 Git 2.31（2021 年第一季度）之前，实现“ git merge-base --independent” ^（man）的代码做得很差，并且从该功能的一开始就保留了下来。

请参阅Derrick Stolee ( ) 的提交 41f3c99、提交 3677773、提交 c8d693e、提交 fbc21e3（2021 年 2 月 19 日）和提交 0fac156（2021 年 2 月 1 日）。^（由^{Junio C Hamano 合并 --}^--^在^{提交 48923e8}^{中，2021 年 2 月 25 日）}derrickstolee
^gitster

commit-reach: 使用启发式remove_redundant()

^{签字人：Derrick Stolee}

可达性算法commit-reach.c经常受益于使用第一父历史作为满足可达性查询的启发式方法。
最明显的例子是在4fbcca4中实现的（“ commit-reach：make can_all_from_reach...
linear”，2018-07-20，Git v2.20.0-rc0 --批次 #1中列出的合并）。

更新步入remove_redundant()以使用相同的启发式。
在这里，我们从输入提交的父节点开始。
对这些父母进行排序，然后从最高一代走向更低的一代。
每次，在继续扩展游走之前，使用启发式搜索第一个父历史。

我们探索提交的顺序很重要，因此更新compare_commits_by_gen以打破世代编号与提交日期的联系。
当提交位于计算了更正提交日期的提交图文件中时，这无效，但当提交位于具有“无限”代数的提交图“上方”区域时，它将有所帮助。
请注意，我们不能转移到使用compare_commits_by_gen_then_commit_date，因为方法原型不同。
我们使用compare_commits_by_genforQSORT()而不是作为优先级函数。

重要的一点是确保当我们发现有一个非冗余提交时，我们可以将遍历短路。
在寻找合并基础或将多个标签与 ' git merge-base --independent' ^{( man )}进行比较时，这种情况经常发生。
使用新的计数“ count_still_independent”，如果达到 1，我们可以停止行走。

为了正确更新“ count_still_independent”，我们在输入提交上添加了 RESULT 标志的使用。
然后我们可以检测何时达到这些提交之一并减少计数。
那时我们需要删除 RESULT 标志，因为我们可能会在弹出堆栈时重新访问该提交。

我们使用 STALE 标志来标记已添加到新walk_start列表中的父母，但我们需要在开始行走之前清除该标志，这样这些标志就不会停止我们的深度优先搜索行走。

在我的 Linux 内核存储库副本中，“ git merge-base --independent”的性能<all-tags>从 1.1 秒变为 0.11 秒。

在 Git 2.31（2021 年第一季度）中，处理多包索引和提交图文件共享的“分块文件格式”的通用代码已被分解，以帮助两种文件类型的代码路径变得更加健壮。

请参阅Taylor Blau ( ) 的提交 c4ff24b（2021 年 2 月 24 日）。请参阅提交A43A2E6，提交329FAC3，提交6ab3b8b，提交2692c2f，提交5f087f，commit 63a8f0e，commit c144241 ，提交0ccd713，提交 980f525，commit 7a3a，提交31bda9a ，提交b4d9414，提交577dc49，提交570df42，提交570df42（18 2021 年 2 月），以及ttaylorr
由Derrick Stolee ( )derrickstolee提交 eb90719（2021 年 2 月 5 日）。
^{（由Junio C Hamano 合并 -- gitster--在提交 660dd97中，2021 年 3 月 1 日）}

commit-graph.c: 写入时显示正确的块数

^{报道人：SZEDER Gábor 署名}
^{者：Taylor Blau}
^{署名者：Derrick Stolee}

编写提交图时，会显示一个进度表，指示要写入的数据条数（每个块中的每个提交一个）。

在47410aa (" commit-graph: use chunk-format write API", 2021-02-18, Git v2.32.0 -- merge ) 中，新的 chunk-format API 会跟踪块的数量。但是，当用于跟踪相同的情况
时，会留下一个杂散的局部变量。write_commit_graph_file()

由于在47410aa之后不再更新，因此进度表出现损坏：
$ git commit-graph write --reachable
Expanding reachable commits in commit graph: 837569, done.
Writing out commit graph in 3 passes: 166% (4187845/2512707), done.
删除局部变量并依赖块格式 API 来告诉我们正确的块数。

performance - git rev-list 有什么替代品，因为这有时很慢？

2 回答 2

`commit-reach`：采用`can_all_from_reach`

`commit-graph`: 拆分`close_reachable()`进度输出

`commit-graph`写：添加中间进度

`commit-graph`：关掉`save_commit_buffer`

`commit-graph`：在扩展可达提交时不显示进度百分比

`commit-reach`: 使用快速逻辑`repo_in_merge_base`

`commit-reach`: 避免`is_descendant_of()`垫片

`commit-reach`: 使用启发式`remove_redundant()`

`commit-graph.c`: 写入时显示正确的块数

performance - git rev-list 有什么替代品，因为这有时很慢？

2 回答 2

commit-reach： 采用can_all_from_reach

commit-graph: 拆分close_reachable()进度输出

commit-graph写：添加中间进度

commit-graph： 关掉save_commit_buffer

commit-graph：在扩展可达提交时不显示进度百分比

commit-reach: 使用快速逻辑repo_in_merge_base

commit-reach: 避免is_descendant_of()垫片

commit-reach: 使用启发式remove_redundant()

commit-graph.c: 写入时显示正确的块数

Related

Reference

`commit-reach`：采用`can_all_from_reach`

`commit-graph`: 拆分`close_reachable()`进度输出

`commit-graph`写：添加中间进度

`commit-graph`：关掉`save_commit_buffer`

`commit-graph`：在扩展可达提交时不显示进度百分比

`commit-reach`: 使用快速逻辑`repo_in_merge_base`

`commit-reach`: 避免`is_descendant_of()`垫片

`commit-reach`: 使用启发式`remove_redundant()`

`commit-graph.c`: 写入时显示正确的块数