Bug#645558: Improve britney2 auto-hinter
On 2011-10-17 01:14, Niels Thykier wrote:
> Package: release.debian.org
> Severity: wishlist
> User: release.debian.org@packages.debian.org
> Usertags: britney
>
> Hi,
>
> I have written a patch to improve britney2's auto-hinter. I noticed that britney2 does not quite cope with complex cases.
>
> The tree-circle-dependencies-huge-graph-no-hint[1] test case demonstrates this issue. The current britney cannot solve this if the "DEPTH" and "WIDTH" (in hooks/post-setup) are greater than 3. With the patch it solved the the 20x20 variant[2].
>
In case you would like a "visual" version of the set up, I have prepared
some dot graphs of the issue[1]. This is entirely binary package
relations (there are no source relations in this case). The source for
these graphs are generated in the test case
($rundir/$test/debug-deps-$suite.dot) as an image of "before migration".
The setup is designed so that src-i-{0..WIDTH/2-1} forms a circular
dependency (so that is DEPTH loops of size WIDTH/2) and
src-i-{j/2..WIDTH} depends in a straight line into the circle on the
same row.
On top of this, each src-i-j depends on src-(i-1)-j, which forms a
non-circular graph on the j/2..WIDTH-nodes. As explained above, all of
these ends in the DEPTH circles. In the dot graphs the circles are on
the left and the non-circular part is on the right (not by design btw).
The 20x20 variant takes about 5.5 seconds on franck (with the live
britney). The patched version is not visibly faster (even for a 30x30,
the patched version only reduces the runtime from ~37 to ~36s on my
machine).
Auto-hinting before the main run has have an incredible effect on the
runtime in this test case[2], because the patched version would reduce
the main run to 0 packages. This is somewhat unrealistic in "real
data". However considering how cheap auto-hinting is compared to the
main run, this might be worth it.
~Niels
[1]
4x4: http://release.debian.org/~nthykier/unstable-4x4.png
20x20: http://release.debian.org/~nthykier/unstable-20x20.png
Btw, I suspect that for graphs smaller than 4x4, the resulting relations
are generated wrong.
[2] Reducing the runtime of the patched britney to ~2 seconds from 36
seconds on the 30x30 variant. The 20x20 variant is less than a second.
> The basic algorithm for the auto-hinter in this patch is to transform the graph of valid candidates into a DAG[3]. Using the DAG it will calculate which components must migrate together.
>
> The runtime complexity of this algorithm should be in O(|V| + |E|)[4], where |V| is the number of validate candidates and |E| is the dependencies between them (vertexes and edges in the graph, respectively).
>
> ~Niels
>
> [1] http://release.debian.org/~nthykier/britney-tests/t/tree-circle-dependencies-huge-graph-no-hint/
>
> [2] In all my tests DEPTH and WIDTH were equal to each other.
>
> [3] Using Strongly Connected Components, see
>
> http://en.wikipedia.org/wiki/Directed_acyclic_graph#Relation_to_other_kinds_of_graphs
>
> [4] I am assuming (on average) constant time hash-look up, append to lists, linear time iteration over hashes. This should be a valid assumption. :)
>
>
> -- System Information:
> Debian Release: wheezy/sid
> APT prefers testing
> APT policy: (990, 'testing'), (500, 'unstable'), (1, 'experimental')
> Architecture: i386 (x86_64)
>
> Kernel: Linux 3.0.0-1-amd64 (SMP w/8 CPU cores)
> Locale: LANG=en_DK.UTF-8, LC_CTYPE=en_DK.UTF-8 (charmap=UTF-8)
> Shell: /bin/sh linked to /bin/dash
Reply to: