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
26A decorator-based implementation to count hits and misses of the computed
27values that various methods cache in memory.
28
29Use of this modules assumes that wrapped methods be coded to cache their
30values in a consistent way. In particular, it requires that the class uses a
31dictionary named "_memo" to store the cached values.
32
33Here is an example of wrapping a method that returns a computed value,
34with 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
50Here is an example of wrapping a method that will return different values
51based 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
77Deciding what to cache is tricky, because different configurations
78can have radically different performance tradeoffs, and because the
79tradeoffs involved are often so non-obvious.  Consequently, deciding
80whether or not to cache a given method will likely be more of an art than
81a science, but should still be based on available data from this module.
82Here are some VERY GENERAL guidelines about deciding whether or not to
83cache 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.
101use_memoizer = None
102
103# Global list of counter objects
104CounterList = {}
105
106class 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):
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):
124        print("    {:7d} hits {:7d} misses    {}()".format(self.hit, self.miss, self.key()))
125    def __eq__(self, other):
126        try:
127            return self.key() == other.key()
128        except AttributeError:
129            return True
130
131class 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):
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
149class 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):
160        """
161        """
162        Counter.__init__(self, cls_name, method_name)
163        self.keymaker = keymaker
164    def count(self, *args, **kw):
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
180def Dump(title=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
189def EnableMemoization():
190    global use_memoizer
191    use_memoizer = 1
192
193def 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
213def 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:
243