PoC: Cached function calls

[Lutger]

Chris Nicholson-Sauls wrote:
> A discussion on this group caused me to add a new feature to a 
> hypothetical scripting language I've been toying around with for a 
> couple months or so.  It looks, basically, like this:
> 
> # cache Int fibidx (Int n) {
> #   if (n < 2) return n;
> #   else       return fibidx(n - 1) + fibidx(n - 2);
> # }
> 
> The nifty feature is the keyword 'cache' up there, which causes the 
> function 'fibidx' to be evaluated /exactly once/ for a given parameter 
> list.  (Granted in the case of Fibonacci one can easily accomplish what 
> I'm talking about with a class, but I thought it'd make a simple 
> demonstration case.)
> 
> So I got to thinking... wouldn't it be nifty to have this, or something 
> like it, in D! With that in mind, I tried to think up a way it might be 
> accomplished -- I hadn't yet actually tried to do anything with any of 
> D's nifty new templating features, namely tuples.  Well, I've learned a 
> few things anyhow.  :)  The following actually works!
> 
> # import std .traits ;
> #
> # struct TCachedFunc (alias Func) { static:
> #
> #   alias ReturnType         !(Func) Ret    ;
> #   alias ParameterTypeTuple !(Func) Params ;
> #
> #   static if (is(typeof(Params[1]))) {
> #     // multiple parameters
> #
> #     private struct Node {
> #       Params params ;
> #     }
> #
> #     private Ret[Node] p_cache ;
> #
> #     Ret opCall (Params args) {
> #       Node node   ;
> #       Ret* result ;
> #
> #       foreach (i, x; args) {
> #         node.params[i] = x;
> #       }
> #       result = node in p_cache;
> #
> #       if (!result) {
> #         p_cache[node] = Func(args);
> #         result = node in p_cache;
> #       }
> #       return *result;
> #     }
> #   }
> #   else {
> #     // single parameter
> #
> #     alias Params[0] Param ;
> #
> #     private Ret[Param] p_cache ;
> #
> #     Ret opCall (Param arg) {
> #       Ret* result = arg in p_cache;
> #
> #       if (!result) {
> #         p_cache[arg] = Func(arg);
> #         result = arg in p_cache;
> #       }
> #       return *result;
> #     }
> #   }
> # }
> 
> Given a 'fibidx' D function like the one above, one may use this 
> template to create a cached version by simply aliasing the template.  
> For example:
> # alias TCachedFunc!(fibidx) fibidx_cached;
> 
> Then just call it like normal.  I timed such a function as a means of 
> testing the template.  The results follow (in order: normal function 
> call, initial use of cache, a second use of the cache):
> <Benchmark TCachedFunc> Baseline 17.520000
> <Benchmark TCachedFunc> Time 16.810000 & 1.042237 versus baseline
> <Benchmark TCachedFunc> Time 0.000000 & inf versus baseline
> 
> Just, wow.  That said, it really only exhibits any benefits for 
> functions of some reasonable complexity, or with deep recursion that 
> eats up cycles (like a fib function ;)).  Anything that would normally 
> be inlined by the compiler will definitely perform better with a normal 
> call.
> 
> Anyhow, I just thought someone might find it interesting.  Maybe even 
> useful.  I'm considering it for inclusion in Cashew, once I figure out 
> how to properly do this with a delegate as well.
> 
> -- Chris Nicholson-Sauls

That is pretty cool. The technique is called memoization iirc. One 
problem is that functions in D are not guaranteed to be referentially 
transparent, thus for some class of functions the result will be 
incorrect (also there have to be no side-effects of course). But the 
user could determine that calling the function with the same arguments 
will always lead to the same result, so I think it is useful anyway if 
you are aware of that, thanks.