Re: Consistency question

Andreas Krey [off-list ref] writes:

On Wed, 15 Jan 2014 12:40:29 +0000, David Kastrup wrote:
...

quoted

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.

Hmm, how about traversing from all the start commits downwards
simultaneously, noting which start you say each commit from, and stopping
when you have a commit carrying all start labels?

It means that when the start commits are at considerably different
depth, you'll traverse much more material than necessary.

Also you need labels.

I don't quite see how the same size plus lockstep works out (but the
'same size' part is possibly the same as my 'concurrent traversal').

It just equalizes the depth before starting, so you don't need labels:
any common ancestor is reached at the same time by its descendants.

Of course, I conveniently forgot merge commits.  This scheme works out
of the box only with single parenting.  And it works fine without a
common ancestor, too: you just run into a NULL pointer at the same time
when there isn't one.

So, uh, this solution does not really seem to match the problem...

-- 
David Kastrup

On Wed, 15 Jan 2014 14:00:30 +0000, David Kastrup wrote:

Andreas Krey [off-list ref] writes:

...

quoted

Hmm, how about traversing from all the start commits downwards
simultaneously, noting which start you say each commit from, and stopping
when you have a commit carrying all start labels?

It means that when the start commits are at considerably different
depth, you'll traverse much more material than necessary.

But it has the advantage that you don't need to traverse the DAG
to the root when the differences are small - the runtimes are roughly
proportional to the difference between the commits.

Also you need labels.

Yes, I assume that that (marking commits) is not a cost factor.

quoted

I don't quite see how the same size plus lockstep works out (but the
'same size' part is possibly the same as my 'concurrent traversal').

It just equalizes the depth before starting, so you don't need labels:
any common ancestor is reached at the same time by its descendants.

Of course, I conveniently forgot merge commits.

I finally noticed but forgot to mention in the last post.

Merges also mean that there is not necessarily a unique common
ancestor between commits.

Andreas

-- 
"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800