Re: Extremely slow progress during 'git reflog expire --all'

From: Jeff King <peff@peff.net>
Date: Apr 6, 2010, 06:02 UTC
Message-ID: <20100406060217.GF3901@coredump.intra.peff.net>
In-Reply-To: <7v1vetpw63.fsf@alter.siamese.dyndns.org>

On Mon, Apr 05, 2010 at 11:54:28AM -0700, Junio C Hamano wrote:

Show 11 quoted lines

> Jeff King <peff@peff.net> writes:
> 
> > Hmm. It looks like mark_reachable() stops traversing when it hits a
> > commit older than expire_total. I imagine that's to avoid going all the
> > way to the roots. But if we hit any unreachable entry, in_merge_bases()
> > is going to have to go all the way to the roots, anyway.
> 
> Yeah, an alternative is to keep the list of commits where the initial
> mark_reachable() run stopped, and instead of doing in_merge_bases(),
> lazily restart the traversal all the way down to root, and then rely
> solely on the REACHABLE bit from then on.

Ah, yeah, that is much more clever. It has the same worst case performance as what I proposed, but is much more optimistic that we won't have to do it at all.

Show 12 quoted lines

> > I wonder if, in addition to your patch, we should remove the
> > double-check in_merge_bases and simply report those old ones as
> > reachable. We may be wrong, but we are erring on the side of keeping
> > entries, and they will eventually expire in the regular cycle (i.e., 90
> > days instead of 30).
> >
> > All of that being said, your patch does drop Frans' case down to about
> > 1s of CPU time, so perhaps it is not worth worrying about beyond that.
> 
> I think a reasonable solution would be along the lines you described, but
> the patch you are responding to does err on the wrong side when a clock
> skew is there.  Does it matter?  Probably not.

True. With the technique you mentioned above, you would reverse your test and do:

  if (flags & REACHABLE)
    return 0;
  if (expanded_reachable_to_root)
    return 1; /* we know it's not */
  expand_reachable_to_root();
  return !(flags & REACHABLE);

I don't think I care enough to do a patch, though. I don't have a problem with you applying what you posted earlier.

-Peff