1#
2# Copyright (c) 2001 - 2016 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 rel_2.5.0:3543:937e55cd78f7 2016/04/09 11:29:54 bdbaddog"
25
26__doc__ = """Memoizer
27
28A decorator-based implementation to count hits and misses of the computed
29values that various methods cache in memory.
30
31Use of this modules assumes that wrapped methods be coded to cache their
32values in a consistent way. In particular, it requires that the class uses a
33dictionary named "_memo" to store the cached values.
34
35Here is an example of wrapping a method that returns a computed value,
36with no input parameters:
37
38    @SCons.Memoize.CountMethodCall
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
52Here is an example of wrapping a method that will return different values
53based on one or more input arguments:
54
55    def _bar_key(self, argument):                               # Memoization
56        return argument                                         # Memoization
57
58    @SCons.Memoize.CountDictCall(_bar_key)
59    def bar(self, argument):
60
61        memo_key = argument                                     # Memoization
62        try:                                                    # Memoization
63            memo_dict = self._memo['bar']                       # Memoization
64        except KeyError:                                        # Memoization
65            memo_dict = {}                                      # Memoization
66            self._memo['dict'] = memo_dict                      # Memoization
67        else:                                                   # Memoization
68            try:                                                # Memoization
69                return memo_dict[memo_key]                      # Memoization
70            except KeyError:                                    # Memoization
71                pass                                            # Memoization
72
73        result = self.compute_bar_value(argument)
74
75        memo_dict[memo_key] = result                            # Memoization
76
77        return result
78
79Deciding what to cache is tricky, because different configurations
80can have radically different performance tradeoffs, and because the
81tradeoffs involved are often so non-obvious.  Consequently, deciding
82whether or not to cache a given method will likely be more of an art than
83a science, but should still be based on available data from this module.
84Here are some VERY GENERAL guidelines about deciding whether or not to
85cache return values from a method that's being called a lot:
86
87    --  The first question to ask is, "Can we change the calling code
88        so this method isn't called so often?"  Sometimes this can be
89        done by changing the algorithm.  Sometimes the *caller* should
90        be memoized, not the method you're looking at.
91
92    --  The memoized function should be timed with multiple configurations
93        to make sure it doesn't inadvertently slow down some other
94        configuration.
95
96    --  When memoizing values based on a dictionary key composed of
97        input arguments, you don't need to use all of the arguments
98        if some of them don't affect the return values.
99
100"""
101
102# A flag controlling whether or not we actually use memoization.
103use_memoizer = None
104
105# Global list of counter objects
106CounterList = {}
107
108class Counter(object):
109    """
110    Base class for counting memoization hits and misses.
111
112    We expect that the initialization in a matching decorator will
113    fill in the correct class name and method name that represents
114    the name of the function being counted.
115    """
116    def __init__(self, cls_name, method_name):
117        """
118        """
119        self.cls_name = cls_name
120        self.method_name = method_name
121        self.hit = 0
122        self.miss = 0
123    def key(self):
124        return self.cls_name+'.'+self.method_name
125    def display(self):
126        fmt = "    %7d hits %7d misses    %s()"
127        print fmt % (self.hit, self.miss, self.key())
128    def __cmp__(self, other):
129        try:
130            return cmp(self.key(), other.key())
131        except AttributeError:
132            return 0
133
134class 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
152class 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
183def 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
192def EnableMemoization():
193    global use_memoizer
194    use_memoizer = 1
195
196def 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
216def 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