git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: "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>
Subject: [PATCH v3 0/5] Speed up remove_redundant()
Date: Fri, 19 Feb 2021 12:34:05 +0000	[thread overview]
Message-ID: <pull.852.v3.git.1613738051.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.852.v2.git.1612183647.gitgitgadget@gmail.com>

Michael Haggerty pointed out that git merge-base --independent is quite slow
when many commits are provided in the input. This boils down to some
quadratic behavior in remove_redundant() because it calls
paint_down_to_common() in a loop.

This series avoids that by using a single commit walk, pushing a flag that
means "this commit is reachable from a parent of a commit in the list." At
the end of the walk, the input commits without that flag are independent.

There is an extra performance enhancement using the first-parent history as
a heuristic. This helps only when there is a single independent result, as
we can short circuit the walk when all other inputs are found to be
reachable from the top one. It also gets faster when we discover the commit
with lowest generation and can restrict our walk further to the next-lowest
generation number.

My tests were on the Linux kernel repository, testing this command:

  git merge-base --independent $(git for-each-ref refs/tags --format="%(refname)")

       Before: 16.4s
After Patch 1:  1.1s
After Patch 2:  0.1s


This does not change the correctness of the function. It is tested carefully
in t6600-test-reach.c, among existing merge-base tests. There are also more
tests in scripts like t6012-rev-list-simplify.sh that trigger the new logic
under GIT_TEST_COMMIT_GRAPH=1.


Updates in V3
=============

 * Patch 2 is updated to René's comments. Sorry I dropped the ball on this.
   I had the changes locally, but never pushed them until now.


Updates in V2
=============

 * The old algorithm is not entirely removed. It is still faster than the
   new algorithm if all input commits are not in the commit-graph file
   (unless the commit-graph file is really close to the input commits, but
   that is an unreasonable expectation). Now, the new logic only happens if
   there is an input commit with finite generation number.

 * There was a copy of 'array' being used for the final reorder which is now
   removed. We still need to be careful about the RESULT bit.

 * The final patch is new, adding yet another speedup in the form of
   increasing the min_generation cutoff when we find the input commit of
   smallest generation. This can reduce the time significantly when given
   many inputs. This does require copying the 'array' again, so we can sort
   by generation number while preserving the original order of 'array' which
   is required by some callers.

Thanks, -Stolee

Derrick Stolee (5):
  commit-reach: reduce requirements for remove_redundant()
  commit-reach: use one walk in remove_redundant()
  commit-reach: move compare_commits_by_gen
  commit-reach: use heuristic in remove_redundant()
  commit-reach: stale commits may prune generation further

 commit-reach.c | 190 ++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 165 insertions(+), 25 deletions(-)


base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-852%2Fderrickstolee%2Fmerge-independent-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-852/derrickstolee/merge-independent-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/852

Range-diff vs v2:

 1:  649f6799e6bf = 1:  649f6799e6bf commit-reach: reduce requirements for remove_redundant()
 2:  2f80ae5fcb00 ! 2:  c2c08989ce60 commit-reach: use one walk in remove_redundant()
     @@ commit-reach.c: struct commit_list *get_octopus_merge_bases(struct commit_list *
       	unsigned char *redundant;
       	int *filled_index;
      @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt
     - 	for (i = filled = 0; i < cnt; i++)
     - 		if (!redundant[i])
     - 			array[filled++] = work[i];
     -+	for (j = filled, i = 0; i < cnt; i++)
     -+		if (redundant[i])
     -+			array[j++] = work[i];
     - 	free(work);
     - 	free(redundant);
     - 	free(filled_index);
       	return filled;
       }
       
     @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit
      +	}
      +
      +	/* clear marks */
     -+	for (i = 0; i < walk_start_nr; i++)
     -+		clear_commit_marks(walk_start[i], STALE);
     ++	clear_commit_marks_many(walk_start_nr, walk_start, STALE);
      +	free(walk_start);
      +
      +	return count_non_stale;
 3:  009f64b53c95 = 3:  1d3c5ebbb632 commit-reach: move compare_commits_by_gen
 4:  83feabeebb5f = 4:  c1fc174d42aa commit-reach: use heuristic in remove_redundant()
 5:  14f0974c9872 = 5:  539db83bd735 commit-reach: stale commits may prune generation further

-- 
gitgitgadget

  parent reply	other threads:[~2021-02-19 12:38 UTC|newest]

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-01-28 16:24 [PATCH 0/3] " 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
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   ` Derrick Stolee via GitGitGadget [this message]
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=pull.852.v3.git.1613738051.gitgitgadget@gmail.com \
    --to=gitgitgadget@gmail.com \
    --cc=derrickstolee@github.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=l.s.r@web.de \
    --cc=me@ttaylorr.com \
    --cc=mhagger@alum.mit.edu \
    --cc=peff@peff.net \
    --cc=stolee@gmail.com \
    --subject='Re: [PATCH v3 0/5] Speed up 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).