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 (14:22)
From: Damien Doligez <damien.doligez@i...>
Subject: Re: [Caml-list] Impact of GC on memoized algorithm
On Mar 30, 2005, at 17:03, Alex Baretta wrote:

> And, then again, how does the Gc.full_major scale as the "cache" for 
> the algorithm fills up with millions of key-value pairs? Is the GC 
> linear on the number of *reclaimed* blocks, or is it linear in the 
> *total* number of allocated blocks?

Why did you have to ask this question on the first day of my vacation? 

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

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

-- Damien