[mercury-users] Memory consumption w/memoization

[Kral Stefan]

Hi.

On Fri, 23 Sep 2005, Zoltan Somogyi wrote:
> On 22-Sep-2005, Kral Stefan <skral at mips.complang.tuwien.ac.at> wrote:
> > Is there a way to limit the amount of memory used for the 
> > memoization of a predicate?
> 
> No, not at the moment. We have recognized the issue, 
> and I know that some other people have also implemented 
> probabilistic memoization, where you memo only e.g. 5% of answers.
> (On transitive closure of graphs, this gets most of the available 
> speedup, if I recall the relevant paper correctly.) I don't know 
> of any widely disseminated systems that have such facilities, but
> then again I haven't looked lately.
> 
> This has always been on my list of ideas to try sometime later, 
> the reason I haven't taken it up being the lack of a representative 
> application. If you think you have one, I would be glad to work 
> on it with you.
I see. I'm flattered by your offer;-)

Unfortunately, it appears as though my little micro-benchmarks 
(like binary-splitting fibonacci) are best implemented using
explicit memoization, as this allows to use both memoization 
_and_ unique modes (for immediate reuse of some GMP integers).

Generally, I think the great thing about _transparent memoization_
(like it is present already in Mercury) is that it allows the 
application programmer to experiment with it, without having 
to alter the implementation of the program. 

The alternative (turning everything upside down, doing it in a 
bottom-up instead of a top-down style, explicitly threading and
handling the cache) does not seem so attractive.

That way, the (admittedly few) points within an application 
(where memoization is beneficial) can easily be identified,
by turning on and off some pragmas, doing a few tests, analysing
the runtime data, and finally deciding which points seem worthwhile.

> There are several design issues to consider, such as what method of
> controlling space consumption is actually best for users, and how 
> the time overhead of the extra checks required and the extra 
> recomputation required can be traded off against the time required
> to actually memo answers as well as the space consumed by answers.
Regarding the fibonacci I would like to be able to specify 
	:- pragma memo(fib/2, [cache_lru=25]).
which specifies a maximum of 25 solutions is memoized.
(I favor that over the specification of some memory limit.)

Also, it would be nice to have some goal/directive that is 
explicitly inserted by the application programmer, that is 
declaratively a nop, but operationally lets the runtime system
forget all memoizated solutions of some given predicate.

Best Regards,
Stefan.

--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------