summaryrefslogtreecommitdiff
path: root/src/engine/SCons/Memoize.py
diff options
context:
space:
mode:
Diffstat (limited to 'src/engine/SCons/Memoize.py')
-rw-r--r--src/engine/SCons/Memoize.py292
1 files changed, 292 insertions, 0 deletions
diff --git a/src/engine/SCons/Memoize.py b/src/engine/SCons/Memoize.py
new file mode 100644
index 0000000..fc79157
--- /dev/null
+++ b/src/engine/SCons/Memoize.py
@@ -0,0 +1,292 @@
+#
+# Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 The SCons Foundation
+#
+# Permission is hereby granted, free of charge, to any person obtaining
+# a copy of this software and associated documentation files (the
+# "Software"), to deal in the Software without restriction, including
+# without limitation the rights to use, copy, modify, merge, publish,
+# distribute, sublicense, and/or sell copies of the Software, and to
+# permit persons to whom the Software is furnished to do so, subject to
+# the following conditions:
+#
+# The above copyright notice and this permission notice shall be included
+# in all copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
+# KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
+# WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+# LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+# OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+# WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+#
+
+__revision__ = "src/engine/SCons/Memoize.py 4577 2009/12/27 19:44:43 scons"
+
+__doc__ = """Memoizer
+
+A metaclass implementation to count hits and misses of the computed
+values that various methods cache in memory.
+
+Use of this modules assumes that wrapped methods be coded to cache their
+values in a consistent way. Here is an example of wrapping a method
+that returns a computed value, with no input parameters:
+
+ memoizer_counters = [] # Memoization
+
+ memoizer_counters.append(SCons.Memoize.CountValue('foo')) # Memoization
+
+ def foo(self):
+
+ try: # Memoization
+ return self._memo['foo'] # Memoization
+ except KeyError: # Memoization
+ pass # Memoization
+
+ result = self.compute_foo_value()
+
+ self._memo['foo'] = result # Memoization
+
+ return result
+
+Here is an example of wrapping a method that will return different values
+based on one or more input arguments:
+
+ def _bar_key(self, argument): # Memoization
+ return argument # Memoization
+
+ memoizer_counters.append(SCons.Memoize.CountDict('bar', _bar_key)) # Memoization
+
+ def bar(self, argument):
+
+ memo_key = argument # Memoization
+ try: # Memoization
+ memo_dict = self._memo['bar'] # Memoization
+ except KeyError: # Memoization
+ memo_dict = {} # Memoization
+ self._memo['dict'] = memo_dict # Memoization
+ else: # Memoization
+ try: # Memoization
+ return memo_dict[memo_key] # Memoization
+ except KeyError: # Memoization
+ pass # Memoization
+
+ result = self.compute_bar_value(argument)
+
+ memo_dict[memo_key] = result # Memoization
+
+ return result
+
+At one point we avoided replicating this sort of logic in all the methods
+by putting it right into this module, but we've moved away from that at
+present (see the "Historical Note," below.).
+
+Deciding what to cache is tricky, because different configurations
+can have radically different performance tradeoffs, and because the
+tradeoffs involved are often so non-obvious. Consequently, deciding
+whether or not to cache a given method will likely be more of an art than
+a science, but should still be based on available data from this module.
+Here are some VERY GENERAL guidelines about deciding whether or not to
+cache return values from a method that's being called a lot:
+
+ -- The first question to ask is, "Can we change the calling code
+ so this method isn't called so often?" Sometimes this can be
+ done by changing the algorithm. Sometimes the *caller* should
+ be memoized, not the method you're looking at.
+
+ -- The memoized function should be timed with multiple configurations
+ to make sure it doesn't inadvertently slow down some other
+ configuration.
+
+ -- When memoizing values based on a dictionary key composed of
+ input arguments, you don't need to use all of the arguments
+ if some of them don't affect the return values.
+
+Historical Note: The initial Memoizer implementation actually handled
+the caching of values for the wrapped methods, based on a set of generic
+algorithms for computing hashable values based on the method's arguments.
+This collected caching logic nicely, but had two drawbacks:
+
+ Running arguments through a generic key-conversion mechanism is slower
+ (and less flexible) than just coding these things directly. Since the
+ methods that need memoized values are generally performance-critical,
+ slowing them down in order to collect the logic isn't the right
+ tradeoff.
+
+ Use of the memoizer really obscured what was being called, because
+ all the memoized methods were wrapped with re-used generic methods.
+ This made it more difficult, for example, to use the Python profiler
+ to figure out how to optimize the underlying methods.
+"""
+
+import new
+
+# A flag controlling whether or not we actually use memoization.
+use_memoizer = None
+
+CounterList = []
+
+class Counter:
+ """
+ Base class for counting memoization hits and misses.
+
+ We expect that the metaclass initialization will have filled in
+ the .name attribute that represents the name of the function
+ being counted.
+ """
+ def __init__(self, method_name):
+ """
+ """
+ self.method_name = method_name
+ self.hit = 0
+ self.miss = 0
+ CounterList.append(self)
+ def display(self):
+ fmt = " %7d hits %7d misses %s()"
+ print fmt % (self.hit, self.miss, self.name)
+ def __cmp__(self, other):
+ try:
+ return cmp(self.name, other.name)
+ except AttributeError:
+ return 0
+
+class CountValue(Counter):
+ """
+ A counter class for simple, atomic memoized values.
+
+ A CountValue object should be instantiated in a class for each of
+ the class's methods that memoizes its return value by simply storing
+ the return value in its _memo dictionary.
+
+ We expect that the metaclass initialization will fill in the
+ .underlying_method attribute with the method that we're wrapping.
+ We then call the underlying_method method after counting whether
+ its memoized value has already been set (a hit) or not (a miss).
+ """
+ def __call__(self, *args, **kw):
+ obj = args[0]
+ if obj._memo.has_key(self.method_name):
+ self.hit = self.hit + 1
+ else:
+ self.miss = self.miss + 1
+ return apply(self.underlying_method, args, kw)
+
+class CountDict(Counter):
+ """
+ A counter class for memoized values stored in a dictionary, with
+ keys based on the method's input arguments.
+
+ A CountDict object is instantiated in a class for each of the
+ class's methods that memoizes its return value in a dictionary,
+ indexed by some key that can be computed from one or more of
+ its input arguments.
+
+ We expect that the metaclass initialization will fill in the
+ .underlying_method attribute with the method that we're wrapping.
+ We then call the underlying_method method after counting whether the
+ computed key value is already present in the memoization dictionary
+ (a hit) or not (a miss).
+ """
+ def __init__(self, method_name, keymaker):
+ """
+ """
+ Counter.__init__(self, method_name)
+ self.keymaker = keymaker
+ def __call__(self, *args, **kw):
+ obj = args[0]
+ try:
+ memo_dict = obj._memo[self.method_name]
+ except KeyError:
+ self.miss = self.miss + 1
+ else:
+ key = apply(self.keymaker, args, kw)
+ if memo_dict.has_key(key):
+ self.hit = self.hit + 1
+ else:
+ self.miss = self.miss + 1
+ return apply(self.underlying_method, args, kw)
+
+class Memoizer:
+ """Object which performs caching of method calls for its 'primary'
+ instance."""
+
+ def __init__(self):
+ pass
+
+# Find out if we support metaclasses (Python 2.2 and later).
+
+class M:
+ def __init__(cls, name, bases, cls_dict):
+ cls.use_metaclass = 1
+ def fake_method(self):
+ pass
+ new.instancemethod(fake_method, None, cls)
+
+try:
+ class A:
+ __metaclass__ = M
+
+ use_metaclass = A.use_metaclass
+except AttributeError:
+ use_metaclass = None
+ reason = 'no metaclasses'
+except TypeError:
+ use_metaclass = None
+ reason = 'new.instancemethod() bug'
+else:
+ del A
+
+del M
+
+if not use_metaclass:
+
+ def Dump(title):
+ pass
+
+ try:
+ class Memoized_Metaclass(type):
+ # Just a place-holder so pre-metaclass Python versions don't
+ # have to have special code for the Memoized classes.
+ pass
+ except TypeError:
+ class Memoized_Metaclass:
+ # A place-holder so pre-metaclass Python versions don't
+ # have to have special code for the Memoized classes.
+ pass
+
+ def EnableMemoization():
+ import SCons.Warnings
+ msg = 'memoization is not supported in this version of Python (%s)'
+ raise SCons.Warnings.NoMetaclassSupportWarning, msg % reason
+
+else:
+
+ def Dump(title=None):
+ if title:
+ print title
+ CounterList.sort()
+ for counter in CounterList:
+ counter.display()
+
+ class Memoized_Metaclass(type):
+ def __init__(cls, name, bases, cls_dict):
+ super(Memoized_Metaclass, cls).__init__(name, bases, cls_dict)
+
+ for counter in cls_dict.get('memoizer_counters', []):
+ method_name = counter.method_name
+
+ counter.name = cls.__name__ + '.' + method_name
+ counter.underlying_method = cls_dict[method_name]
+
+ replacement_method = new.instancemethod(counter, None, cls)
+ setattr(cls, method_name, replacement_method)
+
+ def EnableMemoization():
+ global use_memoizer
+ use_memoizer = 1
+
+# Local Variables:
+# tab-width:4
+# indent-tabs-mode:nil
+# End:
+# vim: set expandtab tabstop=4 shiftwidth=4: