Re: [Caml-list] Impact of GC on memoized algorithm

[Jan Kybic <kybic@fel.cvut.cz>]

> In my experience, it is important to pay attention to the cost of the
> hashing function.  If you can avoid going through the whole structure to
> compute the hash, you'll save a lot of time.
> 
> It may also be a good idea to limit the number of cache entries, instead
> of just letting the cache grow arbitrarily large.  I've had good results
> by deleting some entries at random when the cache gets too big.

Exactly. When the cache size exceeds your real RAM, it is often
cheaper to recalculate the value instead of retrieving it from the
disk (swap).  I have good experience with deleting the oldest (by
order of creation) and cheapest-to-recalculate entries when memory
becomes scarce by alternatively filling several (linked) hash tables.
The heuristic needs monitoring the current memory consumption, the
size of the items and timing the memoized operations.

On the other hand, an exact LRU (last recently used) cache based on
doubly-linked lists did not work well for me, the cost of maintaining
the links was too high.

The best trade-off obviously depends on the size of your items and
keys, cost of recalculating the items, and on the access
pattern... Experimenting is probably unavoidable.

Jan

-- 
-------------------------------------------------------------------------
Jan Kybic <kybic@fel.cvut.cz>                       tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic                      ICQ 200569450