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

[Alex Baretta <alex@barettadeit.com>]

Damien Doligez wrote:
> On Mar 30, 2005, at 17:03, Alex Baretta wrote:

> Anyway, the total cost of a major collection cycle is proportional to
> the heap size, but the frequency of these cycles is inversely proportional
> to the heap size.  Hence, under reasonable assumptions, average GC cost is
> constant for each word that you allocate.

This is what I was hoping for.

> Of course, the picture becomes entirely different if you have lots of
> explicit calls to Gc.major, Gc.full_major, or Gc.compact.

No, I don't, so the cost of memoization should only impact the 
multiplicative constant and not the complexity class of my algorithm. 
This is good. Now I'll have to experiment with Maps and Hashtbls with 
and without custom hash functions to find the most efficient caching 
scheme. Any suggestions?

Alex

-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>