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

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

Cool!

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.

Lutger wrote:
> 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.

Dynamic programming and memoization might came handy when doing intensive string processing with templates. I did some benchmarking with runtime versions of "longest common substring" in D a while ago. It might be pretty easy to convert them into templates. Haven't done much template magic, though.

On Sat, 16 Dec 2006 08:11:09 +0200, Chris Nicholson-Sauls <ibisbasenji@gmail.com> 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


Heheh, nice! I was considering implementing similar thing in C++ a while ago. The solution is so simple in D. :)

Nice, I really like these type of algorithms.  I once wrote a C++ one to move the vtable of objects to a local area in memory to avoid double seeking.   One optimisation you may consider (if it hasn't already been added is:

Change
> #         p_cache[node] = Func(args);
> #         result = node in p_cache;

To

> #         result = Func(args);
> #	    p_cache[node] = result;

That way you avoid an unnecessary lookups.  Unless D is smart enough to do the optimisation itself which would be nice but unlikely.

Chris Nicholson-Sauls wrote:
> # 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;
> #     }
> #   }
> # }


> -- Chris Nicholson-Sauls

janderson wrote:
> Nice, I really like these type of algorithms.  I once wrote a C++ one to move the vtable of objects to a local area in memory to avoid double seeking.   One optimisation you may consider (if it hasn't already been added is:
> 
> Change
>  > #         p_cache[node] = Func(args);
>  > #         result = node in p_cache;
> 
> To
> 
>  > #         result = Func(args);
>  > #        p_cache[node] = result;

Actually I ended up changing these to 'return p_cache[node] = Func(args);'.  Even quicker.  :)  The only problem with your suggested way is that 'result' is a pointer, and I can't take the address of a return value (I don't think...).

-- Chris Nicholson-Sauls