1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 __revision__ = "src/engine/SCons/Memoize.py rel_2.4.0:3365:9259ea1c13d7 2015/09/21 14:03:43 bdbaddog"
25
26 __doc__ = """Memoizer
27
28 A decorator-based 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. In particular, it requires that the class uses a
33 dictionary named "_memo" to store the cached values.
34
35 Here is an example of wrapping a method that returns a computed value,
36 with 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
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 @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
79 Deciding what to cache is tricky, because different configurations
80 can have radically different performance tradeoffs, and because the
81 tradeoffs involved are often so non-obvious. Consequently, deciding
82 whether or not to cache a given method will likely be more of an art than
83 a science, but should still be based on available data from this module.
84 Here are some VERY GENERAL guidelines about deciding whether or not to
85 cache 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
103 use_memoizer = None
104
105
106 CounterList = {}
107
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
124 return self.cls_name+'.'+self.method_name
126 fmt = " %7d hits %7d misses %s()"
127 print fmt % (self.hit, self.miss, self.key())
129 try:
130 return cmp(self.key(), other.key())
131 except AttributeError:
132 return 0
133
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
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
195
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
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
242
243
244
245
246