Re: [PATCH v2 4/5] commit-reach: use heuristic in remove_redundant()

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 1, 2021, 20:05 UTC
Message-ID: <xmqqczxjlfj1.fsf@gitster.c.googlers.com>
In-Reply-To: <83feabeebb5f035059758fba1ca5cf74f3a22c91.1612183647.git.gitgitgadget@gmail.com>

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

Show 5 quoted lines

> 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)?

Show 13 quoted lines

> 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.