Re: Consistency question

[David Kastrup <dak@gnu.org>]

Jeff King <peff@peff.net> writes:

> On Wed, Jan 15, 2014 at 11:37:08AM +0100, David Kastrup wrote:
>
>> The question is what guarantees I have with regard to the commit date of
>> a commit in relation to that of its parent commits:
>> 
>> a) none
>> b) commitdate(child) >= commitdate(parent)
>> c) commitdate(child) > commitdate(parent)
>
> a) none
>
>> Obviously, I can rely on c) being true "almost always":
>
> Actually, b) is quite often the case in automated processes (e.g., "git
> am" or "git rebase"). The author dates are different, but the committer
> dates may be in the same second.

Ok, thanks.  Assuming that rebases don't happen 1000/s, I should likely
not worry too much about O(n^2) for this case (and frankly, clearly
nobody worried about O(n^2) in the current blame.c anyway).  It's also
not really relevant for linear parts of the history like that of "git
rebase" since in that case the parent enters my priority queue when its
child is getting processed: nothing to be confused about here.  This is
more about sibling rivalries calling a parent to the queue before the
sibling had a chance to leave.  So it comes into play for my use case
basically only when dealing with merge commits.

> I suspect there are other algorithms that could be sped up, too, if we
> had trustworthy generation numbers (I implemented and timed the
> "--contains" algorithm, but haven't done so for other algorithms).

With a single root, "depth" helps a lot.  When looking for a common
parent of a number of commits, you first shorten all ancestries to the
same size and then you can look for the point of convergence in
lockstep.

But didn't git forego the "single root" requirement in its commit DAG at
some point of time?

Thanks for the speedy reply!  I think I'm good with what I need to know
to go ahead.  The rest is just idle curiosity.

-- 
David Kastrup