On 2011-10-17 01:14, Niels Thykier wrote: > Package: release.debian.org > Severity: wishlist > User: release.debian....@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 -- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org