Re: [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking

[Brian Dolbec <dolsen@gentoo.org>]

On Wed, 29 Jan 2014 16:33:04 +0100
Sebastian Luther <SebastianLuther@gmx.de> wrote:

> Hi all,
> 
> as you may have noticed, emerge can in some cases take ages ( >5-10
> minutes) to resolve dependencies these days. This happens when lots
> of backtracking is required to solve slot conflicts and/or to
> schedule slot operator rebuilds. The problem is that the current
> backtracking implementation has to rebuild the entire dependency
> graph from scratch each time it backtracks.
> 
> This series of patches is a first step into fixing this problem.
> 
> What these patches do:
> 	Patch 1
> 	-------
> 	Adds a new data structure called package_tracker. This data
> structure is meant to replace several of the depgraph data structures.
> 	It has some new features not present in the existing data
> structures. 1) It can properly deal with several packages in the same
> slot. 2) It supports removal of previously added packages.
> 		3) It tracks package conflicts automatically.
> 		4) It has a more general concept of conflicts.
> 
> 	Not all of the features are used for now, but they will make
> future changes easier.
> 
> 	Patch 2-5
> 	---------
> 	These patches replace the old data structures with the
> package tracker
> 
> 	Patch 6-8
> 	---------
> 	These patches fix several issues with emerge output. 6 and 8
> are somewhat independent of the other patches in this series. Patch 7
> introduces a new function used in Patch 10.
> 
> 	Patch 9
> 	-------
> 	New function for patch 10.
> 
> 	Patch 10
> 	--------
> 	This patch builds on top of all the previous patches. It
> introduces two new functions to the depgraph class. A function to
> remove packages that have previously been pulled in and a function to
> solve simple slot conflicts without backtracking.
> 
> 	This should resolve most "no parents that aren't satisfied by
> other packages in this slot" slot conflicts.
> 
> You may find these patches on github here:
> https://github.com/few/fews-portage-branch/tree/package_tracker
> 
> Some numbers
> ------------
> 
> My system has quite a number of conflicts that give emerge a hard time
> resolving dependencies.
> 
> -uDN world
> 
> Without the patches:
> 	* 11 unsolved slot conflicts
> 	* 2 unsolved blockers
> 	* takes 5 backtracking steps and then fails
> 
> With the patches:
> 	* no unsolved slot conflicts or blockers
> 	* takes 7 backtracking steps and then succeeds
> 
> In this case it actually became slower, but was finally able to find
> a solution.
> 
> -e world
> 
> Without the patches:
> 	* 5 unsolved slot conflicts
> 	* 1 unsolved blocker
> 	* takes 23 backtracking steps and then fails
> 
> With the patches:
> 	* 1 unsolved slot conflict (From a quick look it looks like
> there really is no solution.)
> 	* takes 13 backtracking steps and then fails
> 
> In this case it's a lot faster, but still unacceptably slow.
> The result is improved by solving 4 out of 5 conflicts.
> 
> 
> 

I'm replying to all the series.  I saw no glaring obvious mistakes.

This code is in areas I know little about, but your changes do seem
logical.  Your additional fixes to these patches also look good.

If Mike/Arfrever gives the thumbs up.  They're good to go in my opinion.

-- 
Brian Dolbec <dolsen>