Package SCons :: Module Memoize
[hide private]
[frames] | no frames]

Source Code for Module SCons.Memoize

  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: 245