Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Impact of GC on memoized algorithm
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-04-11 (15:48)
From: Alex Baretta <alex@b...>
Subject: Re: [Caml-list] Impact of GC on memoized algorithm
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?


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)

The FreerP Project