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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html


[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]