[boost] Re: [ATT:Jim Apple] Memoization Library status?

From: Jim Apple (japple_at_[hidden])
Date: 2004-08-15 00:55:08

Mattias Flodin wrote:
> In December last year, Jim Apple asked if there was interest in a
> memoization library he was working on. [1] It seems there were several
> people interested in this, but I have seen no more posts about it. Was
> this project discontinued? Are there other boosters working on a
> library like this?

I cut short work when I faced what I considered a very serious 
thread-safety issue.  Thread safety not only becomes an issue in the 
tricky cases (clearing the cache after every top-level call, clearing 
the cache manually), but also in the simplest case. I could lose 
substantial time saving benefits if the would-be-saved calculations are 
on a different threads and can't see the work that each is doing.

I should have, at this point asked a couple of new questions:
1. Are there any thread gurus who want to work with me on this?
2. Is there any interest in a memoization library that is known to be 
thread-UNsafe?
3. How do lazy languages (Clean, Haskell) deal with this issue?

> 
> Dave Abrahams pointed out (in [2]) that a library such as this may
> need the ability to invalidate parts of the cache, but was met with
> confusion and I don't think the motivation for the need was widely
> understood.

I have developed methods for clearing the cache automatically when a 
global variable or passed parameter changes. Partial invalidation is not 
something I have considered.

> With a memoization library that knows about parameter dependencies, we
> would be able to try many different values of this parameter and only
> the dependent parts of the cache would be invalidated, which could
> save hours if not days of processing time.

A suggestion:

image intro_step(const image &)
image final_step(const image &)

Assume intro_step depends on no globals, but final_step does. Give them 
different caches, then manually clear final_step's every time you change 
a global. Am I missing the point?

Jim