Re: Consistency question

From: David Kastrup <dak@gnu.org>
Date: Jan 15, 2014, 11:40 UTC
Message-ID: <871u098ocy.fsf@fencepost.gnu.org>
In-Reply-To: <20140115111330.GH14335@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 16 quoted lines

> 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