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

From: Junio C Hamano <gitster@pobox.com>
Date: Apr 5, 2010, 18:54 UTC
Message-ID: <7v1vetpw63.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20100405062621.GA30934@coredump.intra.peff.net>

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.

> Or is that what your "clock skew" is meant to mean?

What I meant was you commit A, a child B, rewind clock to commit its child C at an incorrect and old time, and fix clock to commit its child D which is at the tip of a ref. mark_reachable() will stop at C saying that is sufficiently old and recent A and B may be pruned too early.

Show 8 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.