]> git.ipfire.org Git - thirdparty/git.git/commit
last-modified: use Bloom filters when available
authorToon Claes <toon@iotcl.com>
Tue, 5 Aug 2025 09:33:58 +0000 (11:33 +0200)
committerJunio C Hamano <gitster@pobox.com>
Thu, 28 Aug 2025 23:44:58 +0000 (16:44 -0700)
commit8d9a7cdfda4c883e83d6ea7b57d0a1d989a7d439
treeff72d2ff3a66f13c891130f22bcd275acd340850
parent97d5301c54152d91a4e47449f759567f83140d4f
last-modified: use Bloom filters when available

Our 'git last-modified' performs a revision walk, and computes a diff at
each point in the walk to figure out whether a given revision changed
any of the paths it considers interesting.

When changed-path Bloom filters are available, we can avoid computing
many such diffs. Before computing a diff, we first check if any of the
remaining paths of interest were possibly changed at a given commit by
consulting its Bloom filter. If any of them are, we are resigned to
compute the diff.

If none of those queries returned "maybe", we know that the given commit
doesn't contain any changed paths which are interesting to us. So, we
can avoid computing it in this case.

Comparing the perf test results on git.git:

    Test                                        HEAD~             HEAD
    ------------------------------------------------------------------------------------
    8020.1: top-level last-modified             4.49(4.34+0.11)   2.22(2.05+0.09) -50.6%
    8020.2: top-level recursive last-modified   5.64(5.45+0.11)   5.62(5.30+0.11) -0.4%
    8020.3: subdir last-modified                0.11(0.06+0.04)   0.07(0.03+0.04) -36.4%

Based-on-patch-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Toon Claes <toon@iotcl.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/last-modified.c
commit-graph.c