Jeff King <peff@xxxxxxxx> writes: > We could topologically order the commits going into limit_list (it just > works most of the time because the date ordering is _mostly_ right). > This guarantees that we deal with 'four' before 'one'. But topo sorting > is expensive. I recall we did a rather clever optimization in merge-base. I am starting to suspect that we would need a similar trick there. The issue is: * We have pushed "one" out already to "newlist", but we haven't given UNINTERESTING bit to it yet. * We are responsible to mark "one" UNINTERESTING, if it can be reached from a commit that is UNINTERESTING. We expect further looping of the "while (list)" and mark_parents_uninteresting() in that loop will eventually smudge it. * We can obviously prove that we marked all UNINTERESTING commits that matters by traversing _all_ history (i.e. make sure mark_parents_uninteresting() recurses, and wait until "list" truly becomes empty), but we would want to somehow optimize it. The everybody_uninteresting() check was introduced for that purpose, but that is not a right optimization if commit timestamps are skewed like this. The right optimization is probably: * Wait until everybody on "list" is UNINTERESTING. IOW, keep the "everybody_uninteresting()" check with break as is. At that point "newlist" will contain all the commits that we might be interested in (e.g. "one"). The issue is reduced from "mark _all_ commits that can be reached from known UNINTERESTING ones" to "make sure the commits on the newlist that are reachable from UNINTERESTING ones in the "list" are marked as UNINTERESTING (e.g. "one" should be checked for reachability from the remaining UNINTERESTING commits in "list", we do not have to check for anything else). * After the loop exits, traverse from all non UNINTERESTING commits on the "newlist" and all remaining commits on the "list" (by definition, the latter are UNINTERESTING) down to their common merge base, propagating UNINTERESTING bit down. Once we do that, we have proven that "one" is reachable from any of the UNINTERESTING commit. - 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
