On Mon, Apr 05, 2010 at 11:54:28AM -0700, Junio C Hamano wrote:
> Jeff King <peff@xxxxxxxx> 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.
Ah, yeah, that is much more clever. It has the same worst case
performance as what I proposed, but is much more optimistic that we
won't have to do it at all.
> > 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.
True. With the technique you mentioned above, you would reverse your
test and do:
if (flags & REACHABLE)
return 0;
if (expanded_reachable_to_root)
return 1; /* we know it's not */
expand_reachable_to_root();
return !(flags & REACHABLE);
I don't think I care enough to do a patch, though. I don't have a
problem with you applying what you posted earlier.
-Peff
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html