[PATCH v2 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits
Toon Claes <[email protected]>
| Newsgroups | org.kernel.vger.git |
|---|---|
| Message-ID | <[email protected]> |
We have received a report[1] git-last-modified(1) is slow compared to
git-log(1) if you want to find the last commit for all entries in a
directory. For example running the following command on ziglang/zig[2]:
$ git last-modified -t --max-depth=0 $OID -- doc/langref/
Turns out to find results about 2.5 times slower than:
$ git log --name-status -c --format=commit%x00%H %P%x00" \
--parents --no-renames -t -z $OID -- :(literal)doc/langref
Now the latter needs some post-processing to come to the same results,
the total solution still is faster than integrating
git-last-modified(1).
After some research we've discovered the Bloom filters aren't used
optimally. But it turns out the code powering git-log(1) can fairly easy
be reused. We do this in a few steps:
- Patch 1 & 2 prepare revision.[ch] to expose the helper to check if
revs maybe changes in Bloom filter.
- Patch 3 & 4 prepare a similar helper, but this one is needed when
git-last-modified(1) is called with `--show-trees`.
- Patch 5 uses these helpers in git-last-modified(1).
- Patch 6 is a bonus change, which optimizes when working with wildcard
pathspecs.
Below are benchmarks on the ziglang/zig repository for the
`doc/langref/` directory (with commit-graphs written using
`--changed-paths`):
Benchmark 1: master: last-modified -z -t
Time (mean ± σ): 61.9 ms ± 1.8 ms [User: 57.1 ms, System: 4.0 ms]
Range (min … max): 58.5 ms … 68.9 ms 150 runs
Benchmark 2: HEAD: last-modified -z -t
Time (mean ± σ): 31.8 ms ± 1.3 ms [User: 27.1 ms, System: 4.2 ms]
Range (min … max): 29.7 ms … 35.6 ms 150 runs
Benchmark 3: git log -t
Time (mean ± σ): 22.1 ms ± 1.2 ms [User: 16.7 ms, System: 5.0 ms]
Range (min … max): 20.1 ms … 26.6 ms 150 runs
Summary
git log -t ran
1.44 ± 0.10 times faster than HEAD: last-modified -z -t
2.80 ± 0.18 times faster than master: last-modified -z -t
Comparing HEAD to master, there is about 1.95x speedup on running `git
last-modified -z -t. `git log -t` is still slightly faster though.
But without `-t` the speedup is even bigger:
Benchmark 1: master: last-modified -z
Time (mean ± σ): 60.7 ms ± 4.5 ms [User: 56.5 ms, System: 3.8 ms]
Range (min … max): 57.5 ms … 96.2 ms 150 runs
Benchmark 2: HEAD: last-modified -z
Time (mean ± σ): 16.2 ms ± 1.4 ms [User: 13.3 ms, System: 2.7 ms]
Range (min … max): 13.9 ms … 20.4 ms 212 runs
Benchmark 3: git log (no -t)
Time (mean ± σ): 22.0 ms ± 3.7 ms [User: 16.8 ms, System: 4.9 ms]
Range (min … max): 18.7 ms … 37.6 ms 150 runs
Summary
HEAD: last-modified -z ran
1.35 ± 0.25 times faster than git log (no -t)
3.74 ± 0.42 times faster than master: last-modified -z
This makes sense because without `-t` we can use the Bloom filter more
optimally.
Similar timings are seen across a few other repositories (like GitLab's
monolith gitlab-org/gitlab).
[1]: https://lore.kernel.org/git/[email protected]/
[2]: https://codeberg.org/ziglang/zig
---
Changes in v2:
- Make the public helper revs_maybe_changed_in_bloom() return a bool
instead of a tristate.
- Keep the bloom_keyvecs_nr precondition before get_bloom_filter() and
return early from the key vector loop.
- Add commits 3 & 4 to add helper used with `--show-trees`.
- Use Bloom filter correctly with `--show-trees` and add test to prove.
- Rerun benchmarks to compare results with and without `--show-trees`.
- Link to v1: https://patch.msgid.link/[email protected]
---
Toon Claes (6):
revision: move bloom keyvec precondition into function
revision: expose check for paths maybe changed in Bloom filter
bloom: add helper to check if any key in a vector is present
revision: add Bloom check that includes parent directories
last-modified: check pathspec against Bloom filter first
last-modified: keep per-path Bloom filters for wildcard pathspecs
bloom.c | 12 +++++++++++
bloom.h | 11 ++++++++++
builtin/last-modified.c | 20 +++++++++++++++++++
revision.c | 52 +++++++++++++++++++++++++++++++++++++-----------
revision.h | 20 +++++++++++++++++++
t/t8020-last-modified.sh | 21 +++++++++++++++++++
6 files changed, 124 insertions(+), 12 deletions(-)
Range-diff versus v1:
1: dd152b3fd5 = 1: 961bf0c547 revision: move bloom keyvec precondition into function
2: 0e80ca2500 ! 2: 8d8eaea04f revision: expose check for paths maybe changed in Bloom filter
@@ Commit message
Expose the new function via revision.h so other builtins can reuse the
exact same filtering that `git log <pathspec>` performs.
+ The existing function check_maybe_different_in_bloom_filter() returns a
+ tristate value. This returns either:
+
+ * `-1` : No Bloom filter was used.
+ * `0` : The commit definitely did not change any of the paths.
+ * `1` : The commit maybe changed one of the paths.
+
+ These return values are used to keep count of false-positives. But
+ because the new function revs_maybe_changed_in_bloom() is not involved
+ in counting statistics, it returns a boolean value telling whether the
+ commit definitely did not change any of the paths, or maybe changed some
+ of them.
+
Signed-off-by: Toon Claes <[email protected]>
## revision.c ##
@@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *re
{
struct bloom_filter *filter;
- int result = 0;
--
-- if (!revs->bloom_keyvecs_nr)
-- return -1;
-+ int result;
- if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
+ if (!revs->bloom_keyvecs_nr)
return -1;
-
- filter = get_bloom_filter(revs->repo, commit);
--
- if (!filter) {
- count_bloom_filter_not_present++;
+@@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
return -1;
}
@@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *re
- result = bloom_filter_contains_vec(filter,
- revs->bloom_keyvecs[nr],
- revs->bloom_filter_settings);
-- }
-+ result = revs_maybe_changed_in_bloom(revs, filter);
-+ if (result < 0)
-+ return result;
-
- if (result)
- count_bloom_filter_maybe++;
-@@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
- return result;
- }
++ if (revs_maybe_changed_in_bloom(revs, filter)) {
++ count_bloom_filter_maybe++;
++ return 1;
+ }
-+int revs_maybe_changed_in_bloom(struct rev_info *revs,
-+ struct bloom_filter *filter)
-+{
-+ int result = 0;
-+
-+ if (!revs->bloom_keyvecs_nr)
-+ return -1;
-+
-+ for (size_t nr = 0; !result && nr < revs->bloom_keyvecs_nr; nr++) {
-+ result = bloom_filter_contains_vec(filter,
-+ revs->bloom_keyvecs[nr],
-+ revs->bloom_filter_settings);
-+ }
+- if (result)
+- count_bloom_filter_maybe++;
+- else
+- count_bloom_filter_definitely_not++;
++ count_bloom_filter_definitely_not++;
+
-+ return result;
++ return 0;
+}
+
++bool revs_maybe_changed_in_bloom(struct rev_info *revs,
++ struct bloom_filter *filter)
++{
++ if (!revs->bloom_keyvecs_nr || !filter)
++ return true;
++
++ for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
++ if (bloom_filter_contains_vec(filter,
++ revs->bloom_keyvecs[nr],
++ revs->bloom_filter_settings))
++ return true;
+
+- return result;
++ return false;
+ }
+
static int rev_compare_tree(struct rev_info *revs,
- struct commit *parent, struct commit *commit, int nth_parent)
- {
## revision.h ##
@@ revision.h: struct string_list;
@@ revision.h: void reset_revision_walk(void);
int prepare_revision_walk(struct rev_info *revs);
+/**
-+ * Take in a changed-path Bloom filter that belongs to a commit, and consult it
-+ * to see if it might have modified any of the paths in the `revs`.
-+ * The caller should look up `filter`, probably with get_bloom_filter().
++ * Consult a changed-path Bloom filter to determine if the commit to which the
++ * filter belongs might have changed any of the paths in the `revs`.
+ * prepare_revision_walk() needs to be called in advance to ensure
+ * pathspec key vectors are set up.
+ *
-+ * Returns -1 if no sensible answer could be given because of missing
-+ * preconditions (no pathspec key vectors).
-+ * Returns 0 if the commit definitely did not change any of the paths and 1 if
-+ * the commit maybe has changed one of them, although that might be a
-+ * false-positive.
++ * Returns false iff the commit definitely did not change any of the paths.
+ */
-+int revs_maybe_changed_in_bloom(struct rev_info *revs,
-+ struct bloom_filter *filter);
++bool revs_maybe_changed_in_bloom(struct rev_info *revs,
++ struct bloom_filter *filter);
+
/* Drain the commits linked list into the priority queue. */
void rev_info_commit_list_to_queue(struct rev_info *revs);
-: ---------- > 3: a2d2c47cd5 bloom: add helper to check if any key in a vector is present
-: ---------- > 4: b33ef3dfd1 revision: add Bloom check that includes parent directories
3: 378403d38d ! 5: f1f194d66d last-modified: check pathspec against Bloom filter first
@@ Commit message
pre-filter, paths are still checked one-by-one to only find those which
don't have a "last commit" yet.
+ With `--show-trees` the list holds more than the paths matching the
+ pathspec. It also holds each parent tree entry, up to the root. Each of
+ those can resolve to a different commit. Thus for the pathspec "a/b/c",
+ the list will also hold "a" and "a/b".
+
+ When a commit touches "a/other", that commit could be the last commit
+ for "a", but revs_maybe_changed_in_bloom() would discard it, because it
+ doesn't match the full pathspec.
+
+ Instead, when `--show-trees` is given, use
+ revs_maybe_changed_in_bloom_with_parents(), which indicates the commit
+ maybe changed any of the paths leading up to the path in the pathspec.
+
Signed-off-by: Toon Claes <[email protected]>
## builtin/last-modified.c ##
@@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm
if (!filter)
return true;
-+ if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)
-+ return false;
++ /*
++ * With --show-trees we also track the tree entries containing the
++ * paths, so a change to any of those parent directories matters too.
++ */
++ if (lm->show_trees) {
++ if (!revs_maybe_changed_in_bloom_with_parents(&lm->rev, filter))
++ return false;
++ } else {
++ if (!revs_maybe_changed_in_bloom(&lm->rev, filter))
++ return false;
++ }
+
hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
if (active && !bitmap_get(active, ent->diff_idx))
continue;
+
+ ## t/t8020-last-modified.sh ##
+@@ t/t8020-last-modified.sh: test_expect_success 'last-modified merge undoes changes' '
+ EOF
+ '
+
++test_expect_success 'last-modified with Bloom filters and --show-trees' '
++ test_when_finished rm -rf bloom &&
++ git init bloom &&
++ (
++ cd bloom &&
++ mkdir d &&
++ test_commit base-a d/a &&
++ test_commit base-b d/b &&
++ test_commit touch-a d/a &&
++ test_commit touch-b d/b &&
++
++ git commit-graph write --reachable --changed-paths &&
++ git -c core.commitGraph=false last-modified -t HEAD -- d/a \
++ >expect &&
++ git -c core.commitGraph=true last-modified -t HEAD -- d/a \
++ >actual &&
++
++ test_cmp expect actual
++ )
++'
++
+ test_expect_success 'cannot run last-modified on two commits' '
+ test_must_fail git last-modified HEAD HEAD~1 2>err &&
+ test_grep "last-modified can only operate on one commit at a time" err
4: 24884916d4 = 6: f313142134 last-modified: keep per-path Bloom filters for wildcard pathspecs
---
base-commit: 2c78326f810173a4f3aefd8021f1e07575412481
change-id: 20260716-toon-speed-up-last-modified-b04ea1f21831