Re: [PATCH v4 4/7] revision.c: begin refactoring --topo-order logic

[Junio C Hamano <gitster@pobox.com>]

Derrick Stolee <stolee@gmail.com> writes:

>     time git log --topo-order -10 master >/dev/null
>
>     time git log --topo-order -10 maint..master >/dev/null
>
> I get 0.39s for the first call and 0.01s for the second. (Note: I
> specified "-10" to ensure we are only writing 10 commits and the
> output size does not factor into the time.) This is because the first
> walks the entire history, while the second uses the heuristic walk to
> identify a much smaller subgraph that the topo-order algorithm uses.

The algorithm can be fooled by skewed timestamps (i.e. that SLOP
thing tries to work around), but is helped by being able to leave
early, and it will give us the correct answer as long as there is no
timestamp inversion.

But monotonically increasing "timestamp" without inversion is what
we invented "generation numbers" for, no?  When there is no
timestamp inversion, would a walk based on commit timestamps walk
smaller set than a walk based on commit generation numbers?

> Just as before, by using this algorithm for the B..A case, we are
> adding an extra restriction on the algorithm: always be correct. This
> results in us walking a larger set (everything reachable from B or A
> with generation number at least the smallest generation of a commit
> reachable from only one).
>
> I believe this can be handled by using a smarter generation number
> (one that relies on commit date as a heuristic, but still have enough
> information to guarantee topological relationships), and I've already
> started testing a few of these directions.

Good ot hear.