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

[Junio C Hamano <gitster@pobox.com>]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> That made no sense. It should have been:
>
> On Mon, 30 Mar 2009, Linus Torvalds wrote:
>> 
>> but we care about the commits that are younger than 'expire_total' (older 
>> than that, and they are pruned unconditionally), but older than 
>> 'expire_unreachable' (younger than that and the date doesn't matter).
>                                                   ^^^^
>                                                  reachability
>
> but other than that the commentary stands.

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.

Suppose you do not do "mark_reachable(cb.ref_commit, 0)" but use the
expire_total as the cut-off value (which is what I've queued).  If you
have one unreachable entry that you end up running in_merge_bases() for,
you will traverse all the history down _anyway_, and at that point, you
would be better off if you actually marked everything upfront, and
discarded anything unmarked as unreachable without falling back to
in_merge_bases() at all.

The above reasoning of course assumes that "keep reflog entries if they
are reachable from the tip, otherwise drop them if they are more than 30
days old" is a good medium level semantics to cull what the other rule
"drop any reflog entry older than 90 days" may not.

A hacky alternative would be to use total_expire as the cut-off and do not
fall back on in_merge_bases().  We might incorrectly prune away an entry
that records that you pulled a commit that is still reachable from the tip
last week, if that commit happens to be 4 months old if we did so, so I am
not convinced myself it is a reasonable hack, though.