Re: [boost] Memoization library

From: Beman Dawes (bdawes_at_[hidden])
Date: 2003-12-12 11:46:06

At 08:25 PM 12/11/2003, Jim Apple wrote:

 >Is there any interest in a memoization library?

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?

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

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?

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

* Caching of the last result is surprisingly helpful, but beyond that a 
cache has to be really large to do much good.
* Caching of some fairly small number (5 to 50) is quite helpful.
* Don't bother unless the cache is really large (thousands or more).
* The ratio of caching cost vs full computation cost affects decisions 
about caching strategy. Least recently used vs least recently added 
discards, for example.
* Self-tuning sounds attractive, but I've never actually implemented it.

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

--Beman