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.net, Derrick Stolee <derrickstolee@github.com> Subject: [PATCH 0/3] Speed up remove_redundant() Date: Thu, 28 Jan 2021 16:24:51 +0000 [thread overview] Message-ID: <pull.852.git.1611851095.gitgitgadget@gmail.com> (raw) 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. 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. Thanks, -Stolee Derrick Stolee (3): commit-reach: use one walk in remove_redundant() commit-reach: move compare_commits_by_gen commit-reach: use heuristic in remove_redundant() commit-reach.c | 178 +++++++++++++++++++++++++++++++++---------------- 1 file changed, 120 insertions(+), 58 deletions(-) base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-852%2Fderrickstolee%2Fmerge-independent-v1 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-852/derrickstolee/merge-independent-v1 Pull-Request: https://github.com/gitgitgadget/git/pull/852 -- gitgitgadget
next reply other threads:[~2021-01-28 16:26 UTC|newest] Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-01-28 16:24 Derrick Stolee via GitGitGadget [this message] 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 ` [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=pull.852.git.1611851095.gitgitgadget@gmail.com \ --to=gitgitgadget@gmail.com \ --cc=derrickstolee@github.com \ --cc=git@vger.kernel.org \ --cc=gitster@pobox.net \ --cc=me@ttaylorr.com \ --cc=mhagger@alum.mit.edu \ --cc=peff@peff.net \ --subject='Re: [PATCH 0/3] 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).