Impact of GC on memoized algorithm

Impact of GC on memoized algorithm

[Alex Baretta]

I am trying to fine tune a "cut stock" optimization algorithm which I 
have written for Ocaml. It so happens that the vanilla recursive 
implementation is quite fast, relatively to other implementations I've 
seen, whereas the memoized implementation is very slow. The vanilla 
implementation has a memory footprint of only a few megabytes, whereas 
the memoized version takes up some 60 MB on the same input. Quite 
obviously, the hashtable used to cache the results suffers from the 
combinatorial explosion of possible inputs. Now, given this, it is 
expected that the memoized version be as slow or slightly slower than 
the non memoized version, but it is not obvious why it would be a couple 
of orders of magnitude slower.

I have come to think that the difference in performance might be 
attributable to the garbage collector. This might be the case if the 
complexity of a collection is proportional to the total allocated 
memory, because the overall allocation/reclaiming cost of a fresh block 
would be proportional to the total number of allocated blocks.

Is my diagnosis correct? That is, is the GC collection a O(n) algorithm? 
  Would the C-language malloc/free model be any faster here? As far as I 
know malloc keeps a linked list of free blocks, which is also O(n).

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/>

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

[Jon Harrop]

On Wednesday 30 March 2005 09:39, Alex Baretta wrote:
> I have come to think that the difference in performance might be
> attributable to the garbage collector.

Try to objectively quantify the performance bottleneck using profiling, rather 
than speculating. Most of the time, most of the people speculate 
incorrectly. :-)

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...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

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

[Alex Baretta]

Jon Harrop wrote:
> On Wednesday 30 March 2005 09:39, Alex Baretta wrote:
> 
>>I have come to think that the difference in performance might be
>>attributable to the garbage collector.
> 
> 
> Try to objectively quantify the performance bottleneck using profiling, rather 
> than speculating. Most of the time, most of the people speculate 
> incorrectly. :-)

Might be. I'm just trying to analyze critically my own work.

> 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?

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/>

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

[Alexander S. Usov]

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,
  Alexander.

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

[Marcin 'Qrczak' Kowalczyk]

"Alexander S. Usov" <A.S.Usov@KVI.nl> writes:

>> 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.

No, OCaml's hash tables are resized automatically.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

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

[Alex Baretta]

Joh Harrop wrote:

>>> This is rather unlikely. The key to the hashtable is a unique integer...
> 
> So not a [0|1] list like the /. troll then?  ;-) 

No, definitely not. Actually, I am trying to use as much of the bonuses 
of functional programming to further speed up a fairly fast (but, alas, 
worst-case exponential) cutting stock algorithm. The present one works 
as a bytecode library to our AS/Xcaml application server, and provides 
performance comparable to that of the most widely available commercial 
implementations. Yet, it is necessary to do better to win the market 
over, and it it takes a little more effort than switching from ocamlc to 
ocamlopt ;)

>>> Rather, what happens, time-wise, if I create a hashtable with 4096 slots
>>> and end up filling it with several million key-value pairs?
> 
> 
> The hashtable will dynamically double its size each time it feels full. This 
> incurs an O(n) cost at exact solutions of n = 2^p - 1 for integer p>0, IIRC. 
> This will cause the program to stutter but should not adversely impact 
> overall performance. This would be a problem for real-time applications.

Marcin 'Qrczak' Kowalczyk wrote:
> "Alexander S. Usov" <A.S.Usov@KVI.nl> writes:
> 
> No, OCaml's hash tables are resized automatically.

Ok. So, just as I expected, I am guaranteed that I have no hash 
conflicts desperately degrading the performance of my algorithm. But 
what is the amortized complexity of an insertion into a resizable 
hashtable? Am I right in stating that it is O(log n)? Or is it maybe 
O(n) due to saturation of number of buckets available to the hashtable? 
Then, in this case, I would need to expand the number of buckets by 
allocating a super-hashtable implemented as a hashtable of hashtables 
(as someone already suggested) or an array of hashtables.

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?


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/>

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

[Jean-Christophe Filliatre]

Marcin 'Qrczak' Kowalczyk wrote:
> 
> No, OCaml's hash tables are resized automatically.

Alex Baretta writes:
> 
> Ok. So, just as I expected, I am guaranteed that I have no hash 
> conflicts desperately degrading the performance of my algorithm. 

Note that it is true only if your hash function is good enough.

I had once a code spending most of its time in the resizing of Ocaml's
hash tables because of a  bad hash function. This is particularly true
of the ocaml  default hash function on ``pure''  abstract syntax trees
(recursive data types with few  types such as int or strings). Writing
my own hash function immediately solved the performance issue.

(In your case, however, the problem seems to be elsewhere ince you are
using unique integers as keys).

As somebody already  said, a profiling is a simple way  to find out if
the hash tables resizing is the issue.

Best regards,
-- 
Jean-Christophe

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

[Damien Doligez]

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 
proportional
to the heap size.  Hence, under reasonable assumptions, average GC cost 
is
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

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

[Alex Baretta]

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/>

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

[Damien Doligez]

On Apr 11, 2005, at 17:48, Alex Baretta wrote:

> 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?

Assuming you are going to use hash tables:

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.

-- Damien

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

[Jan Kybic]

> 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