git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Derrick Stolee <stolee@gmail.com>
To: Junio C Hamano <gitster@pobox.com>,
	Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com>
Cc: git@vger.kernel.org, "Michael Haggerty" <mhagger@alum.mit.edu>,
	me@ttaylorr.com, peff@peff.net, "René Scharfe" <l.s.r@web.de>,
	"Derrick Stolee" <derrickstolee@github.com>,
	"Derrick Stolee" <dstolee@microsoft.com>
Subject: Re: [PATCH v2 4/5] commit-reach: use heuristic in remove_redundant()
Date: Mon, 1 Feb 2021 16:02:32 -0500	[thread overview]
Message-ID: <bd00470c-59d6-52a8-9b2c-dc9e3a0beb82@gmail.com> (raw)
In-Reply-To: <xmqqczxjlfj1.fsf@gitster.c.googlers.com>

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

  reply	other threads:[~2021-02-01 21:03 UTC|newest]

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-01-28 16:24 [PATCH 0/3] Speed up remove_redundant() Derrick Stolee via GitGitGadget
2021-01-28 16:24 ` [PATCH 1/3] commit-reach: use one walk in remove_redundant() Derrick Stolee via GitGitGadget
2021-01-28 20:51   ` Junio C Hamano
2021-01-29 17:11     ` René Scharfe
2021-01-31  3:52       ` Derrick Stolee
2021-01-31 10:20         ` René Scharfe
2021-01-31  3:59     ` Derrick Stolee
2021-01-31 20:13       ` Derrick Stolee
2021-01-31 20:25       ` Junio C Hamano
2021-02-01  3:55         ` Derrick Stolee
2021-01-29 17:10   ` René Scharfe
2021-01-28 16:24 ` [PATCH 2/3] commit-reach: move compare_commits_by_gen Derrick Stolee via GitGitGadget
2021-01-28 16:24 ` [PATCH 3/3] commit-reach: use heuristic in remove_redundant() Derrick Stolee via GitGitGadget
2021-01-28 20:20 ` [PATCH 0/3] Speed up remove_redundant() Junio C Hamano
2021-02-01 12:47 ` [PATCH v2 0/5] " Derrick Stolee via GitGitGadget
2021-02-01 12:47   ` [PATCH v2 1/5] commit-reach: reduce requirements for remove_redundant() Derrick Stolee via GitGitGadget
2021-02-01 19:51     ` Junio C Hamano
2021-02-01 12:47   ` [PATCH v2 2/5] commit-reach: use one walk in remove_redundant() Derrick Stolee via GitGitGadget
2021-02-01 16:12     ` René Scharfe.
2021-02-01 16:31       ` Derrick Stolee
2021-02-01 12:47   ` [PATCH v2 3/5] commit-reach: move compare_commits_by_gen Derrick Stolee via GitGitGadget
2021-02-01 12:47   ` [PATCH v2 4/5] commit-reach: use heuristic in remove_redundant() Derrick Stolee via GitGitGadget
2021-02-01 20:05     ` Junio C Hamano
2021-02-01 21:02       ` Derrick Stolee [this message]
2021-02-01 12:47   ` [PATCH v2 5/5] commit-reach: stale commits may prune generation further Derrick Stolee via GitGitGadget
2021-02-03 15:59     ` Taylor Blau
2021-02-01 15:48   ` [PATCH v2 0/5] Speed up remove_redundant() Derrick Stolee
2021-02-18 23:25     ` Junio C Hamano
2021-02-19 12:17       ` Derrick Stolee
2021-02-20  3:32         ` Junio C Hamano
2021-02-19 12:34   ` [PATCH v3 " Derrick Stolee via GitGitGadget
2021-02-19 12:34     ` [PATCH v3 1/5] commit-reach: reduce requirements for remove_redundant() Derrick Stolee via GitGitGadget
2021-02-19 12:34     ` [PATCH v3 2/5] commit-reach: use one walk in remove_redundant() Derrick Stolee via GitGitGadget
2021-02-19 12:34     ` [PATCH v3 3/5] commit-reach: move compare_commits_by_gen Derrick Stolee via GitGitGadget
2021-02-19 12:34     ` [PATCH v3 4/5] commit-reach: use heuristic in remove_redundant() Derrick Stolee via GitGitGadget
2021-02-19 12:34     ` [PATCH v3 5/5] commit-reach: stale commits may prune generation further Derrick Stolee via GitGitGadget

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=bd00470c-59d6-52a8-9b2c-dc9e3a0beb82@gmail.com \
    --to=stolee@gmail.com \
    --cc=derrickstolee@github.com \
    --cc=dstolee@microsoft.com \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --cc=gitster@pobox.com \
    --cc=l.s.r@web.de \
    --cc=me@ttaylorr.com \
    --cc=mhagger@alum.mit.edu \
    --cc=peff@peff.net \
    --subject='Re: [PATCH v2 4/5] commit-reach: use heuristic in remove_redundant()' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).