Re: History of Debian bootstrapping/porting efforts
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
Reply to: