Re: [PATCH 0/3] Speed up remove_redundant()

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 28, 2021, 20:20 UTC
Message-ID: <xmqqzh0svmnj.fsf@gitster.c.googlers.com>
In-Reply-To: <pull.852.git.1611851095.gitgitgadget@gmail.com>

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

Show 8 quoted lines

> 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.

Yay. I've been quite unhappy with the loop ever since I wrote it back in 2012.

Thanks for cleaning it up.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.