"Derrick Stolee via GitGitGadget" [off-list ref] writes:
The important piece is to ensure we short-circuit the walk when we find
that there is a single non-redundant commit. This happens frequently
when looking for merge-bases or comparing several tags with 'git
merge-base --independent'. Use a new count 'count_still_independent' and
if that hits 1 we can stop walking.
That is because when you are left one single thing, it may be able
to reach many other things, but the fact that it by itself won't be
reachable by remaining independent things will not change (because,
that sole remaining independent thing is itself)?
To update 'count_still_independent' properly, we add use of the RESULT
flag on the input commits. Then we can detect when we reach one of these
commits and decrease the count. We need to remove the RESULT flag at
that moment because we might re-visit that commit when popping the
stack.
We use the STALE flag to mark parents that have been added to the new
walk_start list, but we need to clear that flag before we start walking
so those flags don't halt our depth-first-search walk.
On my copy of the Linux kernel repository, the performance of 'git
merge-base --independent <all-tags>' goes from 1.1 seconds to 0.11
seconds.
These two numbers are with commit-graph fully populated with usable
generation numbers, I presume, and it is quite impressive.
On 2/1/2021 3:05 PM, Junio C Hamano wrote:
"Derrick Stolee via GitGitGadget" [off-list ref] writes:
quoted
The important piece is to ensure we short-circuit the walk when we find
that there is a single non-redundant commit. This happens frequently
when looking for merge-bases or comparing several tags with 'git
merge-base --independent'. Use a new count 'count_still_independent' and
if that hits 1 we can stop walking.
That is because when you are left one single thing, it may be able
to reach many other things, but the fact that it by itself won't be
reachable by remaining independent things will not change (because,
that sole remaining independent thing is itself)?
Right. If there is only one non-STALE input commit left, then it will
be the only returned result. We will never find that all commits are
redundant because the commit graph is acyclic. The performance
improvement comes from halting the DFS walk: there might be more
commits to walk but they won't change the result.
quoted
To update 'count_still_independent' properly, we add use of the RESULT
flag on the input commits. Then we can detect when we reach one of these
commits and decrease the count. We need to remove the RESULT flag at
that moment because we might re-visit that commit when popping the
stack.
We use the STALE flag to mark parents that have been added to the new
walk_start list, but we need to clear that flag before we start walking
so those flags don't halt our depth-first-search walk.
On my copy of the Linux kernel repository, the performance of 'git
merge-base --independent <all-tags>' goes from 1.1 seconds to 0.11
seconds.
These two numbers are with commit-graph fully populated with usable
generation numbers, I presume, and it is quite impressive.
Yes, these numbers are with a full commit-graph.
Thanks,
-Stolee