The test case for bug 743115 has revealed that the amount of backtracking is significantly reduced if we prefer choices that satisfy all parents when we backtrack for a slot conflict. This patch sorts choices by the number of parents that the choice does not satisfy (referred to as "conflict atoms" in the code), and reduces the required backtracking tries from 21 to 7: > diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py > index 3f864aefc..4d4f34b73 100644 > --- a/lib/_emerge/depgraph.py > +++ b/lib/_emerge/depgraph.py > @@ -1797,6 +1797,12 @@ class depgraph: > if parent_atom not in parent_atoms) > backtrack_data.append((to_be_masked, conflict_atoms)) > > + # Prefer choices that minimize conflict atoms. This is intended > + # to take precedence over the earlier package version sort. The > + # package version sort is still needed or else the > + # testOverlapSlotConflict method of VirtualMinimizeChildrenTestCase > + # will not succeed reliably with the default backtrack limit. > + backtrack_data.sort(key=lambda item: len(item[1])) > to_be_masked = backtrack_data[-1][0] > > self._dynamic_config._backtrack_infos.setdefault( > diff --git a/lib/portage/tests/resolver/test_slot_operator_missed_update.py b/lib/portage/tests/resolver/test_slot_operator_missed_update.py > index fce012f62..1ea701003 100644 > --- a/lib/portage/tests/resolver/test_slot_operator_missed_update.py > +++ b/lib/portage/tests/resolver/test_slot_operator_missed_update.py > @@ -90,7 +90,7 @@ class BacktrackMissedUpdateTestCase(TestCase): > # Bug 743115: missed updates trigger excessive backtracking > ResolverPlaygroundTestCase( > [">=dev-python/pypy3-7.3.2_rc", "@world"], > - options={"--update": True, "--deep": True, "--backtrack": 25}, > + options={"--update": True, "--deep": True, "--backtrack": 10}, > success=True, > mergelist=[ > "dev-python/pypy3-7.3.2_rc2_p37-r1",
Patch posted for review: https://archives.gentoo.org/gentoo-portage-dev/message/106cfc69cedb5dd1184d95f28c2787d4 https://github.com/gentoo/portage/pull/623
The bug has been referenced in the following commit(s): https://gitweb.gentoo.org/proj/portage.git/commit/?id=f64310749f176f8921b72ce282b4294efe81c3f0 commit f64310749f176f8921b72ce282b4294efe81c3f0 Author: Zac Medico <zmedico@gentoo.org> AuthorDate: 2020-09-19 21:32:41 +0000 Commit: Zac Medico <zmedico@gentoo.org> CommitDate: 2020-09-20 22:27:32 +0000 _slot_confict_backtrack: minimize conflict atoms (bug 743631) Prefer choices that minimize conflict atoms, so that choices which satisfy all parents are preferred. This reduces the minimum necessary backtrack tries from 21 to 7 for the unit test related to bug 743115. Bug: https://bugs.gentoo.org/743115 Bug: https://bugs.gentoo.org/743631 Signed-off-by: Zac Medico <zmedico@gentoo.org> lib/_emerge/depgraph.py | 6 ++++++ lib/portage/tests/resolver/test_slot_operator_missed_update.py | 2 +- 2 files changed, 7 insertions(+), 1 deletion(-)
The bug has been referenced in the following commit(s): https://gitweb.gentoo.org/repo/gentoo.git/commit/?id=862266358f01efa90c12d182d1f85a3014b80439 commit 862266358f01efa90c12d182d1f85a3014b80439 Author: Zac Medico <zmedico@gentoo.org> AuthorDate: 2020-09-21 05:35:06 +0000 Commit: Zac Medico <zmedico@gentoo.org> CommitDate: 2020-09-21 05:59:31 +0000 sys-apps/portage: Bump to version 3.0.8 #404157 emerge: --keep-going support pkg_pretend failures #644246 Add mercurial sync support #710432 emerge: Enable parallel-fetch during pkg_pretend #743115 emerge: Fix slot conflict backtracking to group similar missed updates into a single backtracking try #743631 emerge: Fix slot conflict backtracking to prefer choices that satisfy all dependencies Bug: https://bugs.gentoo.org/739718 Bug: https://bugs.gentoo.org/404157 Bug: https://bugs.gentoo.org/644246 Bug: https://bugs.gentoo.org/710432 Bug: https://bugs.gentoo.org/743115 Bug: https://bugs.gentoo.org/743631 Package-Manager: Portage-3.0.8, Repoman-3.0.1 Signed-off-by: Zac Medico <zmedico@gentoo.org> sys-apps/portage/Manifest | 1 + sys-apps/portage/portage-3.0.8.ebuild | 267 ++++++++++++++++++++++++++++++++++ 2 files changed, 268 insertions(+)
