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

From: Jeff King <peff@peff.net>
Date: Apr 5, 2010, 06:26 UTC
Message-ID: <20100405062621.GA30934@coredump.intra.peff.net>
In-Reply-To: <7vy6h36pt1.fsf@alter.siamese.dyndns.org>

On Sun, Apr 04, 2010 at 11:22:18AM -0700, Junio C Hamano wrote:

Show 5 quoted lines

> Thanks for the analysis, but expire_reflog() that is run for each ref
> already does that, I think.  It first runs mark_reachable(), then walks
> each reflog entry for the ref to call expire_reflog_ent(), which in turn
> calls unreachable() that first checks if mark_reachable() has marked the
> commit, and if so we don't run in_merge_bases().

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.

If we just marked everything, couldn't we then trust the REACHABLE value and not have to do the in_merge_bases double-check? It has worse best-case cost (since we always go to the root), but better worst-case (since we can potentially go to the roots for each unreachable reflog entry).

For example:

Show 9 quoted lines

> +	/*
> +	 * Unless there was a clock skew, younger ones that are
> +	 * reachable should have been marked by mark_reachable().
> +	 */
> +	if (cb->cmd->expire_total < commit->date)
> +		return 1;
> +
>  	if (in_merge_bases(commit, &cb->ref_commit, 1))
>  		return 0;

If we haven't done a "reflog expire" in a while, won't we have a bunch of old commits that will still need double-checked, and produce the same slow behavior? Or is that what your "clock skew" is meant to mean? That we would have removed those old ones already assuming the commit date and the reflog entry for them match up? That's not necessarily true if you move to an older commit, which freshens its reflog entry compared to the commit date.

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.

-Peff