Re: [PATCH v2] rev-list docs: clarify --topo-order description

From: Thomas Rast <trast@student.ethz.ch>
Date: Aug 17, 2012, 09:50 UTC
Message-ID: <87sjbletjt.fsf@thomas.inf.ethz.ch>
In-Reply-To: <874no1hnfg.fsf@thomas.inf.ethz.ch>

Thomas Rast <trast@inf.ethz.ch> writes:

Show 9 quoted lines

> Junio C Hamano <gitster@pobox.com> writes:
>
> The topo order algorithm can be modified to take advantage of
> [generation numbers], in order to provide incremental processing:
>
>   Let S be the set of tentative sources
>
>   Let U be the set of vertices whose out-edges are no known yet
>     (i.e., the set of commits which haven't been loaded yet)

[...]

Show 16 quoted lines

>   while there are any vertices left:
>
>     pick any tentative source C from S that we "want to emit"
>
>     # Ascertain that no unknown commit (from U or further beyond) can be
>     # a descendant of C
>     while there is a D in U such that g(D) > g(C):
>       load D
>       remove D from U
>       add the parents of D to U if they were not already loaded
>       possibly remove some elements of S if their indegree became nonzero
>
>     if C was removed from S:
>       continue
>
>     remove C from the graph and emit it

By the way, this does bump the runtime of the algorithm a bit, depending on the data structure used for U. Recall that ordinary topo-sort with a stack for S (i.e., --topo-order) runs linearly with the number of vertices.

If we use a priority queue for U, which lets us get at the highest-generation unknown commits easily, it potentially goes to n log n if U reaches linear size at some point.

That shouldn't hurt too much of course, since on the one hand it should rarely actually get that big, and OTOH --date-order has n log n runtime anyway (using a priority queue for S).

Thanks for challenging me on my "it should work" feeling. It was quite interesting to actually think it through and write down a workable algorithm.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch