Re: How would you use britney for Kali and are generalization patches welcome?

[Niels Thykier <niels@thykier.net>]

On 2014-07-16 23:57, Niels Thykier wrote:
> On 2014-07-16 15:48, Raphael Hertzog wrote:
>> > Hello britney maintainers,
>> > 
> Hi, :)
> 
> Your problem in a nutshell: You triggered something that looks like
> O(2^n) runtime in Britney. /o\

Hi again,

I managed to devise a few patches against the current master that can
complete the kali "wheezy->jessie" in ~2 hours on my laptop.

The patches are available from the [optimize-kali] branch in my personal
git repository.  I suspect the primary patches are:

 * [aa550ed]: installability: Exploit equvialency to reduce choices
   - It vastly reduces the amount of backtracking done by analysing and
     reducing the problem size.  E.g. the spell-checker dependencies are
     reduces from 150ish candidats to 35ish.
   - However, this commit in itself is insufficient to get an suitable
     runtime.
 * [ad2874b]: inst-tester: Attempt to avoid needing to backtrack
   - Combined with the above, I believe this is sufficient for making
     the "main run" complete.  It will still get stuck in the auto
     hinters.
   - This commit tries to avoid backtracking entirely in many cases
     including the spell-checkers.  It tries the candidate before
     setting up a backtrack point.  When the candidate can be chosen
     without any risk of breaking installability, Britney immediately
     commits to the candidate without needing to recuse.
     - Admittedly, the code here is straight forward and could possibly
       do a bit smarter behaviour here.
 * [4a74c5f]: britney.py: Split iter_packages into two
   - This makes commit make Britney able to cope with hints better.


The rest of the patches are just "free extras". :)

NOTE: The "original auto hinter" spent the better part of 15 minutes
computing the hints on my machine.  During this time, there will be
absolutely no output, which to the casual eye may seem like Britney is
stuck.  The last line before that will be[1]:

  I: [<date>] - > Processing hints from the auto hinter [Original]


At the end of the run, kali would have increased installability of 15
packages (as counted by Britney).  Se also [kali-fun-facts]



Enjoy,
~Niels




[optimize-kali]:
https://anonscm.debian.org/cgit/users/nthykier/britney/log/?h=optimise-kali

[aa550ed]:
https://anonscm.debian.org/cgit/users/nthykier/britney/commit/?h=optimise-kali&id=aa550ed6f057e1454ce6ef0b26b8c60b093a6546

[ad2874b]:
https://anonscm.debian.org/cgit/users/nthykier/britney/commit/?h=optimise-kali&id=ad2874beb52572f80b6207e1853df5f612840c6b

[4a74c5f]:
https://anonscm.debian.org/cgit/users/nthykier/britney/commit/?h=optimise-kali&id=4a74c5ffa04e46a1f09279ffd07f851bb07338b2

[1] In my case:

I: [Fri Jul 25 11:46:04 2014] - > Processing hints from the auto hinter
[Original]
I: [Fri Jul 25 12:02:30 2014] - > Processing 'easy' hint from autohinter

[kali-fun-facts]:

Installability:
 before: 49+0: i-17:a-9:a-11:a-12
  after: 34+0: i-8:a-5:a-10:a-11

Number of valid candidates/migrate-able items: 16353
Number of items migrating during the "main run": 7105
Number of items migrating thanks to auto hinters: 28 (a bit sad)
 - Hinted removals: 14 (4 hints, 100% success rate here!)
Number of items remaining: 9220
Number of "old" (smooth-updated) libraries after the run: 62
  - 19 unique package names listed

Obsolete source packages removed: 109
  I.e source packages without any binary packages left in "target"

The resulting log file is about 44M (gzip -9 -> 11M).