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

[Linus Torvalds <torvalds@linux-foundation.org>]

On Wed, 1 Apr 2009, Junio C Hamano wrote:
> 
> 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