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-03-30 (13:09)
From: Alexander S. Usov <A.S.Usov@K...>
Subject: Re: [Caml-list] Impact of GC on memoized algorithm
On Wednesday 30 March 2005 14:34, Alex Baretta wrote:
> > In this case, if you are using an inappropriate data structure as the key
> > to the hash table then you may be getting a lot of clashes. In which
> > case, lots of time will be spent looking up elements in hash table's own
> > list implementation. IIRC, most of the time will then be spent in the
> > Hashtbl.find_rec function...
> This is rather unlikely. The key to the hashtable is a unique integer...
> Rather, what happens, time-wise, if I create a hashtable with 4096 slots
> and end up filling it with several million key-value pairs?

In the best case you end up with a few hundreds or even few thousands of 
elements per bucket. And it will make it really slow.
You should better increase a hashtable size by at least an order of magnitude,
or create a hash of hashes.

Best regards,