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

[Sebastian Luther]

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.