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 // Ugh, repeated code
41 private template _memoize(alias fun, string attr)
42 {
43     // alias Args = Parameters!fun; // Bugzilla 13580
44 
45     ReturnType!fun _memoize(const(Parameters!fun) args)
46     {
47         alias Args = Parameters!fun;
48         import std.typecons : Tuple;
49 
50         mixin(attr ~ " static Unqual!(ReturnType!fun)[Tuple!Args] memo;");
51         auto t = Tuple!Args(args);
52         if (auto p = t in memo)
53             return *p;
54         return memo[t] = fun(args);
55     }
56 }
57 
58 private template _referenceMemoize(alias fun, string attr)
59 {
60     // alias Args = Parameters!fun; // Bugzilla 13580
61 
62     ref Unqual!(ReturnType!fun) _referenceMemoize(const(Parameters!fun) args)
63     {
64         alias Args = Parameters!fun;
65         import std.typecons : Tuple;
66 
67         static ReturnType!fun*[Tuple!Args] memo;
68         auto t = Tuple!Args(args);
69         if (auto p = t in memo) return **p;
70         memo[t] = &fun(args);
71         return *memo[t];
72     }
73 }
74 
75 // TODO: It does not compile when modifier != ""
76 // (also compiling with different modifiers would use more program memory)
77 private template _memoize(alias fun, uint maxSize, string modifier)
78 {
79     // alias Args = Parameters!fun; // Bugzilla 13580
80     // Ugh, repeated code
81     ReturnType!fun _memoize(const(Parameters!fun) args)
82     {
83         import std.traits : hasIndirections;
84         import std.typecons : tuple;
85         static struct Value { const(Parameters!fun) args; ReturnType!fun res; }
86         mixin(modifier ~ " static Unqual!(Value)[] memo;");
87         mixin(modifier ~ " static size_t[] initialized;");
88 
89         if (!memo.length)
90         {
91             import core.memory : GC;
92 
93             // Ensure no allocation overflows
94             static assert(maxSize < size_t.max / Value.sizeof);
95             static assert(maxSize < size_t.max - (8 * size_t.sizeof - 1));
96 
97             enum attr = GC.BlkAttr.NO_INTERIOR | (hasIndirections!Value ? 0 : GC.BlkAttr.NO_SCAN);
98             mixin("alias VType = " ~ modifier ~ " Value;");
99             memo = (cast(VType*) GC.malloc(Value.sizeof * maxSize, attr))[0 .. maxSize];
100             enum nwords = (maxSize + 8 * size_t.sizeof - 1) / (8 * size_t.sizeof);
101             mixin("alias mysize_t = " ~ modifier ~ " size_t;");
102             initialized = (cast(mysize_t*) GC.calloc(nwords * size_t.sizeof, attr | GC.BlkAttr.NO_SCAN))[0 .. nwords];
103         }
104 
105         import core.bitop : bt, bts;
106         import std.conv : emplace;
107 
108         size_t hash;
109         foreach (ref arg; args)
110             hash = hashOf(arg, hash);
111         // cuckoo hashing
112         immutable idx1 = hash % maxSize;
113         if (!bt(cast(size_t*) initialized.ptr, idx1))
114         {
115             emplace(cast(Unqual!(Value*)) &memo[idx1], args, fun(args));
116             bts(cast(size_t*) initialized.ptr, idx1); // only set to initialized after setting args and value (bugzilla 14025)
117             return memo[idx1].res;
118         }
119         else if (memo[idx1].args == args)
120             return memo[idx1].res;
121         // FNV prime
122         immutable idx2 = (hash * 16_777_619) % maxSize;
123         if (!bt(cast(size_t*) initialized.ptr, idx2))
124         {
125             emplace(&memo[idx2], memo[idx1]);
126             bts(cast(size_t*) initialized.ptr, idx2); // only set to initialized after setting args and value (bugzilla 14025)
127         }
128         else if (memo[idx2].args == args)
129             return memo[idx2].res;
130         else if (idx1 != idx2)
131             memo[idx2] = memo[idx1];
132 
133         memo[idx1] = Value(args, fun(args));
134         return memo[idx1].res;
135     }
136 }
137 
138 private template _referenceMemoize(alias fun, uint maxSize, string modifier)
139 {
140     ref Unqual!(ReturnType!fun) _referenceMemoize(const(Parameters!fun) args)
141     {
142         import std.traits : hasIndirections;
143         import std.typecons : tuple;
144         static struct Value { const(Parameters!fun) args; ReturnType!fun *res; }
145         mixin(modifier ~ " static Unqual!(Value)*[] memo;");
146         mixin(modifier ~ " static size_t[] initialized;");
147 
148         if (!memo.length)
149         {
150             import core.memory : GC;
151 
152             // Ensure no allocation overflows
153             static assert(maxSize < size_t.max / Value.sizeof);
154             static assert(maxSize < size_t.max - (8 * size_t.sizeof - 1));
155 
156             enum attr = GC.BlkAttr.NO_INTERIOR | (hasIndirections!Value ? 0 : GC.BlkAttr.NO_SCAN);
157             mixin("alias VType = " ~ modifier ~ " Value;");
158             memo = (cast(VType*) GC.malloc(Value.sizeof * maxSize, attr))[0 .. maxSize];
159             enum nwords = (maxSize + 8 * size_t.sizeof - 1) / (8 * size_t.sizeof);
160             mixin("alias mysize_t = " ~ modifier ~ " size_t;");
161             initialized = (cast(mysize_t*) GC.calloc(nwords * size_t.sizeof, attr | GC.BlkAttr.NO_SCAN))[0 .. nwords];
162         }
163 
164         import core.bitop : bt, bts;
165         import std.conv : emplace;
166 
167         size_t hash;
168         foreach (ref arg; args)
169             hash = hashOf(arg, hash);
170         // cuckoo hashing
171         immutable idx1 = hash % maxSize;
172         if (!bt(cast(size_t*) initialized.ptr, idx1))
173         {
174             emplace(&memo[idx1], args, &fun(args));
175             bts(cast(size_t*) initialized.ptr, idx1); // only set to initialized after setting args and value (bugzilla 14025)
176             return *memo[idx1].res;
177         }
178         else if (memo[idx1].args == args)
179             return *memo[idx1].res;
180         // FNV prime
181         immutable idx2 = (hash * 16_777_619) % maxSize;
182         if (!bt(cast(size_t*) initialized.ptr, idx2))
183         {
184             emplace(&memo[idx2], memo[idx1]);
185             bts(cast(size_t*) initialized.ptr, idx2); // only set to initialized after setting args and value (bugzilla 14025)
186         }
187         else if (memo[idx2].args == args)
188             return *memo[idx2].res;
189         else if (idx1 != idx2)
190             memo[idx2] = memo[idx1];
191 
192         memo[idx1] = Value(args, &fun(args));
193         return *memo[idx1].res;
194     }
195 }
196 
197 // See https://issues.dlang.org/show_bug.cgi?id=4533 why aliases are not used.
198 
199 /**
200 The same as in Phobos `std.functional`.
201 */
202 //alias memoize(alias fun) = _memoize!(fun, "");
203 template memoize(alias fun)
204 {
205     ReturnType!fun memoize(const(Parameters!fun) args)
206     {
207         return _memoize!(fun, "")(args);
208     }
209 }
210 
211 template referenceMemoize(alias fun)
212 {
213     ref Unqual!(ReturnType!fun) referenceMemoize(const(Parameters!fun) args)
214     {
215         return _referenceMemoize!(fun, "")(args);
216     }
217 }
218 
219 /// ditto
220 //alias memoize(alias fun, uint maxSize) = _memoize!(fun, maxSize, "");
221 template memoize(alias fun, uint maxSize)
222 {
223     ReturnType!fun memoize(const(Parameters!fun) args)
224     {
225         return _memoize!(fun, maxSize, "")(args);
226     }
227 }
228 
229 template referenceMemoize(alias fun, uint maxSize)
230 {
231     ref Unqual!(ReturnType!fun) referenceMemoize(const(Parameters!fun) args)
232     {
233         return _referenceMemoize!(fun, maxSize, "")(args);
234     }
235 }
236 
237 /// must be locked explicitly!
238 //alias noLockMemoize(alias fun) = _memoize!(fun, "shared");
239 template noLockMemoize(alias fun)
240 {
241     ReturnType!fun noLockMemoize(const(Parameters!fun) args)
242     {
243         return _memoize!(fun, "shared")(args);
244     }
245 }
246 
247 template referenceNoLockMemoize(alias fun)
248 {
249     ref Unqual!(ReturnType!fun) referenceNoLockMemoize(const(Parameters!fun) args)
250     {
251         return _referenceMemoize!(fun, "shared")(args);
252     }
253 }
254 
255 /// must be locked explicitly!
256 //alias noLockMemoize(alias fun, uint maxSize) = _memoize!(fun, maxSize, "shared");
257 template noLockMemoize(alias fun, uint maxSize)
258 {
259     ReturnType!fun noLockMemoize(const(Parameters!fun) args)
260     {
261         //return _memoize!(fun, maxSize, "shared")(args); // does not compile
262         return _memoize!(fun, maxSize, "")(args);
263     }
264 }
265 
266 template referenceNoLockMemoize(alias fun, uint maxSize)
267 {
268     ref Unqual!(ReturnType!fun) referenceNoLockMemoize(const(Parameters!fun) args)
269     {
270         return _referenceMemoize!(fun, maxSize, "shared")(args);
271     }
272 }
273 
274 /**
275 Synchronized version of `memoize` using global (interthread) cache.
276 */
277 template synchronizedMemoize(alias fun) {
278     private alias impl = memoize!fun;
279     ReturnType!fun synchronizedMemoize(const(Parameters!fun) args) {
280         synchronized {
281             return impl(args);
282         }
283     }
284 }
285 
286 template referenceSynchronizedMemoize(alias fun) {
287     private alias impl = referenceMemoize!fun;
288     ref Unqual!(ReturnType!fun) referenceSynchronizedMemoize(const(Parameters!fun) args) {
289         synchronized {
290             return impl(args);
291         }
292     }
293 }
294 
295 /// ditto
296 template synchronizedMemoize(alias fun, uint maxSize) {
297     private alias impl = memoize!(fun, maxSize);
298     ReturnType!fun synchronizedMemoize(const(Parameters!fun) args) {
299         synchronized {
300             return impl(args);
301         }
302     }
303 }
304 
305 template referenceSynchronizedMemoize(alias fun, uint maxSize) {
306     private alias impl = referenceMemoize!(fun, maxSize);
307     ref Unqual!(ReturnType!fun) referenceSynchronizedMemoize(const(Parameters!fun) args) {
308         synchronized {
309             return impl(args);
310         }
311     }
312 }
313 
314 @safe unittest
315 {
316     ulong fib(ulong n) @safe
317     {
318         return n < 2 ? n : memoize!fib(n - 2) + memoize!fib(n - 1);
319     }
320     assert(fib(10) == 55);
321     ulong fib2(ulong n) @safe
322     {
323         return n < 2 ? n : synchronizedMemoize!fib2(n - 2) + synchronizedMemoize!fib2(n - 1);
324     }
325     assert(fib2(10) == 55);
326     ulong fib3(ulong n) @safe
327     {
328         return n < 2 ? n : noLockMemoize!fib3(n - 2) + noLockMemoize!fib3(n - 1);
329     }
330     assert(fib3(10) == 55);
331 }
332 
333 @safe unittest
334 {
335     ulong fact(ulong n) @safe
336     {
337         return n < 2 ? 1 : n * memoize!fact(n - 1);
338     }
339     assert(fact(10) == 3628800);
340     ulong fact2(ulong n) @safe
341     {
342         return n < 2 ? 1 : n * synchronizedMemoize!fact2(n - 1);
343     }
344     assert(fact2(10) == 3628800);
345     ulong fact3(ulong n) @safe
346     {
347         return n < 2 ? 1 : n * noLockMemoize!fact3(n - 1);
348     }
349     assert(fact3(10) == 3628800);
350 }
351 
352 @safe unittest
353 {
354     ulong factImpl(ulong n) @safe
355     {
356         return n < 2 ? 1 : n * factImpl(n - 1);
357     }
358     alias fact = memoize!factImpl;
359     assert(fact(10) == 3628800);
360     ulong factImpl2(ulong n) @safe
361     {
362         return n < 2 ? 1 : n * factImpl2(n - 1);
363     }
364     alias fact2 = synchronizedMemoize!factImpl;
365     assert(fact2(10) == 3628800);
366     ulong factImpl3(ulong n) @safe
367     {
368         return n < 2 ? 1 : n * factImpl3(n - 1);
369     }
370     alias fact3 = noLockMemoize!factImpl;
371     assert(fact3(10) == 3628800);
372 }
373 
374 @system unittest // not @safe due to memoize
375 {
376     ulong fact(ulong n)
377     {
378         // Memoize no more than 8 values
379         return n < 2 ? 1 : n * memoize!(fact, 8)(n - 1);
380     }
381     assert(fact(8) == 40320);
382     // using more entries than maxSize will overwrite existing entries
383     assert(fact(10) == 3628800);
384     ulong fact2(ulong n)
385     {
386         // Memoize no more than 8 values
387         return n < 2 ? 1 : n * synchronizedMemoize!(fact2, 8)(n - 1);
388     }
389     assert(fact2(8) == 40320);
390     // using more entries than maxSize will overwrite existing entries
391     assert(fact2(10) == 3628800);
392     ulong fact3(ulong n)
393     {
394         // Memoize no more than 8 values
395         return n < 2 ? 1 : n * noLockMemoize!(fact3, 8)(n - 1);
396     }
397     assert(fact3(8) == 40320);
398     // using more entries than maxSize will overwrite existing entries
399     assert(fact3(10) == 3628800);
400 }
401 
402 @system unittest
403 {
404     static ulong x;
405     ref ulong f()
406     {
407         return x;
408     }
409     assert(&referenceMemoize!f() == &x);
410     assert(&referenceSynchronizedMemoize!f() == &x);
411     assert(&referenceNoLockMemoize!f() == &x);
412 }
413 
414 /**
415 Use it to memoize both a struct or class instance for a member function and function arguments like:
416 ```
417 struct S {
418     int f(int a, int b) {
419         return a + b;
420     }
421 }
422 alias f2 = memoizeMember!(S, "f");
423 alias f3 = memoizeMember!(S, "f", 10);
424 S s;
425 assert(f2(s, 2, 3) == 5);
426 ```
427 
428 As you see the member function name ("f" in the example) is passed as a string.
429 This is very unnatural, but I found no other way to do it.
430 */
431 template memoizeMember(S, string name) {
432     alias Member = __traits(getMember, S, name);
433     ReturnType!Member f(S s, Parameters!Member others) {
434         return __traits(getMember, s, name)(others);
435     }
436     alias memoizeMember = memoize!f;
437 }
438 
439 template referenceMemoizeMember(S, string name) {
440     alias Member = __traits(getMember, S, name);
441     ref ReturnType!Member f(S s, Parameters!Member others) {
442         return __traits(getMember, s, name)(others);
443     }
444     alias referenceMemoizeMember = referenceMemoize!f;
445 }
446 
447 /// ditto
448 template memoizeMember(S, string name, uint maxSize) {
449     alias Member = __traits(getMember, S, name);
450     ReturnType!Member f(S s, Parameters!Member others) {
451         return __traits(getMember, s, name)(others);
452     }
453     alias memoizeMember = memoize!(f, maxSize);
454 }
455 
456 template referenceMemoizeMember(S, string name, uint maxSize) {
457     alias Member = __traits(getMember, S, name);
458     ref ReturnType!Member f(S s, Parameters!Member others) {
459         return __traits(getMember, s, name)(others);
460     }
461     alias referenceMemoizeMember = referenceMemoize!(f, maxSize);
462 }
463 
464 /// ditto
465 template noLockMemoizeMember(S, string name) {
466     alias Member = __traits(getMember, S, name);
467     ReturnType!Member f(S s, Parameters!Member others) {
468         return __traits(getMember, s, name)(others);
469     }
470     alias noLockMemoizeMember = noLockMemoize!f;
471 }
472 
473 template referenceNoLockMemoizeMember(S, string name) {
474     alias Member = __traits(getMember, S, name);
475     ref ReturnType!Member f(S s, Parameters!Member others) {
476         return __traits(getMember, s, name)(others);
477     }
478     alias referenceNoLockMemoizeMember = referenceNoLockMemoize!f;
479 }
480 
481 /// ditto
482 template noLockMemoizeMember(S, string name, uint maxSize) {
483     alias Member = __traits(getMember, S, name);
484     ReturnType!Member f(S s, Parameters!Member others) {
485         return __traits(getMember, s, name)(others);
486     }
487     alias noLockMemoizeMember = noLockMemoize!(f, maxSize);
488 }
489 
490 template referenceNoLockMemoizeMember(S, string name, uint maxSize) {
491     alias Member = __traits(getMember, S, name);
492     ref ReturnType!Member f(S s, Parameters!Member others) {
493         return __traits(getMember, s, name)(others);
494     }
495     alias referenceNoLockMemoizeMember = referenceNoLockMemoize!(f, maxSize);
496 }
497 
498 /// ditto
499 template synchronizedMemoizeMember(S, string name) {
500     alias Member = __traits(getMember, S, name);
501     ReturnType!Member f(S s, Parameters!Member others) {
502         return __traits(getMember, s, name)(others);
503     }
504     alias synchronizedMemoizeMember = synchronizedMemoize!f;
505 }
506 
507 template referenceSynchronizedMemoizeMember(S, string name) {
508     alias Member = __traits(getMember, S, name);
509     ref ReturnType!Member f(S s, Parameters!Member others) {
510         return __traits(getMember, s, name)(others);
511     }
512     alias referenceSynchronizedMemoizeMember = referenceSynchronizedMemoize!f;
513 }
514 
515 /// ditto
516 template synchronizedMemoizeMember(S, string name, uint maxSize) {
517     alias Member = __traits(getMember, S, name);
518     ReturnType!Member f(S s, Parameters!Member others) {
519         return __traits(getMember, s, name)(others);
520     }
521     alias synchronizedMemoizeMember = synchronizedMemoize!(f, maxSize);
522 }
523 
524 template referenceSynchronizedMemoizeMember(S, string name, uint maxSize) {
525     alias Member = __traits(getMember, S, name);
526     ref ReturnType!Member f(S s, Parameters!Member others) {
527         return __traits(getMember, s, name)(others);
528     }
529     alias referenceSynchronizedMemoizeMember = referenceSynchronizedMemoize!(f, maxSize);
530 }
531 
532 unittest {
533     struct S2 {
534         int f(int a, int b) {
535             return a + b;
536         }
537     }
538     alias f2 = memoizeMember!(S2, "f");
539     alias f3 = memoizeMember!(S2, "f", 10);
540     alias f4 = synchronizedMemoizeMember!(S2, "f");
541     alias f5 = synchronizedMemoizeMember!(S2, "f", 10);
542     alias f6 = noLockMemoizeMember!(S2, "f");
543     alias f7 = noLockMemoizeMember!(S2, "f", 10);
544     S2 s;
545     assert(f2(s, 2, 3) == 5);
546     assert(f2(s, 2, 3) == 5);
547     assert(f3(s, 2, 3) == 5);
548     assert(f4(s, 2, 3) == 5);
549     assert(f5(s, 2, 3) == 5);
550     assert(f6(s, 2, 3) == 5);
551     assert(f7(s, 2, 3) == 5);
552 }
553 
554 unittest {
555     int x;
556     struct S2 {
557         ref int f() {
558             return x;
559         }
560     }
561     S2 s;
562     assert(&referenceMemoizeMember!(S2, "f")(s) == &x);
563     assert(&referenceSynchronizedMemoizeMember!(S2, "f")(s) == &x);
564     assert(&referenceNoLockMemoizeMember!(S2, "f")(s) == &x);
565 }