git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: Strange O(N^3) behavior in "git filter-branch"

From
Junio C Hamano <gitster@pobox.com>
Date
Jul 15, 2011, 18:51 UTC
Message-ID
<7vlivz1inu.fsf@alter.siamese.dyndns.org>
In-Reply-To
<4E200611.9010005@alum.mit.edu>
Michael Haggerty <mhagger@alum.mit.edu> writes:
Show 8 quoted lines
> 1. Change git-filter-branch (and any other long-running commands?) to do
> an initial check for the presence of replace references (packed or
> loose), and if there are none, set GIT_NO_REPLACE_OBJECTS automatically.
>  This would of course fail if any of the user's scripts try to set up
> replace references.  (Side note: perhaps the git-replace command should
> complain if GIT_NO_REPLACE_OBJECTS is turned on?  It would almost always
> indicate a mistake.)  It also wouldn't help in repositories that *have*
> replace references.

In the short term I think this makes sense, as the whole point of using filter-branch in a repository that has grafts and replacements is so that the resulting history won't have to look-aside into grafts and replace information.

But I think the replace-object codepath should be optimized to realize there is no funky replacement (which _is_ a rare configuration) going on much early so that it does not incur that much overhead you observed. IOW, I tend to agree with your 3. below.

> 2. Add an option to git-filter-branch to have it pack references
> occasionally.
Doesn't the code already do this via "git gc" though?
> 3. Optimize the specific case where there is no refs/replace
> directory--if this directory is missing, then defer populating the loose
> refs cache in the hope that it will never be needed.
Previous: Michael HaggertyNext: Jeff King
Message 4 of 11 in “Strange O(N^3) behavior in "git filter-branch"”
  1. Michael HaggertyJul 14, 2011
  2. Michael HaggertyJul 14, 2011
  3. Michael HaggertyJul 15, 2011
  4. Junio C HamanoJul 15, 2011
  5. Jeff KingJul 15, 2011
  6. Michael HaggertyJul 16, 2011
  7. Drew NorthupJul 17, 2011
  8. Jakub NarebskiJul 18, 2011
  9. Drew NorthupJul 18, 2011
  10. Michael HaggertyAug 3, 2011
  11. Jeff KingAug 3, 2011

Read the whole thread, see it on lore, or plain text.

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