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