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

Source Code for Module SCons.Memoize

  1  # 
  2  # Copyright (c) 2001 - 2017 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  from __future__ import print_function 
 24   
 25  __revision__ = "src/engine/SCons/Memoize.py 74b2c53bc42290e911b334a6b44f187da698a668 2017/11/14 13:16:53 bdbaddog" 
 26   
 27  __doc__ = """Memoizer 
 28   
 29  A decorator-based implementation to count hits and misses of the computed 
 30  values that various methods cache in memory. 
 31   
 32  Use of this modules assumes that wrapped methods be coded to cache their 
 33  values in a consistent way. In particular, it requires that the class uses a 
 34  dictionary named "_memo" to store the cached values. 
 35   
 36  Here is an example of wrapping a method that returns a computed value, 
 37  with no input parameters:: 
 38   
 39      @SCons.Memoize.CountMethodCall 
 40      def foo(self): 
 41   
 42          try:                                                    # Memoization 
 43              return self._memo['foo']                            # Memoization 
 44          except KeyError:                                        # Memoization 
 45              pass                                                # Memoization 
 46   
 47          result = self.compute_foo_value() 
 48   
 49          self._memo['foo'] = result                              # Memoization 
 50   
 51          return result 
 52   
 53  Here is an example of wrapping a method that will return different values 
 54  based on one or more input arguments:: 
 55   
 56      def _bar_key(self, argument):                               # Memoization 
 57          return argument                                         # Memoization 
 58   
 59      @SCons.Memoize.CountDictCall(_bar_key) 
 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  Deciding what to cache is tricky, because different configurations 
 81  can have radically different performance tradeoffs, and because the 
 82  tradeoffs involved are often so non-obvious.  Consequently, deciding 
 83  whether or not to cache a given method will likely be more of an art than 
 84  a science, but should still be based on available data from this module. 
 85  Here are some VERY GENERAL guidelines about deciding whether or not to 
 86  cache return values from a method that's being called a lot: 
 87   
 88      --  The first question to ask is, "Can we change the calling code 
 89          so this method isn't called so often?"  Sometimes this can be 
 90          done by changing the algorithm.  Sometimes the *caller* should 
 91          be memoized, not the method you're looking at. 
 92   
 93      --  The memoized function should be timed with multiple configurations 
 94          to make sure it doesn't inadvertently slow down some other 
 95          configuration. 
 96   
 97      --  When memoizing values based on a dictionary key composed of 
 98          input arguments, you don't need to use all of the arguments 
 99          if some of them don't affect the return values. 
100   
101  """ 
102   
103  # A flag controlling whether or not we actually use memoization. 
104  use_memoizer = None 
105   
106  # Global list of counter objects 
107  CounterList = {} 
108   
109 -class Counter(object):
110 """ 111 Base class for counting memoization hits and misses. 112 113 We expect that the initialization in a matching decorator will 114 fill in the correct class name and method name that represents 115 the name of the function being counted. 116 """
117 - def __init__(self, cls_name, method_name):
118 """ 119 """ 120 self.cls_name = cls_name 121 self.method_name = method_name 122 self.hit = 0 123 self.miss = 0
124 - def key(self):
125 return self.cls_name+'.'+self.method_name
126 - def display(self):
127 print(" {:7d} hits {:7d} misses {}()".format(self.hit, self.miss, self.key()))
128 - def __eq__(self, other):
129 try: 130 return self.key() == other.key() 131 except AttributeError: 132 return True
133
134 -class CountValue(Counter):
135 """ 136 A counter class for simple, atomic memoized values. 137 138 A CountValue object should be instantiated in a decorator for each of 139 the class's methods that memoizes its return value by simply storing 140 the return value in its _memo dictionary. 141 """
142 - def count(self, *args, **kw):
143 """ Counts whether the memoized value has already been 144 set (a hit) or not (a miss). 145 """ 146 obj = args[0] 147 if self.method_name in obj._memo: 148 self.hit = self.hit + 1 149 else: 150 self.miss = self.miss + 1
151
152 -class CountDict(Counter):
153 """ 154 A counter class for memoized values stored in a dictionary, with 155 keys based on the method's input arguments. 156 157 A CountDict object is instantiated in a decorator for each of the 158 class's methods that memoizes its return value in a dictionary, 159 indexed by some key that can be computed from one or more of 160 its input arguments. 161 """
162 - def __init__(self, cls_name, method_name, keymaker):
163 """ 164 """ 165 Counter.__init__(self, cls_name, method_name) 166 self.keymaker = keymaker
167 - def count(self, *args, **kw):
168 """ Counts whether the computed key value is already present 169 in the memoization dictionary (a hit) or not (a miss). 170 """ 171 obj = args[0] 172 try: 173 memo_dict = obj._memo[self.method_name] 174 except KeyError: 175 self.miss = self.miss + 1 176 else: 177 key = self.keymaker(*args, **kw) 178 if key in memo_dict: 179 self.hit = self.hit + 1 180 else: 181 self.miss = self.miss + 1
182
183 -def Dump(title=None):
184 """ Dump the hit/miss count for all the counters 185 collected so far. 186 """ 187 if title: 188 print(title) 189 for counter in sorted(CounterList): 190 CounterList[counter].display()
191
192 -def EnableMemoization():
193 global use_memoizer 194 use_memoizer = 1
195
196 -def CountMethodCall(fn):
197 """ Decorator for counting memoizer hits/misses while retrieving 198 a simple value in a class method. It wraps the given method 199 fn and uses a CountValue object to keep track of the 200 caching statistics. 201 Wrapping gets enabled by calling EnableMemoization(). 202 """ 203 if use_memoizer: 204 def wrapper(self, *args, **kwargs): 205 global CounterList 206 key = self.__class__.__name__+'.'+fn.__name__ 207 if key not in CounterList: 208 CounterList[key] = CountValue(self.__class__.__name__, fn.__name__) 209 CounterList[key].count(self, *args, **kwargs) 210 return fn(self, *args, **kwargs)
211 wrapper.__name__= fn.__name__ 212 return wrapper 213 else: 214 return fn 215
216 -def CountDictCall(keyfunc):
217 """ Decorator for counting memoizer hits/misses while accessing 218 dictionary values with a key-generating function. Like 219 CountMethodCall above, it wraps the given method 220 fn and uses a CountDict object to keep track of the 221 caching statistics. The dict-key function keyfunc has to 222 get passed in the decorator call and gets stored in the 223 CountDict instance. 224 Wrapping gets enabled by calling EnableMemoization(). 225 """ 226 def decorator(fn): 227 if use_memoizer: 228 def wrapper(self, *args, **kwargs): 229 global CounterList 230 key = self.__class__.__name__+'.'+fn.__name__ 231 if key not in CounterList: 232 CounterList[key] = CountDict(self.__class__.__name__, fn.__name__, keyfunc) 233 CounterList[key].count(self, *args, **kwargs) 234 return fn(self, *args, **kwargs)
235 wrapper.__name__= fn.__name__ 236 return wrapper 237 else: 238 return fn 239 return decorator 240 241 # Local Variables: 242 # tab-width:4 243 # indent-tabs-mode:nil 244 # End: 245 # vim: set expandtab tabstop=4 shiftwidth=4: 246