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

From: Jeff King <peff@peff.net>
Date: Jul 15, 2011, 21:20 UTC
Message-ID: <20110715212059.GA2117@sigill.intra.peff.net>
In-Reply-To: <7vlivz1inu.fsf@alter.siamese.dyndns.org>

On Fri, Jul 15, 2011 at 11:51:49AM -0700, Junio C Hamano wrote:

Show 8 quoted lines

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

It already tries to do so. It looks like it calls:

  for_each_replace_ref(...)

which calls:

  do_for_each_ref("refs/replace", ...)

which reads _every_ loose ref, regardless of the prefix we have given it. So the optimization should go into the for_each_ref code, which should avoid looking at parts of the hierarchy that are just going to be culled, no?

And then we would see immediately that there is no refs/replace at all, and quit early. And as a bonus, things like "for_each_tag_ref" would get faster in a repository with many branches, too.

-Peff