From: Taylor Blau <me@ttaylorr.com> To: Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> Cc: git@vger.kernel.org, "Michael Haggerty" <mhagger@alum.mit.edu>, me@ttaylorr.com, peff@peff.net, gitster@pobox.com, "René Scharfe" <l.s.r@web.de>, "Derrick Stolee" <stolee@gmail.com>, "Derrick Stolee" <derrickstolee@github.com>, "Derrick Stolee" <dstolee@microsoft.com> Subject: Re: [PATCH v2 5/5] commit-reach: stale commits may prune generation further Date: Wed, 3 Feb 2021 10:59:05 -0500 [thread overview] Message-ID: <YBrISQ/5/pJKgGGZ@nand.local> (raw) In-Reply-To: <14f0974c987215bd36e91450c1a6ebc6d5732121.1612183647.git.gitgitgadget@gmail.com> On Mon, Feb 01, 2021 at 12:47:27PM +0000, Derrick Stolee via GitGitGadget wrote: > From: Derrick Stolee <dstolee@microsoft.com> > Note that these are only modest improvements for the case where the two > independent commits are not in the commit-graph (not until v5.10). All > algorithms get faster as more commits are indexed, which is not a > surprise. However, the cost of walking extra commits is more and more > prevalent in relative terms as more commits are indexed. Finally, the > last case allows us to jump to the minimum generation between the last > two commits (that are actually independent) so we greatly reduce the > cost in that case. Very nice. The explanation and implementation makes sense to me. > Signed-off-by: Derrick Stolee <dstolee@microsoft.com> > --- > commit-reach.c | 28 +++++++++++++++++++++------- > 1 file changed, 21 insertions(+), 7 deletions(-) > > diff --git a/commit-reach.c b/commit-reach.c > index d3a6e2bdd04..c2e0747fea4 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -237,15 +237,27 @@ static int remove_redundant_with_gen(struct repository *r, > { > int i, count_non_stale = 0, count_still_independent = cnt; > timestamp_t min_generation = GENERATION_NUMBER_INFINITY; > - struct commit **walk_start; > + struct commit **walk_start, **sorted; > size_t walk_start_nr = 0, walk_start_alloc = cnt; > + int min_gen_pos = 0; > + > + /* > + * Sort the input by generation number, ascending. This allows > + * us to increase the "min_generation" limit when we discover > + * the commit with lowest generation is STALE. The index > + * min_gen_pos points to the current position within 'array' > + * that is not yet known to be STALE. > + */ > + ALLOC_ARRAY(sorted, cnt); > + COPY_ARRAY(sorted, array, cnt); > + QSORT(sorted, cnt, compare_commits_by_gen); > + min_generation = commit_graph_generation(sorted[0]); This line caught my eye, but we return early in commit-reach.c:reduce_heads() before even calling remove_redundant() (which itself calls remove_redundant_with_gen()), so it's always OK to assume that we have at least one element in 'array'. This patch and the others in v2 all look good to me. Thanks, Taylor
next prev parent reply other threads:[~2021-02-03 16:02 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 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 [this message] 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=YBrISQ/5/pJKgGGZ@nand.local \ --to=me@ttaylorr.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=mhagger@alum.mit.edu \ --cc=peff@peff.net \ --cc=stolee@gmail.com \ --subject='Re: [PATCH v2 5/5] commit-reach: stale commits may prune generation further' \ /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).