Hi, On Tue, Nov 20, 2012 at 09:22:40PM +0000, Thorsten Glaser wrote: > For reviving m68k:
Thanks for your detailed explanations! I added a summary of it to the m68k section of the wiki page [1], extending the notes entered there by Ingo Jürgensmann. Thanks to both of you! > > - how did you go about finding reduced build dependencies? What were > > the heuristics you used? How did you find dependency cycles to break > > and how did you pick a solution? > > Fully manually. I mostly drew ASCII files like this: > > sourcepkg1 > sourcepkg2 sourcepkg3 sourcepkg4 sourcepkg5 sourcepkg3<dup> > sourcepkg6 sourcepkg2<cyc> > > [...] > > Then I worked on them from right to left, occasionally patching a huge > dependency out or breaking a B-D loop by hand, sometimes also > installing older versions of B-Ds manually, or even building versions > older than sid but newer than what I had. Since yesterday, my tools can now finally turn the whole dependency graph into an acyclic graph by braking only a small number of build dependencies (using an approximative solution to the minimal feedback arc set problem) and output a final build order to build all of Debian starting from an initial minimal build system (priority:essential plus build-essential plus debhelper). Detailed explanations can be found in the email I wrote to our debian-bootstrap mailinglist: http://lists.mister-muffin.de/pipermail/debian-bootstrap/2012-November/000425.html A summary: Using the results I got from Daniel Scheplers x32 bootstrapping work, droppable build dependencies from Thorsten Glaser, Patrick McDermott and my Gentoo work, I was able to reduce the original 923 nodes SCC into one SCC with 159 nodes and another with 42 nodes: http://mister-muffin.de/p/NRTs.png http://mister-muffin.de/p/myFd.png Those two graphs were easily breakable into a DAG by just removing 4 and 2 build dependencies respectively using the feedback arc set algorithm I wrote over the weekend. The same algorithm can also be applied to the full 923 node SCC for Debian Sid, resulting in 90 build dependencies to be dropped to make the graph acyclic and making a final build order possible with (close to) minimal changes. For this to happen, only 50 source packages have to be modified. > > Build-Depends: huge (>= 1.0) [i386 arm] <!embedded !bootstrap>, tiny > > Yeah, waiting for it… As build profiles do not exist yet, there might be instances where my algorithm chooses build dependencies that are not droppable in practice. One obvious example is the dependency cycle: src:pkg-config <--> libglib2.0-dev So I'm now implementing a facility that allows to explicitly mark build dependencies as unbreakable so that the algorithm finds an alternative solution or throws an error. The above case for example has no alternative solution as the cycle is of length two and has no other way of braking it than building pkg-config without libglib2.0-dev. Since this is unlikely to be possible and since the assumption is that only build dependencies might be dropped when necessary but not binary dependencies, a possible solution might be cross compilation. Looking at the cross build dependency graph and braking its dependency cycles is the next step I will take. cheers, josch [1] http://wiki.debian.org/DebianBootstrap/History -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20121120225523.GA18533@hoothoot
