On Wed, 15 Jan 2014 14:00:30 +0000, David Kastrup wrote:
> Andreas Krey <a.k...@gmx.de> writes:
> > 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.

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


"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to