On Wed, 15 Jan 2014 14:00:30 +0000, David Kastrup wrote: > Andreas Krey <a.krey@xxxxxx> 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. Andreas -- "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 majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html