[gentoo-portage-dev] [PATCH] _slot_operator_update_probe: memoize use_reduce (529660)

[gentoo-portage-dev] [PATCH] _slot_operator_update_probe: memoize use_reduce (529660)

[Zac Medico]

Memoize the results of use_reduce calls inside
_slot_operator_update_probe, in order to improve performance. With
memoization, 'emerge -puvDN @world' on one of my computers takes
22.4% less time, and results in 13.5% fewer use_reduce calls.

X-Gentoo-Bug: 529660
X-Gentoo-Url: https://bugs.gentoo.org/show_bug.cgi?id=529660
---
 pym/_emerge/depgraph.py | 65 ++++++++++++++++++++++++++++++++++---------------
 1 file changed, 45 insertions(+), 20 deletions(-)

diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 6f1910d..3f4a097 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -399,6 +399,7 @@ class _dynamic_depgraph_config(object):
 		self._initially_unsatisfied_deps = []
 		self._ignored_deps = []
 		self._highest_pkg_cache = {}
+		self._flatten_atoms_cache = {}
 
 		# Binary packages that have been rejected because their USE
 		# didn't match the user's config. It maps packages to a set
@@ -1719,26 +1720,10 @@ class depgraph(object):
 
 			selected_atoms = None
 
-			atoms = set()
-			invalid_metadata = False
-			for dep_key in ("DEPEND", "HDEPEND", "RDEPEND", "PDEPEND"):
-				dep_string = replacement_parent._metadata[dep_key]
-				if not dep_string:
-					continue
-
-				try:
-					dep_string = portage.dep.use_reduce(dep_string,
-						uselist=self._pkg_use_enabled(replacement_parent),
-						is_valid_flag=replacement_parent.iuse.is_valid_flag,
-						flat=True, token_class=Atom,
-						eapi=replacement_parent.eapi)
-				except portage.exception.InvalidDependString:
-					invalid_metadata = True
-					break
-
-				atoms.update(token for token in dep_string if isinstance(token, Atom))
-
-			if invalid_metadata:
+			try:
+				atoms = self._flatten_atoms(replacement_parent,
+					self._pkg_use_enabled(replacement_parent))
+			except InvalidDependString:
 				continue
 
 			# List of list of child,atom pairs for each atom.
@@ -2005,6 +1990,46 @@ class depgraph(object):
 		return frozenset(x.unevaluated_atom for
 			x in selected_atoms)
 
+	def _flatten_atoms(self, pkg, use):
+		"""
+		Evaluate all dependency atoms of the given package, and return
+		them as a frozenset. For performance, results are cached.
+
+		@param pkg: a Package instance
+		@type pkg: Package
+		@param pkg: set of enabled USE flags
+		@type pkg: frozenset
+		@rtype: frozenset
+		@return: set of evaluated atoms
+		"""
+
+		cache_key = (pkg, use)
+
+		try:
+			return self._dynamic_config._flatten_atoms_cache[cache_key]
+		except KeyError:
+			pass
+
+		atoms = []
+
+		for dep_key in pkg._dep_keys:
+			dep_string = pkg._metadata[dep_key]
+			if not dep_string:
+				continue
+
+			dep_string = portage.dep.use_reduce(
+				dep_string, uselist=use,
+				is_valid_flag=pkg.iuse.is_valid_flag,
+				flat=True, token_class=Atom, eapi=pkg.eapi)
+
+			atoms.extend(token for token in dep_string
+				if isinstance(token, Atom))
+
+		atoms = frozenset(atoms)
+
+		self._dynamic_config._flatten_atoms_cache[cache_key] = atoms
+		return atoms
+
 	def _iter_similar_available(self, graph_pkg, atom, autounmask_level=None):
 		"""
 		Given a package that's in the graph, do a rough check to
-- 
2.0.4

Re: [gentoo-portage-dev] [PATCH] _slot_operator_update_probe: memoize use_reduce (529660)

[Brian Dolbec]

On Mon, 17 Nov 2014 22:57:42 -0800
Zac Medico <zmedico@gentoo.org> wrote:

> Memoize the results of use_reduce calls inside
> _slot_operator_update_probe, in order to improve performance. With
> memoization, 'emerge -puvDN @world' on one of my computers takes
> 22.4% less time, and results in 13.5% fewer use_reduce calls.
> 
> X-Gentoo-Bug: 529660
> X-Gentoo-Url: https://bugs.gentoo.org/show_bug.cgi?id=529660
> ---

patch looks good, just did you mean "Memorize" & "memorization" instead
of "Memoize" & "memoization"

-- 
Brian Dolbec <dolsen>

Re: [gentoo-portage-dev] [PATCH] _slot_operator_update_probe: memoize use_reduce (529660)

[Zac Medico]

On 11/18/2014 08:13 AM, Brian Dolbec wrote:
> On Mon, 17 Nov 2014 22:57:42 -0800
> Zac Medico <zmedico@gentoo.org> wrote:
> 
>> Memoize the results of use_reduce calls inside
>> _slot_operator_update_probe, in order to improve performance. With
>> memoization, 'emerge -puvDN @world' on one of my computers takes
>> 22.4% less time, and results in 13.5% fewer use_reduce calls.
>>
>> X-Gentoo-Bug: 529660
>> X-Gentoo-Url: https://bugs.gentoo.org/show_bug.cgi?id=529660
>> ---
> 
> patch looks good, just did you mean "Memorize" & "memorization" instead
> of "Memoize" & "memoization"

I meant memoize [1], which doesn't seem to be included in common
spelling dictionaries, but nonetheless is valid technical jargon.

[1] http://en.wikipedia.org/wiki/Memoization
-- 
Thanks,
Zac

Re: [gentoo-portage-dev] [PATCH] _slot_operator_update_probe: memoize use_reduce (529660)

[Alexander Berntsen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 18/11/14 17:36, Zac Medico wrote:
>>> patch looks good, just did you mean "Memorize" & "memorization"
>>> instead of "Memoize" & "memoization"
> I meant memoize [1], which doesn't seem to be included in common 
> spelling dictionaries, but nonetheless is valid technical jargon.
Can confirm that this is established terminology.

Though I would write memoise/memoisation as I'm not American. :-]
- -- 
Alexander
bernalex@gentoo.org
https://secure.plaimi.net/~alexander
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iF4EAREIAAYFAlRsZMEACgkQRtClrXBQc7UIDAD8CkR+gGBu/asIwvVJX/Wrm4Xf
kqMCZNYdn0W+BwfMBiwA/3bKUrY19D8ZCN62oMK65jonbISP7rVUwPXOtc/XlJ/T
=jPzE
-----END PGP SIGNATURE-----