| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
The current implementation of git-last-modified(1) works by doing a
revision walk, and inspecting the diff at each level of that walk to
annotate entries remaining in the hashmap of paths. In other words, if
the diff at some level touches a path which has not yet been associated
with a commit, then that commit becomes associated with the path.
While a perfectly reasonable implementation, it can perform poorly in
either one of two scenarios:
1. There are many entries of interest, in which case there is simply
a lot of work to do.
2. Or, there are (even a few) entries which have not been updated in a
long time, and so we must walk through a lot of history in order to
find a commit that touches that path.
This patch rewrites the last-modified implementation that addresses the
second point. The idea behind the algorithm is to propagate a set of
'active' paths (a path is 'active' if it does not yet belong to a
commit) up to parents and do a truncated revision walk.
The walk is truncated because it does not produce a revision for every
change in the original pathspec, but rather only for active paths.
More specifically, consider a priority queue of commits sorted by
generation number. First, enqueue the set of boundary commits with all
paths in the original spec marked as interesting.
Then, while the queue is not empty, do the following:
1. Pop an element, say, 'c', off of the queue, making sure that 'c'
isn't reachable by anything in the '--not' set.
2. For each parent 'p' (with index 'parent_i') of 'c', do the
following:
a. Compute the diff between 'c' and 'p'.
b. Pass any active paths that are TREESAME from 'c' to 'p'.
c. If 'p' has any active paths, push it onto the queue.
3. Any path that remains active on 'c' is associated to that commit.
This ends up being equivalent to doing something like 'git log -1 --
$path' for each path simultaneously. But, it allows us to go much faster
than the original implementation by limiting the number of diffs we
compute, since we can avoid parts of history that would have been
considered by the revision walk in the original implementation, but are
known to be uninteresting to us because we have already marked all paths
in that area to be inactive.
To avoid computing many first-parent diffs, add another trick on top of
this and check if all paths active in 'c' are DEFINITELY NOT in c's
Bloom filter. Since the commit-graph only stores first-parent diffs in
the Bloom filters, we can only apply this trick to first-parent diffs.
Comparing the performance of this new algorithm shows about a 2.5x
improvement on git.git:
Benchmark 1: master no bloom
Time (mean ± σ): 2.868 s ± 0.023 s [User: 2.811 s, System: 0.051 s]
Range (min … max): 2.847 s … 2.926 s 10 runs
Benchmark 2: master with bloom
Time (mean ± σ): 949.9 ms ± 15.2 ms [User: 907.6 ms, System: 39.5 ms]
Range (min … max): 933.3 ms … 971.2 ms 10 runs
Benchmark 3: HEAD no bloom
Time (mean ± σ): 782.0 ms ± 6.3 ms [User: 740.7 ms, System: 39.2 ms]
Range (min … max): 776.4 ms … 798.2 ms 10 runs
Benchmark 4: HEAD with bloom
Time (mean ± σ): 307.1 ms ± 1.7 ms [User: 276.4 ms, System: 29.9 ms]
Range (min … max): 303.7 ms … 309.5 ms 10 runs
Summary
HEAD with bloom ran
2.55 ± 0.02 times faster than HEAD no bloom
3.09 ± 0.05 times faster than master with bloom
9.34 ± 0.09 times faster than master no bloom
In short, the existing implementation is comparably fast *with* Bloom
filters as the new implementation is *without* Bloom filters. So, most
repositories should get a dramatic speed-up by just deploying this (even
without computing Bloom filters), and all repositories should get faster
still when computing Bloom filters.
When comparing a more extreme example of
`git last-modified -- COPYING t`, the difference is even 5 times better:
Benchmark 1: master
Time (mean ± σ): 4.372 s ± 0.057 s [User: 4.286 s, System: 0.062 s]
Range (min … max): 4.308 s … 4.509 s 10 runs
Benchmark 2: HEAD
Time (mean ± σ): 826.3 ms ± 22.3 ms [User: 784.1 ms, System: 39.2 ms]
Range (min … max): 810.6 ms … 881.2 ms 10 runs
Summary
HEAD ran
5.29 ± 0.16 times faster than master
As an added benefit, results are more consistent now. For example
implementation in 'master' gives:
$ git log --max-count=1 --format=%H -- pkt-line.h
15df15fe07ef66b51302bb77e393f3c5502629de
$ git last-modified -- pkt-line.h
15df15fe07ef66b51302bb77e393f3c5502629de pkt-line.h
$ git last-modified | grep pkt-line.h
5b49c1af03e600c286f63d9d9c9fb01403230b9f pkt-line.h
With the changes in this patch the results of git-last-modified(1)
always match those of `git log --max-count=1`.
One thing to note though, the results might be outputted in a different
order than before. This is not considerd to be an issue because nowhere
is documented the order is guaranteed.
Based-on-patches-by: Derrick Stolee <stolee@gmail.com>
Based-on-patches-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Toon Claes <toon@iotcl.com>
Acked-by: Taylor Blau <me@ttaylorr.com>
[jc: tweaked use of xcalloc() to unbreak coccicheck]
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
In e6c06e87a2 (last-modified: fix bug when some paths remain unhandled,
2025-09-18), we have fixed a bug where under certain circumstances,
git-last-modified(1) would BUG because there's still some unhandled
paths. The fix claims that the root cause here is criss-cross merges,
and it adds a test case that seemingly exercises this.
Curiously, this test case fails on some systems because the actual
output does not match our expectations:
diff --git a/expect b/actual
index 5271607..bdc620e 100644
--- a/expect
--- b/actual
@@ -1,3 +1,3 @@
km3 a
-k2 k
+km2 k
1 file
error: last command exited with $?=1
not ok 15 - last-modified with subdir and criss-cross merge
The output we see is git-name-rev(1) with `--annotate-stdin`. What it
does is to take the output of git-last-modified(1), which contains
object IDs of the blamed commits, and convert those object IDs into the
names of the corresponding tags. Interestingly, we indeed have both "k2"
and "km2" as tags, and even more interestingly both of these tags point
to the same commit. So the output we get isn't _wrong_, as the tags are
ambiguous.
But why do both of these tags point to the same commit? "km2" really is
supposed to be a merge, but due to the way the test is constructed the
merge turns into a fast-forward merge. Which means that the resulting
commit-graph does not even contain a criss-cross merge in the first place!
A quick test though shows that the test indeed triggers the bug, so
the initial analysis that the behaviour is triggered by such merges
must be wrong.
And it is: seemingly, the issue isn't with criss-cross merges, but
rather with a graph where different files in the same directory were
modified on both sides of a merge.
Refactor the test so that we explicitly test for this specific situation
instead of mentioning the "criss-cross merge" red herring. As the test
is very specific to the actual layout of the repository we also adapt it
to use its own standalone repository.
Note that this requires us to drop the `test_when_finished` call in
`check_last_modified` because it's not supported to execute that
function in a subshell.
This refactoring also fixes the original tag ambiguity that caused us to
fail on some platforms.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The recently introduced new subcommand git-last-modified(1) runs into an
error in some scenarios. It then would exit with the message:
BUG: paths remaining beyond boundary in last-modified
This seems to happens for example when criss-cross merges are involved.
In that scenario, the function diff_tree_combined() gets called.
The function diff_tree_combined() copies the `struct diff_options` from
the input `struct rev_info` to override some flags. One flag is
`recursive`, which is always set to 1. This has been the case since the
inception of this function in af3feefa1d (diff-tree -c: show a merge
commit a bit more sensibly., 2006-01-24).
This behavior is incompatible with git-last-modified(1), when called
non-recursive (which is the default).
The last-modified machinery uses a hashmap for all the paths it wants to
get the last-modified commit for. Through log_tree_commit() the callback
mark_path() is called. The diff machinery uses diff_tree_combined()
internally, and due to it's recursive behavior the callback receives
entries inside subtrees, but not the subtree entries themselves. So a
directory is never expelled from the hashmap, and the BUG() statement
gets hit.
Because there are many callers calling into diff_tree_combined(), both
directly and indirectly, we cannot simply change it's behavior.
Instead, add a flag `no_recursive_diff_tree_combined` which supresses
the behavior of diff_tree_combined() to override `recursive` and set
this flag in builtin/last-modified.c.
Signed-off-by: Toon Claes <toon@iotcl.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Similar to git-blame(1), introduce a new subcommand
git-last-modified(1). This command shows the most recent modification to
paths in a tree. It does so by expanding the tree at a given commit,
taking note of the current state of each path, and then walking
backwards through history looking for commits where each path changed
into its final commit ID.
Based-on-patch-by: Jeff King <peff@peff.net>
Improved-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Toon Claes <toon@iotcl.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
