Gentoo Archives: gentoo-dev

From: Zac Medico <zmedico@g.o>
To: gentoo-dev@l.g.o
Subject: Re: [gentoo-dev] Portage dependency solving algorithm
Date: Mon, 24 Nov 2014 02:34:21
Message-Id: 54729923.4080603@gentoo.org
In Reply to: Re: [gentoo-dev] Portage dependency solving algorithm by Andrew Savchenko
1 On 11/23/2014 05:50 PM, Andrew Savchenko wrote:
2 > I've done some profiling with this both patches (from bugs 529660
3 > and 530010) applied. See *p530010*.pdf files for both hosts here:
4 > ftp://brunestud.info/gentoo/portage-v4.tar.xz
5 >
6 > For performance enhancement I get the following data for
7 > normal (that is unprofiled) runs:
8 > time calls
9 > desktop 13% 62%
10 > hitomi 6% 62%
11 >
12 > where time — is % less real time for emerge run and calls stands
13 > for % less _select_pkg_highest_available_imp calls.
14 >
15 > While testing --verbose-conflicts I found that if tree contains
16 > unresolved conflict, it takes much longer time for emerge to
17 > proceed: +36% on desktop and +44% on hitomi.
18 >
19 > Unresolved conflict was created by adding apt-text/dvipdfmx to the
20 > @world: it blocks latex-2014 update. (Actually I just reverted one
21 > of fixes I made earlier in order to run -DNupv @world without
22 > errors .) Looks like emerge tries to build more depgraps to solves
23 > this issue.
24
25 This is controlled by the --backtrack option (10 is default). That means
26 it can create up to 10 depgraphs before it aborts. On a slow computer,
27 you might consider putting --backtrack=1 in EMERGE_DEFAULT_OPTS. That
28 way, it won't waist so mush time searching for a solution before it
29 ultimately fails. Note that you need at least --backtrack=1 for EAPI 5
30 sub-slot rebuilds to work.
31
32 > I'm not sure if this may be a subject for optimization.
33
34 Yes, there are many possible ways to optimize it. Heuristics can be used
35 to recognize various kinds of solvable conflicts and solve them more
36 efficiently. For example, the code in this commit added support for
37 solving some slot conflicts without backtracking:
38
39 https://github.com/gentoo/portage/commit/a862cc5dd1a56114fa579c5fb01b518b243666d9
40
41 > Graps are also present in the tarball in "*@world_with_blocks*.pdf"
42 > files.
43
44 Unfortunately, I don't see anything else that's easily optimized by
45 memoization. Further optimization will require more heuristics as
46 mentioned above.
47
48 > And thank your for optimizations! They really give a new breath to
49 > my old boxes. Awaiting for them upstream :)
50
51 You're welcome. Thanks for collecting the data.
52 --
53 Thanks,
54 Zac