Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(816)

Side by Side Diff: scons-2.0.1/engine/SCons/Memoize.py

Issue 6711079: Added an unmodified copy of SCons to third_party. (Closed) Base URL: svn://svn.chromium.org/native_client/trunk/src/third_party/
Patch Set: '' Created 9 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « scons-2.0.1/engine/SCons/Job.py ('k') | scons-2.0.1/engine/SCons/Node/Alias.py » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Property Changes:
Added: svn:eol-style
+ LF
OLDNEW
(Empty)
1 #
2 # Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 The S Cons 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 5134 2010/08/16 23:02:40 bdeegan"
25
26 __doc__ = """Memoizer
27
28 A metaclass 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. Here is an example of wrapping a method
33 that returns a computed value, with no input parameters:
34
35 memoizer_counters = [] # Memoization
36
37 memoizer_counters.append(SCons.Memoize.CountValue('foo')) # Memoization
38
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 memoizer_counters.append(SCons.Memoize.CountDict('bar', _bar_key)) # Memoiza tion
59
60 def bar(self, argument):
61
62 memo_key = argument # Memoization
63 try: # Memoization
64 memo_dict = self._memo['bar'] # Memoization
65 except KeyError: # Memoization
66 memo_dict = {} # Memoization
67 self._memo['dict'] = memo_dict # Memoization
68 else: # Memoization
69 try: # Memoization
70 return memo_dict[memo_key] # Memoization
71 except KeyError: # Memoization
72 pass # Memoization
73
74 result = self.compute_bar_value(argument)
75
76 memo_dict[memo_key] = result # Memoization
77
78 return result
79
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.).
83
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:
91
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.
96
97 -- The memoized function should be timed with multiple configurations
98 to make sure it doesn't inadvertently slow down some other
99 configuration.
100
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.
104
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:
109
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
114 tradeoff.
115
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.
120 """
121
122 import types
123
124 # A flag controlling whether or not we actually use memoization.
125 use_memoizer = None
126
127 CounterList = []
128
129 class Counter(object):
130 """
131 Base class for counting memoization hits and misses.
132
133 We expect that the metaclass initialization will have filled in
134 the .name attribute that represents the name of the function
135 being counted.
136 """
137 def __init__(self, method_name):
138 """
139 """
140 self.method_name = method_name
141 self.hit = 0
142 self.miss = 0
143 CounterList.append(self)
144 def display(self):
145 fmt = " %7d hits %7d misses %s()"
146 print fmt % (self.hit, self.miss, self.name)
147 def __cmp__(self, other):
148 try:
149 return cmp(self.name, other.name)
150 except AttributeError:
151 return 0
152
153 class CountValue(Counter):
154 """
155 A counter class for simple, atomic memoized values.
156
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.
160
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).
165 """
166 def __call__(self, *args, **kw):
167 obj = args[0]
168 if self.method_name in obj._memo:
169 self.hit = self.hit + 1
170 else:
171 self.miss = self.miss + 1
172 return self.underlying_method(*args, **kw)
173
174 class CountDict(Counter):
175 """
176 A counter class for memoized values stored in a dictionary, with
177 keys based on the method's input arguments.
178
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
182 its input arguments.
183
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).
189 """
190 def __init__(self, method_name, keymaker):
191 """
192 """
193 Counter.__init__(self, method_name)
194 self.keymaker = keymaker
195 def __call__(self, *args, **kw):
196 obj = args[0]
197 try:
198 memo_dict = obj._memo[self.method_name]
199 except KeyError:
200 self.miss = self.miss + 1
201 else:
202 key = self.keymaker(*args, **kw)
203 if key in memo_dict:
204 self.hit = self.hit + 1
205 else:
206 self.miss = self.miss + 1
207 return self.underlying_method(*args, **kw)
208
209 class Memoizer(object):
210 """Object which performs caching of method calls for its 'primary'
211 instance."""
212
213 def __init__(self):
214 pass
215
216 def Dump(title=None):
217 if title:
218 print title
219 CounterList.sort()
220 for counter in CounterList:
221 counter.display()
222
223 class Memoized_Metaclass(type):
224 def __init__(cls, name, bases, cls_dict):
225 super(Memoized_Metaclass, cls).__init__(name, bases, cls_dict)
226
227 for counter in cls_dict.get('memoizer_counters', []):
228 method_name = counter.method_name
229
230 counter.name = cls.__name__ + '.' + method_name
231 counter.underlying_method = cls_dict[method_name]
232
233 replacement_method = types.MethodType(counter, None, cls)
234 setattr(cls, method_name, replacement_method)
235
236 def EnableMemoization():
237 global use_memoizer
238 use_memoizer = 1
239
240 # Local Variables:
241 # tab-width:4
242 # indent-tabs-mode:nil
243 # End:
244 # vim: set expandtab tabstop=4 shiftwidth=4:
OLDNEW
« no previous file with comments | « scons-2.0.1/engine/SCons/Job.py ('k') | scons-2.0.1/engine/SCons/Node/Alias.py » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698