SCons/Memoize.py

   1 # MIT License
   2 #
   3 # Copyright The SCons Foundation
   4 #
   5 # Permission is hereby granted, free of charge, to any person obtaining
   6 # a copy of this software and associated documentation files (the
   7 # "Software"), to deal in the Software without restriction, including
   8 # without limitation the rights to use, copy, modify, merge, publish,
   9 # distribute, sublicense, and/or sell copies of the Software, and to
  10 # permit persons to whom the Software is furnished to do so, subject to
  11 # the following conditions:
  12 #
  13 # The above copyright notice and this permission notice shall be included
  14 # in all copies or substantial portions of the Software.
  15 #
  16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
  17 # KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  18 # WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  19 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  20 # LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  21 # OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  22 # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23
  24 """Decorator-based memoizer to count caching stats.
  25
  26 A decorator-based implementation to count hits and misses of the computed
  27 values that various methods cache in memory.
  28
  29 Use of this modules assumes that wrapped methods be coded to cache their
  30 values in a consistent way. In particular, it requires that the class uses a
  31 dictionary named "_memo" to store the cached values.
  32
  33 Here is an example of wrapping a method that returns a computed value,
  34 with no input parameters::
  35
  36     @SCons.Memoize.CountMethodCall
  37     def foo(self):
  38
  39         try:                                                    # Memoization
  40             return self._memo['foo']                            # Memoization
  41         except KeyError:                                        # Memoization
  42             pass                                                # Memoization
  43
  44         result = self.compute_foo_value()
  45
  46         self._memo['foo'] = result                              # Memoization
  47
  48         return result
  49
  50 Here is an example of wrapping a method that will return different values
  51 based on one or more input arguments::
  52
  53     def _bar_key(self, argument):                               # Memoization
  54         return argument                                         # Memoization
  55
  56     @SCons.Memoize.CountDictCall(_bar_key)
  57     def bar(self, argument):
  58
  59         memo_key = argument                                     # Memoization
  60         try:                                                    # Memoization
  61             memo_dict = self._memo['bar']                       # Memoization
  62         except KeyError:                                        # Memoization
  63             memo_dict = {}                                      # Memoization
  64             self._memo['dict'] = memo_dict                      # Memoization
  65         else:                                                   # Memoization
  66             try:                                                # Memoization
  67                 return memo_dict[memo_key]                      # Memoization
  68             except KeyError:                                    # Memoization
  69                 pass                                            # Memoization
  70
  71         result = self.compute_bar_value(argument)
  72
  73         memo_dict[memo_key] = result                            # Memoization
  74
  75         return result
  76
  77 Deciding what to cache is tricky, because different configurations
  78 can have radically different performance tradeoffs, and because the
  79 tradeoffs involved are often so non-obvious.  Consequently, deciding
  80 whether or not to cache a given method will likely be more of an art than
  81 a science, but should still be based on available data from this module.
  82 Here are some VERY GENERAL guidelines about deciding whether or not to
  83 cache return values from a method that's being called a lot:
  84
  85     --  The first question to ask is, "Can we change the calling code
  86         so this method isn't called so often?"  Sometimes this can be
  87         done by changing the algorithm.  Sometimes the *caller* should
  88         be memoized, not the method you're looking at.
  89
  90     --  The memoized function should be timed with multiple configurations
  91         to make sure it doesn't inadvertently slow down some other
  92         configuration.
  93
  94     --  When memoizing values based on a dictionary key composed of
  95         input arguments, you don't need to use all of the arguments
  96         if some of them don't affect the return values.
  97
  98 """
  99
 100 # A flag controlling whether or not we actually use memoization.
 101 use_memoizer = None
 102
 103 # Global list of counter objects
 104 CounterList = {}
 105
 106 class Counter:
 107     """
 108     Base class for counting memoization hits and misses.
 109
 110     We expect that the initialization in a matching decorator will
 111     fill in the correct class name and method name that represents
 112     the name of the function being counted.
 113     """
 114     def __init__(self, cls_name, method_name) -> None:
 115         """
 116         """
 117         self.cls_name = cls_name
 118         self.method_name = method_name
 119         self.hit = 0
 120         self.miss = 0
 121     def key(self):
 122         return self.cls_name+'.'+self.method_name
 123     def display(self) -> None:
 124         print(f"    {self.hit:7d} hits {self.miss:7d} misses    {self.key()}()")
 125     def __eq__(self, other):
 126         try:
 127             return self.key() == other.key()
 128         except AttributeError:
 129             return True
 130
 131 class CountValue(Counter):
 132     """
 133     A counter class for simple, atomic memoized values.
 134
 135     A CountValue object should be instantiated in a decorator for each of
 136     the class's methods that memoizes its return value by simply storing
 137     the return value in its _memo dictionary.
 138     """
 139     def count(self, *args, **kw) -> None:
 140         """ Counts whether the memoized value has already been
 141             set (a hit) or not (a miss).
 142         """
 143         obj = args[0]
 144         if self.method_name in obj._memo:
 145             self.hit = self.hit + 1
 146         else:
 147             self.miss = self.miss + 1
 148
 149 class CountDict(Counter):
 150     """
 151     A counter class for memoized values stored in a dictionary, with
 152     keys based on the method's input arguments.
 153
 154     A CountDict object is instantiated in a decorator for each of the
 155     class's methods that memoizes its return value in a dictionary,
 156     indexed by some key that can be computed from one or more of
 157     its input arguments.
 158     """
 159     def __init__(self, cls_name, method_name, keymaker) -> None:
 160         """
 161         """
 162         super().__init__(cls_name, method_name)
 163         self.keymaker = keymaker
 164     def count(self, *args, **kw) -> None:
 165         """ Counts whether the computed key value is already present
 166            in the memoization dictionary (a hit) or not (a miss).
 167         """
 168         obj = args[0]
 169         try:
 170             memo_dict = obj._memo[self.method_name]
 171         except KeyError:
 172             self.miss = self.miss + 1
 173         else:
 174             key = self.keymaker(*args, **kw)
 175             if key in memo_dict:
 176                 self.hit = self.hit + 1
 177             else:
 178                 self.miss = self.miss + 1
 179
 180 def Dump(title=None) -> None:
 181     """ Dump the hit/miss count for all the counters
 182         collected so far.
 183     """
 184     if title:
 185         print(title)
 186     for counter in sorted(CounterList):
 187         CounterList[counter].display()
 188
 189 def EnableMemoization() -> None:
 190     global use_memoizer
 191     use_memoizer = 1
 192
 193 def CountMethodCall(fn):
 194     """ Decorator for counting memoizer hits/misses while retrieving
 195         a simple value in a class method. It wraps the given method
 196         fn and uses a CountValue object to keep track of the
 197         caching statistics.
 198         Wrapping gets enabled by calling EnableMemoization().
 199     """
 200     if use_memoizer:
 201         def wrapper(self, *args, **kwargs):
 202             global CounterList
 203             key = self.__class__.__name__+'.'+fn.__name__
 204             if key not in CounterList:
 205                 CounterList[key] = CountValue(self.__class__.__name__, fn.__name__)
 206             CounterList[key].count(self, *args, **kwargs)
 207             return fn(self, *args, **kwargs)
 208         wrapper.__name__= fn.__name__
 209         return wrapper
 210     else:
 211         return fn
 212
 213 def CountDictCall(keyfunc):
 214     """ Decorator for counting memoizer hits/misses while accessing
 215         dictionary values with a key-generating function. Like
 216         CountMethodCall above, it wraps the given method
 217         fn and uses a CountDict object to keep track of the
 218         caching statistics. The dict-key function keyfunc has to
 219         get passed in the decorator call and gets stored in the
 220         CountDict instance.
 221         Wrapping gets enabled by calling EnableMemoization().
 222     """
 223     def decorator(fn):
 224         if use_memoizer:
 225             def wrapper(self, *args, **kwargs):
 226                 global CounterList
 227                 key = self.__class__.__name__+'.'+fn.__name__
 228                 if key not in CounterList:
 229                     CounterList[key] = CountDict(self.__class__.__name__, fn.__name__, keyfunc)
 230                 CounterList[key].count(self, *args, **kwargs)
 231                 return fn(self, *args, **kwargs)
 232             wrapper.__name__= fn.__name__
 233             return wrapper
 234         else:
 235             return fn
 236     return decorator
 237
 238 # Local Variables:
 239 # tab-width:4
 240 # indent-tabs-mode:nil
 241 # End:
 242 # vim: set expandtab tabstop=4 shiftwidth=4: