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

Page generated by adrdox