Re: Consistency question

From: Andreas Krey <a.krey@gmx.de>
Date: Jan 15, 2014, 13:45 UTC
Message-ID: <20140115134508.GE7102@inner.h.apk.li>
In-Reply-To: <87ppnt7635.fsf@fencepost.gnu.org>

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

> Andreas Krey <a.krey@gmx.de> writes:

...

Show 6 quoted lines

> > 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.

Show 7 quoted lines

> > 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