[boost] Re: Memoization library

From: Jim Apple (japple_at_[hidden])
Date: 2003-12-12 19:03:49

Beman Dawes wrote:
> This may be a stupid question, since I've no experience with the caching 
> of math function results, but do you propose to build memoization on top 
> of a general cache facility?

By cache facility, I assume you mean some sort of associative container. 
  If instead you're talking about serialization/persistence, then I 
agree that memoization would benefit from that.  Over different 
invocations of an application, a function becomes more lookup and less 
function? Faboo! Do I think this is necessary for memoization to be very 
useful? No.

Now, assuming you're talking about associative containers

The present prototype takes a type parameter memo_wrap, that, in turn, 
takes a type parameter.  At present, memo_wrap is specialized only for 
map, but a specialization for std::unordered_set would be good, and the 
interface would support a container that optimizes access for most 
accessed objects.

> If so, would it make sense to work on the cache facility first?

First? I don't think so. It yields big advantages for simple containers 
like std::map.

Should a cache facility be developed? I DO think so. It would certainly 
yeild advantages to memoization

> Also, would there be any benefit in specifying the cache facility as a 
> memoization policy, so that different caches with different performance 
> characteristics could be supplied according to user needs?

Yes.

> I do have considerable experience with the caching of the results of 
> search function, and have seen or read about various situations:
> 
 > [snip]

These results would be very helpful if built into different cache types. 
   These benefits would show up in memoization mostly for non-recursive 
functions.

> Given all that variability, policy-based caching might be very attractive.

I agree strongly.

Jim