memoize source code

1 module memoize;
2 
3 import std.traits;
4 
5 /**
6 The following code makes cached (memoized) property `f`
7 ```
8 class {
9     @property string _f() { ... }
10     mixin CachedProperty!"f";
11 }
12 ```
13 */
14 mixin template CachedProperty(string name, string baseName = '_' ~ name) {
15     mixin("private typeof(" ~ baseName ~ ") " ~ name ~ "Cache;");
16     mixin("private bool " ~ name ~ "IsCached = false;");
17     mixin("@property typeof(" ~ baseName ~ ") " ~ name ~ "() {\n" ~
18           "if (" ~ name ~ "IsCached" ~ ") return " ~ name ~ "Cache;\n" ~
19           name ~ "IsCached = true;\n" ~
20           "return " ~ name ~ "Cache = " ~ baseName ~ ";\n" ~
21           '}');
22 }
23 
24 unittest {
25     struct S {
26         @property float _x() { return 1.5; }
27         mixin CachedProperty!"x";
28     }
29     class C {
30         @property float _x() { return 1.5; }
31         mixin CachedProperty!"x";
32     }
33     S s;
34     assert(s.x == 1.5);
35     assert(s.x == 1.5);
36     C c = new C();
37     assert(c.x == 1.5);
38 }
39 
40 private template _memoize(alias fun, string attr)
41 {
42     // alias Args = Parameters!fun; // Bugzilla 13580
43 
44     ReturnType!fun _memoize(Parameters!fun args)
45     {
46         alias Args = Parameters!fun;
47         import std.typecons : Tuple;
48 
49         mixin(attr ~ " static Unqual!(ReturnType!fun)[Tuple!Args] memo;");
50         auto t = Tuple!Args(args);
51         if (auto p = t in memo)
52             return *p;
53         return memo[t] = fun(args);
54     }
55 }
56 
57 private template _memoize(alias fun, uint maxSize, string modifier)
58 {
59     // alias Args = Parameters!fun; // Bugzilla 13580
60     ReturnType!fun _memoize(Parameters!fun args)
61     {
62         import std.traits : hasIndirections;
63         import std.typecons : tuple;
64         static struct Value { Parameters!fun args; ReturnType!fun res; }
65         mixin(modifier ~ " static Unqual!(Value)[] memo;");
66         mixin(modifier ~ " static size_t[] initialized;");
67 
68         if (!memo.length)
69         {
70             import core.memory : GC;
71 
72             // Ensure no allocation overflows
73             static assert(maxSize < size_t.max / Value.sizeof);
74             static assert(maxSize < size_t.max - (8 * size_t.sizeof - 1));
75 
76             enum attr = GC.BlkAttr.NO_INTERIOR | (hasIndirections!Value ? 0 : GC.BlkAttr.NO_SCAN);
77             mixin("alias VType = " ~ modifier ~ " Value;");
78             memo = (cast(VType*) GC.malloc(Value.sizeof * maxSize, attr))[0 .. maxSize];
79             enum nwords = (maxSize + 8 * size_t.sizeof - 1) / (8 * size_t.sizeof);
80             mixin("alias mysize_t = " ~ modifier ~ " size_t;");
81             initialized = (cast(mysize_t*) GC.calloc(nwords * size_t.sizeof, attr | GC.BlkAttr.NO_SCAN))[0 .. nwords];
82         }
83 
84         import core.bitop : bt, bts;
85         import std.conv : emplace;
86 
87         size_t hash;
88         foreach (ref arg; args)
89             hash = hashOf(arg, hash);
90         // cuckoo hashing
91         immutable idx1 = hash % maxSize;
92         if (!bt(cast(size_t*) initialized.ptr, idx1))
93         {
94             emplace(&memo[idx1], args, fun(args));
95             bts(cast(size_t*) initialized.ptr, idx1); // only set to initialized after setting args and value (bugzilla 14025)
96             return memo[idx1].res;
97         }
98         else if (memo[idx1].args == args)
99             return memo[idx1].res;
100         // FNV prime
101         immutable idx2 = (hash * 16_777_619) % maxSize;
102         if (!bt(cast(size_t*) initialized.ptr, idx2))
103         {
104             emplace(&memo[idx2], memo[idx1]);
105             bts(cast(size_t*) initialized.ptr, idx2); // only set to initialized after setting args and value (bugzilla 14025)
106         }
107         else if (memo[idx2].args == args)
108             return memo[idx2].res;
109         else if (idx1 != idx2)
110             memo[idx2] = memo[idx1];
111 
112         memo[idx1] = Value(args, fun(args));
113         return memo[idx1].res;
114     }
115 }
116 
117 // See https://issues.dlang.org/show_bug.cgi?id=4533 why aliases are not used.
118 
119 /**
120 The same as in Phobos `std.functional`.
121 */
122 //alias memoize(alias fun) = _memoize!(fun, "");
123 template memoize(alias fun)
124 {
125     ReturnType!fun memoize(Parameters!fun args)
126     {
127         return _memoize!(fun, "")(args);
128     }
129 }
130 
131 /// ditto
132 //alias memoize(alias fun, uint maxSize) = _memoize!(fun, maxSize, "");
133 template memoize(alias fun, uint maxSize)
134 {
135     ReturnType!fun memoize(Parameters!fun args)
136     {
137         return _memoize!(fun, maxSize, "")(args);
138     }
139 }
140 
141 /// must be locked explicitly!
142 //alias noLockMemoize(alias fun) = _memoize!(fun, "shared");
143 template noLockMemoize(alias fun)
144 {
145     ReturnType!fun noLockMemoize(Parameters!fun args)
146     {
147         return _memoize!(fun, "shared")(args);
148     }
149 }
150 
151 /// must be locked explicitly!
152 //alias noLockMemoize(alias fun, uint maxSize) = _memoize!(fun, maxSize, "shared");
153 template noLockMemoize(alias fun, uint maxSize)
154 {
155     ReturnType!fun noLockMemoize(Parameters!fun args)
156     {
157         return _memoize!(fun, maxSize, "shared")(args);
158     }
159 }
160 
161 /**
162 Synchronized version of `memoize` using global (interthread) cache.
163 */
164 template synchronizedMemoize(alias fun) {
165     private alias impl = memoize!fun;
166     ReturnType!fun synchronizedMemoize(Parameters!fun args) {
167         synchronized {
168             return impl(args);
169         }
170     }
171 }
172 
173 /// ditto
174 template synchronizedMemoize(alias fun, uint maxSize) {
175     private alias impl = memoize!(fun, maxSize);
176     ReturnType!fun synchronizedMemoize(Parameters!fun args) {
177         synchronized {
178             return impl(args);
179         }
180     }
181 }
182 
183 @safe unittest
184 {
185     ulong fib(ulong n) @safe
186     {
187         return n < 2 ? n : memoize!fib(n - 2) + memoize!fib(n - 1);
188     }
189     assert(fib(10) == 55);
190     ulong fib2(ulong n) @safe
191     {
192         return n < 2 ? n : synchronizedMemoize!fib2(n - 2) + synchronizedMemoize!fib2(n - 1);
193     }
194     assert(fib2(10) == 55);
195 }
196 
197 @safe unittest
198 {
199     ulong fact(ulong n) @safe
200     {
201         return n < 2 ? 1 : n * memoize!fact(n - 1);
202     }
203     assert(fact(10) == 3628800);
204     ulong fact2(ulong n) @safe
205     {
206         return n < 2 ? 1 : n * synchronizedMemoize!fact2(n - 1);
207     }
208     assert(fact2(10) == 3628800);
209 }
210 
211 @safe unittest
212 {
213     ulong factImpl(ulong n) @safe
214     {
215         return n < 2 ? 1 : n * factImpl(n - 1);
216     }
217     alias fact = memoize!factImpl;
218     assert(fact(10) == 3628800);
219     ulong factImpl2(ulong n) @safe
220     {
221         return n < 2 ? 1 : n * factImpl2(n - 1);
222     }
223     alias fact2 = synchronizedMemoize!factImpl;
224     assert(fact2(10) == 3628800);
225 }
226 
227 @system unittest // not @safe due to memoize
228 {
229     ulong fact(ulong n)
230     {
231         // Memoize no more than 8 values
232         return n < 2 ? 1 : n * memoize!(fact, 8)(n - 1);
233     }
234     assert(fact(8) == 40320);
235     // using more entries than maxSize will overwrite existing entries
236     assert(fact(10) == 3628800);
237     ulong fact2(ulong n)
238     {
239         // Memoize no more than 8 values
240         return n < 2 ? 1 : n * synchronizedMemoize!(fact2, 8)(n - 1);
241     }
242     assert(fact2(8) == 40320);
243     // using more entries than maxSize will overwrite existing entries
244     assert(fact2(10) == 3628800);
245 }
246 
247 /**
248 Use it to memoize both a struct or class instance for a member function and function arguments like:
249 ```
250 struct S {
251     int f(int a, int b) {
252         return a + b;
253     }
254 }
255 alias f2 = memoizeMember!(S, "f");
256 alias f3 = memoizeMember!(S, "f", 10);
257 S s;
258 assert(f2(s, 2, 3) == 5);
259 ```
260 
261 As you see the member function name ("f" in the example) is passed as a string.
262 This is very unnatural, but I found no other way to do it.
263 */
264 template memoizeMember(S, string name) {
265     alias Member = __traits(getMember, S, name);
266     ReturnType!Member f(S s, Parameters!Member others) {
267         return __traits(getMember, s, name)(others);
268     }
269     alias memoizeMember = memoize!f;
270 }
271 
272 /// ditto
273 template memoizeMember(S, string name, uint maxSize) {
274     alias Member = __traits(getMember, S, name);
275     ReturnType!Member f(S s, Parameters!Member others) {
276         return __traits(getMember, s, name)(others);
277     }
278     alias memoizeMember = memoize!(f, maxSize);
279 }
280 
281 /// ditto
282 template noLockMemoizeMember(S, string name) {
283     alias Member = __traits(getMember, S, name);
284     ReturnType!Member f(S s, Parameters!Member others) {
285         return __traits(getMember, s, name)(others);
286     }
287     alias noLockMemoizeMember = noLockMemoize!f;
288 }
289 
290 /// ditto
291 template noLockMemoizeMember(S, string name, uint maxSize) {
292     alias Member = __traits(getMember, S, name);
293     ReturnType!Member f(S s, Parameters!Member others) {
294         return __traits(getMember, s, name)(others);
295     }
296     alias noLockMemoizeMember = noLockMemoize!(f, maxSize);
297 }
298 
299 /// ditto
300 template synchronizedMemoizeMember(S, string name) {
301     alias Member = __traits(getMember, S, name);
302     ReturnType!Member f(S s, Parameters!Member others) {
303         return __traits(getMember, s, name)(others);
304     }
305     alias synchronizedMemoizeMember = synchronizedMemoize!f;
306 }
307 
308 /// ditto
309 template synchronizedMemoizeMember(S, string name, uint maxSize) {
310     alias Member = __traits(getMember, S, name);
311     ReturnType!Member f(S s, Parameters!Member others) {
312         return __traits(getMember, s, name)(others);
313     }
314     alias synchronizedMemoizeMember = synchronizedMemoize!(f, maxSize);
315 }
316 
317 unittest {
318     struct S2 {
319         int f(int a, int b) {
320             return a + b;
321         }
322     }
323     alias f2 = memoizeMember!(S2, "f");
324     alias f3 = memoizeMember!(S2, "f", 10);
325     alias f4 = synchronizedMemoizeMember!(S2, "f");
326     alias f5 = synchronizedMemoizeMember!(S2, "f", 10);
327     S2 s;
328     assert(f2(s, 2, 3) == 5);
329     assert(f2(s, 2, 3) == 5);
330     assert(f3(s, 2, 3) == 5);
331     assert(f4(s, 2, 3) == 5);
332     assert(f5(s, 2, 3) == 5);
333 }