Re: "git reflog expire --all" very slow

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Apr 2, 2009, 15:30 UTC
Message-ID: <alpine.LFD.2.00.0904020759180.4130@localhost.localdomain>
In-Reply-To: <7vmyazimds.fsf@gitster.siamese.dyndns.org>

On Wed, 1 Apr 2009, Junio C Hamano wrote:

Show 12 quoted lines

> 
> Correct.  But after thinking about this a bit more, I am starting to suspect
> the "of course" in your earlier
> 
>     If I do
> 
>             mark_reachable(cb.ref_commit, 0);
> 
>     instead (to traverse the _whole_ tree, with no regards to date), the time 
>     shrinks to 1.7s. But of course, that's also wrong.
> 
> may not be such a clearly obvious thing.

I think we should never do it up-front, because for nicely behaved people who just pull other peoples work (which are also the people most likely to not have beefy machines), the normal reflog is going to be entirely reachable, and we don't have to traverse the whole thing.

So what I'd suggest is something like:

 - start off with the time limit, possibly with some extra fudging

 - but never bother calling "in_merge_bases()"

 - if we ever get to a commit that doesn't look reachable in that 
   situation, we now have two choices:

    (a) just use the dang 'object->flags & REACHABLE' flag as-is.
        Why even bother to be clever? We did the reachability by time 
        already, it's done, it's there, just use it. In other words, the 
        reachability simply works like "--since=<date>'.

    (b) Try to do the "exact" thing, and waste lots of time on it, and 
        maybe find an odd commit or two where the date had been wrong. Do 
        we really care?

I'd actually go for 'a', with a slight modification: try to convert the "reflog date" (the date of a local action) into a "commit date" (the date of a commit in the repository). Because those two are different "time spaces", and comparing a "commit date" to a "in my repo" date is fairly wrong.

But in general, I don't think this is something that needs any extra precision. We're not talking about "theoretically reachable" here. We're talking about reflog entries that are already older than the unreachability limit, and that point to commits that are older than the reachability limit. Yes, yes, clocks aren't synchronized, but do we really care?

IOW, I'd suggest just removing the in_merge_base() tests entirely. Make the semantics even simpler:

	have_done_reachability = 0;
	reachability_date = 0;

	for_each_reflog_oldest_first() {
		/* Older than unconditional expire? */
		if (really_old(entry)) {
			reachability_date = entry->commit->date;
			goto prune;
		}

		/* Younger than the reflog reachability? */
		if (really_young(entry) && !fix_stale)
			goto save;

		/*
		 * Ok, not an unconditional expire entry.
		 * Do the reachability - once
		 */
		if (!have_done_reachability) {
			have_done_reachability = 1;
			if (fix_stale)
				reachability_date = 0;
			mark_reachabile(top, reachability_date);
		}

		if (!(entry->commit->flags & REACHABLE))
			goto prune;

	save:
		save(entry);
		continue;
	prune:
		prune(entry);
		continue;
	}

Does that change semantics? Yes, absolutely. But it sounds very practical.

		Linus