public inbox for gentoo-portage-dev@lists.gentoo.org
 help / color / mirror / Atom feed
From: Sebastian Luther <SebastianLuther@gmx.de>
To: gentoo-portage-dev@lists.gentoo.org
Subject: [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking
Date: Wed, 29 Jan 2014 16:33:04 +0100	[thread overview]
Message-ID: <1391009594-22750-1-git-send-email-SebastianLuther@gmx.de> (raw)

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.




             reply	other threads:[~2014-01-29 15:33 UTC|newest]

Thread overview: 13+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-01-29 15:33 Sebastian Luther [this message]
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 01/10] Add resolver/package_tracker Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 02/10] Replace _slot_pkg_map and some tree dbapiS with _package_tracker Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 03/10] Replace mydbapi " Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 04/10] Replace _slot_collision_info " Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 05/10] Replace _slot_collision_nodes " Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 06/10] Package.__str__: show slot/sub-slot Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 07/10] format_unmatched_atom: Pretty printing for unmatched atoms Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 08/10] Some small output fixes for the slot conflict handler Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 09/10] Add digraph.discard Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 10/10] Solve some slot conflicts without backtracking Sebastian Luther
2014-02-02 20:41 ` [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Brian Dolbec
2014-02-02 21:04   ` Sebastian Luther

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1391009594-22750-1-git-send-email-SebastianLuther@gmx.de \
    --to=sebastianluther@gmx.de \
    --cc=gentoo-portage-dev@lists.gentoo.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox