On 2/1/2021 3:05 PM, Junio C Hamano wrote: > "Derrick Stolee via GitGitGadget" <gitgitgadget@xxxxxxxxx> 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)? 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. >> 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
