我编写了一个工具，它使用git rev-list -n1 --before=X使用固定的时间间隔迭代 Git 提交历史记录，以便我看到每年、每月等的最新修订版。
问题是，rev-list每次打电话都会开始新的修订，父亲回来需要更长的时间。以下是来自 Linux 内核源代码的一些示例。
$ time git rev-list -n1 --before="Jan 1 2016" HEAD
a889331d759453fa7f424330f75ae4e2b9e02db4
real 0m1.395s
user 0m1.367s
sys 0m0.024s
$ time git rev-list -n1 --before="Jan 1 2015" HEAD
5b5e76218fbdbb71a01d5480f289ead624232876
real 0m2.349s
user 0m2.306s
sys 0m0.036s
$ time git rev-list -n1 --before="Jan 1 2005" HEAD
real 0m5.556s
user 0m5.435s
sys 0m0.105s
如果我想在 N 个递减日期的循环中调用rev-list，该循环将运行 N 次遍历，每次迭代都需要更长的时间。文档讨论了位图和对象遍历策略以加快历史记录，但我很难理解它们。我尝试了git repack -ab然后是git rev-list --use-bitmap-index，但这并没有改善结果。
我唯一的要求是，给定HEAD的任何位置，我可以准确地确定在给--before日期之前出现的第一个修订版，如果需要，可以遵循祖先的路径。
对于此用例，提高rev-list速度的最佳方法是什么？
重复扫描列表以选择连续元素是 O(N^2)。 扫描效率有多高并不重要，N^2 会咬人。
生成一个包含提交 ID 和日期的列表，然后删除您不想要的内容并从选定的 sha 生成真实的日志消息。总共是三遍，而不是 N。
git log --first-parent --pretty=%H %cd --date=short
| awk '$2$3 != last { last=$2$3; print $1}' 'FS=[- ]'
| git log --no-walk --stdin
这花了十五秒在 linux 存储库上的冷缓存，使用一个旋转的东西 hdd，列出了 147 个提交。 重播只用了不到一秒钟。
编辑：--date-orderSubbing for--first-parent考虑所有路径需要 25.1 秒冷缓存，7.9 秒热，列出 782 个提交。
在一般情况下，除了这两个选项之外别无选择：
- 支付步行的全部费用，或
- 存储的信息比只请求一个节点时
git rev-list发出的信息要多得多
因为图漫游有效地线性化(通过优先级队列，以日期作为优先级)任意灌木丛的树(这个"树"是通过切断重新连接形成的，只需不重新访问 DAG 中的任何已经访问过的节点)。 例如，假设我们有一个非常像这样的提交 DAG。 假设所有方向弧都指向左边(直接向左，或向上和向左，或向下和向左)。
A-....--o
/
...--o----...----o <-- HEAD
/
B--...--o
在任何地方都有任意数量的节点的地方，有两个或三个点。 您的某个选择可能会选择节点A作为第一个访问的符合--before条件的节点。 节点B可能早于A，因此可能是从HEAD开始的早期--before选择的节点(因为节点B可以从HEAD访问)。 但是节点B是无法从节点A到达的，所以简单地从节点A开始，你永远不会找到节点B。
如果您以某种方式git rev-list转储其当前的优先级队列内容(以及有关它迄今为止访问过的所有节点的信息 - 尽管最终不需要获得相同的结果;这只是可能加速一些节点修剪的选项)您可以从这些点重新启动其图形步行操作以搜索B， 从而避免重新访问上面大网格-y区域中的许多节点。
但是，如果您强烈限制图形漫游，例如，使用--first-parent，您可以简单地从最近找到的提交重新启动漫游，因为您知道队列深度始终为 1，因此下一个要访问的节点是您之前找到的节点的第一个父节点(您可以将其留给git rev-list)。
您可以重试相同的命令，添加新的--filter=tree:0选项。这应该可以加快所需提交列表的制作。
这是因为在Git 2.20(2018年第四季度)中，"rev-list --filter"功能学会了通过"tree:0"过滤器排除所有树。
请参阅提交 8b10a20(2018 年 10 月 18 日)、提交 d9e6d09(2018 年 10 月 12 日)、提交 bc5975d、提交 cc0b05a、提交 696aa73、提交 99c9aa9、提交 7c0fe33(2018 年 10 月 5 日)、提交 f1d02da(2018 年 8 月 15 日)和提交9202489，提交 f447a49(2018 年 8 月 13 日)，作者：Matthew DeVore (matvore).
(由 Junio C Hamano --gitster-- 合并于 提交 77d5037,2018 年 10 月 30 日)
list-objects：支持跳过树遍历
tree:0过滤器不需要遍历它拥有的树 过滤掉，所以优化列表对象和列表对象过滤器以跳过 完全穿越树木。
列表对象过滤器：实现过滤器树：0
示教列表对象"
tree:0"过滤器，允许过滤 输出所有树和 blob 对象(除非其他对象显式 由用户指定)。此修补程序的目的是允许较小的 部分克隆。此筛选器的名称 -
tree:0- 未明确指定它还会过滤掉所有 blob，但这应该不会引起太多混淆 因为如果没有引用的树，blob 根本没有用 他们。我也认为
only:commits是一个名字，但这是不准确的，因为 它表明省略了带注释的标签，但实际上它们是 包括。名称"
tree:0"允许以后根据深度进行过滤，即"tree:1" 将过滤掉除根树和 blob 之外的所有内容.
为了避免 0 和大写字母 O 之间的混淆，文档的措辞有点迂回，这也暗示了该功能的未来改进。
请注意，Git 2.22(2019 年第 2 季度)将修复回归，其中"is this object available to us?"检查 众所周知的对象，如一棵空树(应该产生"是"， 即使磁盘上没有空树的对象)，也有 已更正。
参见 提交 f06ab02 (04 Mar 2019) by Jeff King (peff).
(由 Junio C Hamano --gitster-- 合并于 commit 83b13e2， 20 Mar 2019)
rev-list：允许缓存对象存在检查
这修复了 7c0fe33 中的回归(修订列表：处理缺少的树 对象正确，2018-10-05)，
rev-list现在将抱怨 当磁盘上不存在物理时为空树。在提交之前，我们依靠遍历代码
list-objects.c穿过树林。由于它使用parse_tree()，我们会做一个正常的 对象查找，包括在一组"缓存"对象中查找 (这就是我们的魔法内部空树发挥作用的地方)。在那次承诺之后，我们反而告诉
list-objects.c不要死在任何 缺少树木，我们使用has_object_file()自己检查它们。但 该函数使用OBJECT_INFO_SKIP_CACHED，这意味着我们不会使用我们的 内部空树。这通常不会出现。对于大多数操作，Git 将尝试 像写出任何其他对象一样写出空树对象。和
push或fetch中的pack-objects将发送空树(即使它是 虚拟在发送端).
但是，在某些情况下，这可以 事。我在野外发现的一个：
通过删除所有文件(不使用索引)，提交的根树变为空。在这种情况下，它是使用 libgit2 的树构建器 API 完成的，但正如包含的测试所示，可以使用 hash-object.
的常规 git 轻松完成，生成的存储库工作正常，因为我们会避免走过我们自己的可访问提交进行连接检查。使用
--reference指向 (1) 中的存储库进行克隆可能会触发问题，因为我们告诉另一方我们已经有了该提交(因此是空树)，但在连接检查期间(我们抱怨它丢失)。可以说，步骤 (1) 中的工作流在编写时应该更加小心 空树对象(如果我们引用它)。但这个工作流程确实做到了 在 7c0fe33 之前工作，所以让我们恢复它。
Git 2.22 中修复的另一个回归：在对象的位置出现"错误"的对象 期望不同类型的，而不是盲目地假设 对象之间的连接已正确建立。
请参阅提交 b49e74e、提交 23c2044、提交 0616617(2019 年 4 月 10 日)和提交 5c07647(2019 年 4 月 5 日)，作者：Taylor Blau (ttaylorr).
参见提交 97dd512、提交 ee4dfee、提交 8348766 (2019 年 4 月 10 日)由 Jeff King (peff).
(由 Junio C Hamano --gitster-- 合并于 提交 ea2dab1,2019 年 5 月 8 日)
修订列表：当 --missing 未使用时让遍历死亡
提交 7c0fe33 (
rev-list：正确处理缺少的树对象， 2018-10-05，Git v2.20.0-rc0)教导git-rev-list使用的遍历机制忽略缺失的树，以便rev-list可以自己处理它们。但是，它只能通过
oid_object_info_extended()检查 对象完全存在.
这可能会错过以前由rev-list检测到的几类错误：
类型不匹配(例如，我们期望一棵树，但得到了一个斑点)
无法读取对象数据(例如，由于磁盘上的 Bitrot)
这一点尤其重要，因为我们使用"
rev-list --objects"作为我们的 连接性检查以允许新对象进入存储库，它将 现在错过这些情况(尽管Bitrot在这里不太重要， 因为我们通常只是散列并存储对象)。
Git 2.23(2019 年第 3 季度)修复了另一个错误：list-objects-filter(管理懒惰稀疏克隆存储库)中使用的filter_data没有正确使用动态数组 API---'nr' 应该指向最后一个元素 正在使用的阵列。
参见 commit 7140600 (2019 年 5 月 31 日) by Matthew DeVore (matvore).
(由 Junio C Hamano --gitster-- 合并于 commit 34032c4， 21 Jun 2019)
list-objects-filter：正确使用ALLOC_GROW
在稀疏筛选器数据中，
array_frame数组的使用方式如下：nr是最后一个元素的索引.
修复此问题，以便nr实际上是数组中元素的数量。
filter_sparse_free函数还具有未寻址TODO，用于释放 与稀疏筛选器 data 关联的内存.
解决TODO并修复内存泄漏的问题。
在 Git 2.24(2019 年第 4 季度)中，存储稀疏克隆/提取的筛选器规范的 blob 对象的名称在 代码，导致 Git 中止：此问题已修复。
参见 提交 a4cafc7，提交 4c96a77 (2019 年 9 月 15 日) by Jeff King (peff).
参见提交 cf34337， 提交 72de589 (2019 年 9 月 15 日) by Jon Simons (simonsj).
(由 Junio C Hamano --gitster-- 合并于 提交 ad8f036， 07 Oct 2019
Git 2.24(2019 年第 4 季度)将使对象遍历更快！
它已经过优化，当我们只对提交历史记录感兴趣时，不加载树对象。
参见 提交 72ed80c (2019 年 9 月 12 日) by Jeff King (peff).
(由 Junio C Hamano 合并 --gitster-- 在提交 bbfe5f2， 07 Oct 2019
list-objects：除非设置了revs->tree_objects否则不要对根树进行排队
当
traverse_commit_list()处理每个提交时，它会将提交的根树排队到挂起的数组中。
然后，在处理完所有提交后，它会调用traverse_trees_and_blobs()遍历挂起列表，在每个列表中调用process_tree()。
但是，如果未设置revs->tree_objects，process_tree()就会立即存在！我们甚至可以通过首先不费心对这些树进行排队来节省一些工作.
我们还在这里检测带有 NULL 树指针的提交.
有几个微妙的要点需要说明：
但这不是对损坏提交的有趣检查，因为我们在提交解析期间所做的
lookup_tree()实际上并没有检查磁盘上是否有树.
所以我们没有失去任何健壮性。除了排队之外，我们还在树对象上设置了
NOT_USER_GIVEN标志.
这是由traverse_commit_list_filtered()变体使用的.
但是如果我们不探索树，那么我们实际上不会关心这个标志，它只在process_tree()代码路径中使用。排队树最终也会导致我们对 blob 进行排队。
但我们不需要在这里check revs->blob_objects。
即使在当前代码中，我们仍然找不到这些 blob，因为我们永远不会打开树对象来列出它们的内容。用户对调用方的可见影响很小.
挂起的树在函数返回时全部清除，无论如何，通过traverse_trees_and_blobs().
我们确实调用了一个show_commit()回调，从技术上讲，它可以在回调期间查看revs->pending.
但这似乎是一件不太可能的事情(如果你想要当前提交的树， 然后访问树结构成员就简单得多了)。所以这应该是安全的。
让我们看看好处：
[before] Benchmark #1: git -C linux rev-list HEAD >/dev/null Time (mean ± σ): 7.651 s ± 0.021 s [User: 7.399 s, System: 0.252 s] Range (min … max): 7.607 s … 7.683 s 10 runs [after] Benchmark #1: git -C linux rev-list HEAD >/dev/null Time (mean ± σ): 7.593 s ± 0.023 s [User: 7.329 s, System: 0.264 s] Range (min … max): 7.565 s … 7.634 s 10 runs不太令人印象深刻，但我们实际上只是避免将指针插入可增长的数组.
但是，我仍然会免费获得 0.75% 的加速。运行"
git commit-graph write"后让我们尝试一下：[before] Benchmark #1: git -C linux rev-list HEAD >/dev/null Time (mean ± σ): 1.458 s ± 0.011 s [User: 1.199 s, System: 0.259 s] Range (min … max): 1.447 s … 1.481 s 10 runs [after] Benchmark #1: git -C linux rev-list HEAD >/dev/null Time (mean ± σ): 1.126 s ± 0.023 s [User: 896.5 ms, System: 229.0 ms] Range (min … max): 1.106 s … 1.181 s 10 runs现在更像是这样了。我们节省了超过 22% 的总时间.
部分原因是运行时间总体上较短，但绝对 改进也大得多.
这是怎么回事？当我们使用 commit graph 填写提交结构时，我们不会费心设置树指针，而是在有人调用 .
时延迟加载它get_commit_tree()所以我们不仅跳过了指针写入挂起队列，而且我们完全跳过了树的延迟加载。
请注意，在 Git 2.34(2021 年第 4 季度)中，方法traverse_trees_and_blobs已重命名为traverse_non_commits。
参见提交 b3e36df (2021 年 8 月 12 日) 滕龙 (dyrone).
(由 Junio C Hamano 合并 --gitster-- 在提交 0d4f46b 中，2021 年 8 月 30 日)
list-objects.c： 将"traverse_trees_and_blobs"重命名为"traverse_non_commits"签约人：滕龙
函数
traverse_trees_and_blobs不仅适用于树和 blob，也适用于标记，函数名称有些误导.
此提交将其重命名为traverse_non_commits.
Git 2.39(2022 年第 4 季度)包括检查可疑 blob 对象是否存在时的parse_object()强化。
参见 提交 8db2dad，提交 04fb962(2022 年 11 月 17 日)，作者：Jeff King (peff).
参见提交 40286ca (2022 年 11 月 21 日)，作者：Ævar Arnfjörð Bjarmason (avar).
(由 Junio C Hamano --gitster-- 合并于 提交 ba88f8c，2022 年 11 月 28 日)
parse_object()：检查可疑 Blob 的磁盘类型签名者：杰夫·金
签名者：泰勒·布劳
在
parse_object()中，我们尝试通过流式处理blob，而不是将它们完全加载到内存中.
这里最常见的情况是我们还没有看到对象并检查oid_object_info()，这告诉我们我们有一个blob。但是我们在另一种情况下触发此代码：当我们有一个类型为
OBJ_BLOB的内存中对象结构时(并且没有设置其"解析"标志，因为否则我们会提前从函数返回).
这表明代码的其他部分怀疑我们有一个 blob(例如，它被树或标签提及)，但我们还没有查看磁盘副本。我对条件进行了一些修改，以便代替：
if ((suspected_blob && oid_object_info() == OBJ_BLOB) (no_clue && oid_object_info() == OBJ_BLOB)我们有更简单的：
if ((suspected_blob || no_clue) && oid_object_info() == OBJ_BLOB)这更短，但也反映了我们真正想说的话，即"我们是否排除这是一个 blob;如果没有，请在磁盘上检查它"。
因此，这修复了0616617中挥之不去的
expect_failure情况之一("t：引入意外对象类型的测试"，2019-04-09，Git v2.22.0-rc0 - 合并在批处理#8中列出)。在此提交之前，我们会悄悄检查 sha1 并将 blob 标记为"parsed".
现在我们正确地抱怨不匹配("hash mismatch")。