2
# Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007 The SCons Foundation
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:
12
# The above copyright notice and this permission notice shall be included
13
# in all copies or substantial portions of the Software.
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.
24
__revision__ = "src/engine/SCons/Memoize.py 2523 2007/12/12 09:37:41 knight"
28
A metaclass implementation to count hits and misses of the computed
29
values that various methods cache in memory.
31
Use of this modules assumes that wrapped methods be coded to cache their
32
values in a consistent way. Here is an example of wrapping a method
33
that returns a computed value, with no input parameters:
35
memoizer_counters = [] # Memoization
37
memoizer_counters.append(SCons.Memoize.CountValue('foo')) # Memoization
42
return self._memo['foo'] # Memoization
43
except KeyError: # Memoization
46
result = self.compute_foo_value()
48
self._memo['foo'] = result # Memoization
52
Here is an example of wrapping a method that will return different values
53
based on one or more input arguments:
55
def _bar_key(self, argument): # Memoization
56
return argument # Memoization
58
memoizer_counters.append(SCons.Memoize.CountDict('bar', _bar_key)) # Memoization
60
def bar(self, argument):
62
memo_key = argument # Memoization
64
memo_dict = self._memo['bar'] # Memoization
65
except KeyError: # Memoization
66
memo_dict = {} # Memoization
67
self._memo['dict'] = memo_dict # Memoization
70
return memo_dict[memo_key] # Memoization
71
except KeyError: # Memoization
74
result = self.compute_bar_value(argument)
76
memo_dict[memo_key] = result # Memoization
80
At one point we avoided replicating this sort of logic in all the methods
81
by putting it right into this module, but we've moved away from that at
82
present (see the "Historical Note," below.).
84
Deciding what to cache is tricky, because different configurations
85
can have radically different performance tradeoffs, and because the
86
tradeoffs involved are often so non-obvious. Consequently, deciding
87
whether or not to cache a given method will likely be more of an art than
88
a science, but should still be based on available data from this module.
89
Here are some VERY GENERAL guidelines about deciding whether or not to
90
cache return values from a method that's being called a lot:
92
-- The first question to ask is, "Can we change the calling code
93
so this method isn't called so often?" Sometimes this can be
94
done by changing the algorithm. Sometimes the *caller* should
95
be memoized, not the method you're looking at.
97
-- The memoized function should be timed with multiple configurations
98
to make sure it doesn't inadvertently slow down some other
101
-- When memoizing values based on a dictionary key composed of
102
input arguments, you don't need to use all of the arguments
103
if some of them don't affect the return values.
105
Historical Note: The initial Memoizer implementation actually handled
106
the caching of values for the wrapped methods, based on a set of generic
107
algorithms for computing hashable values based on the method's arguments.
108
This collected caching logic nicely, but had two drawbacks:
110
Running arguments through a generic key-conversion mechanism is slower
111
(and less flexible) than just coding these things directly. Since the
112
methods that need memoized values are generally performance-critical,
113
slowing them down in order to collect the logic isn't the right
116
Use of the memoizer really obscured what was being called, because
117
all the memoized methods were wrapped with re-used generic methods.
118
This made it more difficult, for example, to use the Python profiler
119
to figure out how to optimize the underlying methods.
124
# A flag controlling whether or not we actually use memoization.
131
Base class for counting memoization hits and misses.
133
We expect that the metaclass initialization will have filled in
134
the .name attribute that represents the name of the function
137
def __init__(self, method_name):
140
self.method_name = method_name
143
CounterList.append(self)
145
fmt = " %7d hits %7d misses %s()"
146
print fmt % (self.hit, self.miss, self.name)
147
def __cmp__(self, other):
149
return cmp(self.name, other.name)
150
except AttributeError:
153
class CountValue(Counter):
155
A counter class for simple, atomic memoized values.
157
A CountValue object should be instantiated in a class for each of
158
the class's methods that memoizes its return value by simply storing
159
the return value in its _memo dictionary.
161
We expect that the metaclass initialization will fill in the
162
.underlying_method attribute with the method that we're wrapping.
163
We then call the underlying_method method after counting whether
164
its memoized value has already been set (a hit) or not (a miss).
166
def __call__(self, *args, **kw):
168
if obj._memo.has_key(self.method_name):
169
self.hit = self.hit + 1
171
self.miss = self.miss + 1
172
return apply(self.underlying_method, args, kw)
174
class CountDict(Counter):
176
A counter class for memoized values stored in a dictionary, with
177
keys based on the method's input arguments.
179
A CountDict object is instantiated in a class for each of the
180
class's methods that memoizes its return value in a dictionary,
181
indexed by some key that can be computed from one or more of
184
We expect that the metaclass initialization will fill in the
185
.underlying_method attribute with the method that we're wrapping.
186
We then call the underlying_method method after counting whether the
187
computed key value is already present in the memoization dictionary
188
(a hit) or not (a miss).
190
def __init__(self, method_name, keymaker):
193
Counter.__init__(self, method_name)
194
self.keymaker = keymaker
195
def __call__(self, *args, **kw):
198
memo_dict = obj._memo[self.method_name]
200
self.miss = self.miss + 1
202
key = apply(self.keymaker, args, kw)
203
if memo_dict.has_key(key):
204
self.hit = self.hit + 1
206
self.miss = self.miss + 1
207
return apply(self.underlying_method, args, kw)
210
"""Object which performs caching of method calls for its 'primary'
216
# Find out if we support metaclasses (Python 2.2 and later).
219
def __init__(cls, name, bases, cls_dict):
220
cls.has_metaclass = 1
226
has_metaclass = A.has_metaclass
227
except AttributeError:
233
if not has_metaclass:
238
class Memoized_Metaclass:
239
# Just a place-holder so pre-metaclass Python versions don't
240
# have to have special code for the Memoized classes.
243
def EnableMemoization():
244
import SCons.Warnings
245
msg = 'memoization is not supported in this version of Python (no metaclasses)'
246
raise SCons.Warnings.NoMetaclassSupportWarning, msg
250
def Dump(title=None):
254
for counter in CounterList:
257
class Memoized_Metaclass(type):
258
def __init__(cls, name, bases, cls_dict):
259
super(Memoized_Metaclass, cls).__init__(name, bases, cls_dict)
261
for counter in cls_dict.get('memoizer_counters', []):
262
method_name = counter.method_name
264
counter.name = cls.__name__ + '.' + method_name
265
counter.underlying_method = cls_dict[method_name]
267
replacement_method = new.instancemethod(counter, None, cls)
268
setattr(cls, method_name, replacement_method)
270
def EnableMemoization():
added
removed
scons/scons-local-0.97.0d20071212/SCons/Memoize.py
