* [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking
@ 2014-01-29 15:33 99% Sebastian Luther
0 siblings, 0 replies; 1+ results
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
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.
^ permalink raw reply [relevance 99%]
Results 1-1 of 1 | reverse | options above
-- pct% links below jump to the message on this page, permalinks otherwise --
2014-01-29 15:33 99% [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox