cpp/scons/scons-local-2.0.0.final.0/SCons/Memoize.py

   1 #
   2 # Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 The SCons Foundation
   3 #
   4 # Permission is hereby granted, free of charge, to any person obtaining
   5 # a copy of this software and associated documentation files (the
   6 # "Software"), to deal in the Software without restriction, including
   7 # without limitation the rights to use, copy, modify, merge, publish,
   8 # distribute, sublicense, and/or sell copies of the Software, and to
   9 # permit persons to whom the Software is furnished to do so, subject to
  10 # the following conditions:
  11 #
  12 # The above copyright notice and this permission notice shall be included
  13 # in all copies or substantial portions of the Software.
  14 #
  15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
  16 # KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  17 # WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  19 # LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  20 # OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  21 # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22 #
  23
  24 __revision__ = "src/engine/SCons/Memoize.py 5023 2010/06/14 22:05:46 scons"
  25
  26 __doc__ = """Memoizer
  27
  28 A metaclass implementation to count hits and misses of the computed
  29 values that various methods cache in memory.
  30
  31 Use of this modules assumes that wrapped methods be coded to cache their
  32 values in a consistent way.  Here is an example of wrapping a method
  33 that returns a computed value, with no input parameters:
  34
  35     memoizer_counters = []                                      # Memoization
  36
  37     memoizer_counters.append(SCons.Memoize.CountValue('foo'))   # Memoization
  38
  39     def foo(self):
  40
  41         try:                                                    # Memoization
  42             return self._memo['foo']                            # Memoization
  43         except KeyError:                                        # Memoization
  44             pass                                                # Memoization
  45
  46         result = self.compute_foo_value()
  47
  48         self._memo['foo'] = result                              # Memoization
  49
  50         return result
  51
  52 Here is an example of wrapping a method that will return different values
  53 based on one or more input arguments:
  54
  55     def _bar_key(self, argument):                               # Memoization
  56         return argument                                         # Memoization
  57
  58     memoizer_counters.append(SCons.Memoize.CountDict('bar', _bar_key)) # Memoization
  59
  60     def bar(self, argument):
  61
  62         memo_key = argument                                     # Memoization
  63         try:                                                    # Memoization
  64             memo_dict = self._memo['bar']                       # Memoization
  65         except KeyError:                                        # Memoization
  66             memo_dict = {}                                      # Memoization
  67             self._memo['dict'] = memo_dict                      # Memoization
  68         else:                                                   # Memoization
  69             try:                                                # Memoization
  70                 return memo_dict[memo_key]                      # Memoization
  71             except KeyError:                                    # Memoization
  72                 pass                                            # Memoization
  73
  74         result = self.compute_bar_value(argument)
  75
  76         memo_dict[memo_key] = result                            # Memoization
  77
  78         return result
  79
  80 At one point we avoided replicating this sort of logic in all the methods
  81 by putting it right into this module, but we've moved away from that at
  82 present (see the "Historical Note," below.).
  83
  84 Deciding what to cache is tricky, because different configurations
  85 can have radically different performance tradeoffs, and because the
  86 tradeoffs involved are often so non-obvious.  Consequently, deciding
  87 whether or not to cache a given method will likely be more of an art than
  88 a science, but should still be based on available data from this module.
  89 Here are some VERY GENERAL guidelines about deciding whether or not to
  90 cache return values from a method that's being called a lot:
  91
  92     --  The first question to ask is, "Can we change the calling code
  93         so this method isn't called so often?"  Sometimes this can be
  94         done by changing the algorithm.  Sometimes the *caller* should
  95         be memoized, not the method you're looking at.
  96
  97     --  The memoized function should be timed with multiple configurations
  98         to make sure it doesn't inadvertently slow down some other
  99         configuration.
 100
 101     --  When memoizing values based on a dictionary key composed of
 102         input arguments, you don't need to use all of the arguments
 103         if some of them don't affect the return values.
 104
 105 Historical Note:  The initial Memoizer implementation actually handled
 106 the caching of values for the wrapped methods, based on a set of generic
 107 algorithms for computing hashable values based on the method's arguments.
 108 This collected caching logic nicely, but had two drawbacks:
 109
 110     Running arguments through a generic key-conversion mechanism is slower
 111     (and less flexible) than just coding these things directly.  Since the
 112     methods that need memoized values are generally performance-critical,
 113     slowing them down in order to collect the logic isn't the right
 114     tradeoff.
 115
 116     Use of the memoizer really obscured what was being called, because
 117     all the memoized methods were wrapped with re-used generic methods.
 118     This made it more difficult, for example, to use the Python profiler
 119     to figure out how to optimize the underlying methods.
 120 """
 121
 122 import types
 123
 124 # A flag controlling whether or not we actually use memoization.
 125 use_memoizer = None
 126
 127 CounterList = []
 128
 129 class Counter(object):
 130     """
 131     Base class for counting memoization hits and misses.
 132
 133     We expect that the metaclass initialization will have filled in
 134     the .name attribute that represents the name of the function
 135     being counted.
 136     """
 137     def __init__(self, method_name):
 138         """
 139         """
 140         self.method_name = method_name
 141         self.hit = 0
 142         self.miss = 0
 143         CounterList.append(self)
 144     def display(self):
 145         fmt = "    %7d hits %7d misses    %s()"
 146         print fmt % (self.hit, self.miss, self.name)
 147     def __cmp__(self, other):
 148         try:
 149             return cmp(self.name, other.name)
 150         except AttributeError:
 151             return 0
 152
 153 class CountValue(Counter):
 154     """
 155     A counter class for simple, atomic memoized values.
 156
 157     A CountValue object should be instantiated in a class for each of
 158     the class's methods that memoizes its return value by simply storing
 159     the return value in its _memo dictionary.
 160
 161     We expect that the metaclass initialization will fill in the
 162     .underlying_method attribute with the method that we're wrapping.
 163     We then call the underlying_method method after counting whether
 164     its memoized value has already been set (a hit) or not (a miss).
 165     """
 166     def __call__(self, *args, **kw):
 167         obj = args[0]
 168         if self.method_name in obj._memo:
 169             self.hit = self.hit + 1
 170         else:
 171             self.miss = self.miss + 1
 172         return self.underlying_method(*args, **kw)
 173
 174 class CountDict(Counter):
 175     """
 176     A counter class for memoized values stored in a dictionary, with
 177     keys based on the method's input arguments.
 178
 179     A CountDict object is instantiated in a class for each of the
 180     class's methods that memoizes its return value in a dictionary,
 181     indexed by some key that can be computed from one or more of
 182     its input arguments.
 183
 184     We expect that the metaclass initialization will fill in the
 185     .underlying_method attribute with the method that we're wrapping.
 186     We then call the underlying_method method after counting whether the
 187     computed key value is already present in the memoization dictionary
 188     (a hit) or not (a miss).
 189     """
 190     def __init__(self, method_name, keymaker):
 191         """
 192         """
 193         Counter.__init__(self, method_name)
 194         self.keymaker = keymaker
 195     def __call__(self, *args, **kw):
 196         obj = args[0]
 197         try:
 198             memo_dict = obj._memo[self.method_name]
 199         except KeyError:
 200             self.miss = self.miss + 1
 201         else:
 202             key = self.keymaker(*args, **kw)
 203             if key in memo_dict:
 204                 self.hit = self.hit + 1
 205             else:
 206                 self.miss = self.miss + 1
 207         return self.underlying_method(*args, **kw)
 208
 209 class Memoizer(object):
 210     """Object which performs caching of method calls for its 'primary'
 211     instance."""
 212
 213     def __init__(self):
 214         pass
 215
 216 def Dump(title=None):
 217     if title:
 218         print title
 219     CounterList.sort()
 220     for counter in CounterList:
 221         counter.display()
 222
 223 class Memoized_Metaclass(type):
 224     def __init__(cls, name, bases, cls_dict):
 225         super(Memoized_Metaclass, cls).__init__(name, bases, cls_dict)
 226
 227         for counter in cls_dict.get('memoizer_counters', []):
 228             method_name = counter.method_name
 229
 230             counter.name = cls.__name__ + '.' + method_name
 231             counter.underlying_method = cls_dict[method_name]
 232
 233             replacement_method = types.MethodType(counter, None, cls)
 234             setattr(cls, method_name, replacement_method)
 235
 236 def EnableMemoization():
 237     global use_memoizer
 238     use_memoizer = 1
 239
 240 # Local Variables:
 241 # tab-width:4
 242 # indent-tabs-mode:nil
 243 # End:
 244 # vim: set expandtab tabstop=4 shiftwidth=4: