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

[Jeff King <peff@peff.net>]

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

> 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