Optimizing garbage collection

Optimizing garbage collection

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 2068 bytes --]

A program I wrote constructs a lot of small lists, and strings and discards
them. It's a search algorithm. I profiled this code and saw that garbage
collection takes significant time.

In C++, we can write custom allocators to optimize the data structures that
cause such slowdowns. Any recommended strategies in ocaml?

Best,

Call graph in gprof output on linux:

granularity: each sample hit covers 2 byte(s) for 0.00% of 8680.47 seconds

index % time    self  children    called     name
                0.00    1.31    3777/13406323     caml_alloc [139]
                0.00    2.45    7076/13406323     caml_alloc_small [94]
                0.00    6.42   18532/13406323     caml_copy_double [119]
                0.05  405.30 1169992/13406323     caml_alloc_string [16]
                0.10  721.02 2081381/13406323     caml_check_urgent_gc [27]
                0.48 3507.65 10125565/13406323     caml_garbage_collection
[3]
[1]     53.5    0.63 4644.15 13406323         caml_minor_collection [1]
                2.13 2625.29 13406323/13406323
caml_major_collection_slice [5]
                2.25 2014.36 26812646/26812646     caml_empty_minor_heap [6]
                0.13    0.00 13406323/13406323     caml_final_do_calls [308]
-----------------------------------------------
                                                 <spontaneous>
[2]     40.4    0.66 3508.19                 caml_call_gc [2]
                0.03 3508.16 10125565/10125565     caml_garbage_collection
[3]
-----------------------------------------------
                0.03 3508.16 10125565/10125565     caml_call_gc [2]
[3]     40.4    0.03 3508.16 10125565         caml_garbage_collection [3]
                0.48 3507.65 10125565/13406323     caml_minor_collection [1]
                0.03    0.00 10125565/10125627
caml_process_pending_signals [429]
-----------------------------------------------

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 2601 bytes --]

Re: [Caml-list] Optimizing garbage collection

[Michael Ekstrand]

On 11/18/2010 09:51 AM, Eray Ozkural wrote:
> A program I wrote constructs a lot of small lists, and strings and
> discards them. It's a search algorithm. I profiled this code and saw
> that garbage collection takes significant time.
> 
> In C++, we can write custom allocators to optimize the data structures
> that cause such slowdowns. Any recommended strategies in ocaml?

The OCaml garbage collector exposes a variety of tuning parameters
through the Gc module[1] and the OCAMLRUNPARAM environment variable[2].
 I would tweak those.  In particular, I would recommend increasing the
minor heap size so that more of your data can be quickly discarded.  You
can also increase the space overhead, thereby causing the GC to be less
aggressive at the expense of higher memory usage/more waste.  Lastly, I
often increase the heap increment to allow memory to allow the heap to
expand more quickly, but I do not know if that will help in your case or
not.  I have documented my practices more thoroughly at my blog[3].

As I see it, the biggest gains will be by tuning your code and your
minor heap size so that ephemeral structures never hit the major heap.
My rule of thumb is that one "work unit", if you have such a concept,
should fit in the minor heap.  Collecting dead structures from the minor
heap is fast; moving a structure to the major heap only to have it be
unreachable by the next GC cycle can cause substantial GC thrashing.

You're on to a good start, though, by measuring.  I use gprof heavily as
I tweak my code's performance.

- Michael

1. http://caml.inria.fr/pub/docs/manual-ocaml/libref/Gc.html
2. http://caml.inria.fr/pub/docs/manual-ocaml/manual024.html#toc96
3. http://elehack.net/michael/blog/2010/06/ocaml-memory-tuning

Re: [Caml-list] Optimizing garbage collection

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 249 bytes --]

Thanks a lot for the suggestions Michael. Much appreciated.

Best,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 457 bytes --]

Re: [Caml-list] Optimizing garbage collection

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 2846 bytes --]

The program I am testing it on is basically a DFS algorithm so it doesn't
use much heap memory really. Just a lot of transient objects.

Looking at the top the RSIZE looks to be not over 11M under OSX.

Yes, the default minor heap size was indeed too low, I've been trying to set
it to a higher value, now testing with the OCAMLRUNPARAM settings you
recommended. It did result in some speedup, but not an awful lot, it's
important to profile it as you say.

Best,

On Fri, Nov 19, 2010 at 4:54 PM, Michael Ekstrand <michael@elehack.net>wrote:

> On 11/18/2010 09:51 AM, Eray Ozkural wrote:
> > A program I wrote constructs a lot of small lists, and strings and
> > discards them. It's a search algorithm. I profiled this code and saw
> > that garbage collection takes significant time.
> >
> > In C++, we can write custom allocators to optimize the data structures
> > that cause such slowdowns. Any recommended strategies in ocaml?
>
> The OCaml garbage collector exposes a variety of tuning parameters
> through the Gc module[1] and the OCAMLRUNPARAM environment variable[2].
>  I would tweak those.  In particular, I would recommend increasing the
> minor heap size so that more of your data can be quickly discarded.  You
> can also increase the space overhead, thereby causing the GC to be less
> aggressive at the expense of higher memory usage/more waste.  Lastly, I
> often increase the heap increment to allow memory to allow the heap to
> expand more quickly, but I do not know if that will help in your case or
> not.  I have documented my practices more thoroughly at my blog[3].
>
> As I see it, the biggest gains will be by tuning your code and your
> minor heap size so that ephemeral structures never hit the major heap.
> My rule of thumb is that one "work unit", if you have such a concept,
> should fit in the minor heap.  Collecting dead structures from the minor
> heap is fast; moving a structure to the major heap only to have it be
> unreachable by the next GC cycle can cause substantial GC thrashing.
>
> You're on to a good start, though, by measuring.  I use gprof heavily as
> I tweak my code's performance.
>
> - Michael
>
> 1. http://caml.inria.fr/pub/docs/manual-ocaml/libref/Gc.html
> 2. http://caml.inria.fr/pub/docs/manual-ocaml/manual024.html#toc96
> 3. http://elehack.net/michael/blog/2010/06/ocaml-memory-tuning
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>



-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 4108 bytes --]

Re: [Caml-list] Optimizing garbage collection

[Alexandre Pilkiewicz]

Hi

2010/11/20 Eray Ozkural <examachine@gmail.com>:
> Yes, the default minor heap size was indeed too low, I've been trying to set
> it to a higher value, now testing with the OCAMLRUNPARAM settings you
> recommended. It did result in some speedup, but not an awful lot, it's
> important to profile it as you say.

Can you tell us how high you set it? I would recommend at least
524288, and even something like 3000000 if you really need to (I'm
talking in words here).

Cheers

Alexandre

Re: [Caml-list] Optimizing garbage collection

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 1398 bytes --]

Hello there Alexandre,

On Sun, Nov 21, 2010 at 8:13 PM, Alexandre Pilkiewicz <
alexandre.pilkiewicz@polytechnique.org> wrote:

> Hi
>
> 2010/11/20 Eray Ozkural <examachine@gmail.com>:
> > Yes, the default minor heap size was indeed too low, I've been trying to
> set
> > it to a higher value, now testing with the OCAMLRUNPARAM settings you
> > recommended. It did result in some speedup, but not an awful lot, it's
> > important to profile it as you say.
>
> Can you tell us how high you set it? I would recommend at least
> 524288, and even something like 3000000 if you really need to (I'm
> talking in words here)
>

I've set it to 4M and I think it's worked wonders, the collection time is no
more so significant in gprof output (surprisingly) at least now I can
identify the real bottlenecks! Indeed the 5-instr long fast path is quite
fast. Due to the peculiarities of my code, it didn't result in much speedup
but I've solved this problem, I can't believe I've overlooked the Gc
parameters, I should probably be setting them from within the code. A bit
embarrassed about it actually :)

I've been thinking whether some kind of doubling strategy would work for the
minor heap size. What do you think?

Best,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 2052 bytes --]

Re: [Caml-list] Optimizing garbage collection

[Damien Doligez]

On 2010-11-21, at 20:26, Eray Ozkural wrote:

> I've been thinking whether some kind of doubling strategy would work for the minor heap size. What do you think?

Sounds like an interesting idea, but what heuristic would you use?
When everything is smooth, the running time decreases something like
exponentially with the minor heap size, so you'd always want to
increase the size.  How do you tell when to stop?  And then, if the
program is not behaving uniformly, when do you decide to reduce
the size?

-- Damien

Re: [Caml-list] Optimizing garbage collection

[Mauricio Fernandez]

On Mon, Nov 22, 2010 at 04:10:49PM +0100, Damien Doligez wrote:
> On 2010-11-21, at 20:26, Eray Ozkural wrote:
> 
> > I've been thinking whether some kind of doubling strategy would work for the minor heap size. What do you think?
> 
> Sounds like an interesting idea, but what heuristic would you use?
> When everything is smooth, the running time decreases something like
> exponentially with the minor heap size, so you'd always want to
> increase the size.  How do you tell when to stop?  And then, if the
> program is not behaving uniformly, when do you decide to reduce
> the size?

Just dropping an idea, not sure it's worth a dime...
How about an exponential growth scheme with hysteresis?
On each minor collection, multiply the size by a if the rate of promoted words
exceeds r1, divide by b if the rate is below r2 (r1 > r2); otherwise remain
stable.

In order to account for the effect of the cache hierarchy, r1 and r2 could
also be a function of the current heap size (e.g., with r1 and r2 being higher
when approaching "magic" numbers such as the size of the L2 cache on the left
and right side respectively).

It'd also be very nice to be able to estimate the amount of time spent on
minor + major GC collection vs. the mutator.

-- 
Mauricio Fernandez  -   http://eigenclass.org

Re: Optimizing garbage collection

[Sylvain Le Gall]

On 22-11-2010, Damien Doligez <damien.doligez@inria.fr> wrote:
>
> On 2010-11-21, at 20:26, Eray Ozkural wrote:
>
>> I've been thinking whether some kind of doubling strategy would work for the minor heap size. What do you think?
>
> Sounds like an interesting idea, but what heuristic would you use?
> When everything is smooth, the running time decreases something like
> exponentially with the minor heap size, so you'd always want to
> increase the size.  How do you tell when to stop?  And then, if the
> program is not behaving uniformly, when do you decide to reduce
> the size?
>

How do you tell when to stop? 
->

Maybe you can stop when you reach (the size of the L2/L3 cache of the
processor) / number of core.

Both information are quite straight to read from /proc/cpuinfo. 

Regards,
Sylvain Le Gall

Re: [Caml-list] Re: Optimizing garbage collection

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 1655 bytes --]

On Mon, Nov 22, 2010 at 6:42 PM, Sylvain Le Gall <sylvain@le-gall.net>wrote:

> On 22-11-2010, Damien Doligez <damien.doligez@inria.fr> wrote:
> >
> > On 2010-11-21, at 20:26, Eray Ozkural wrote:
> >
> >> I've been thinking whether some kind of doubling strategy would work for
> the minor heap size. What do you think?
> >
> > Sounds like an interesting idea, but what heuristic would you use?
> > When everything is smooth, the running time decreases something like
> > exponentially with the minor heap size, so you'd always want to
> > increase the size.  How do you tell when to stop?  And then, if the
> > program is not behaving uniformly, when do you decide to reduce
> > the size?
> >
>
> How do you tell when to stop?
> ->
>
> Maybe you can stop when you reach (the size of the L2/L3 cache of the
> processor) / number of core.
>
> Both information are quite straight to read from /proc/cpuinfo.
>


Yeah that's what I had in mind, determine a kind of sensible upper bound to
grow to. Cache size makes some sense, though I think as recently mentioned
"working set size" is relevant. If the garbage collector could deduce that
it could be used, the other suggestion is also sensible. You could also set
it to something like 1/4 of physical RAM. That kind of logic is used in some
out-of-core data mining algorithms.

The objective here is to amortize the cost of copying until the working set
size is reached, otherwise there will be disk thrashing anyway!

Best,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 2326 bytes --]

RE: [Caml-list] Re: Optimizing garbage collection

[Jon Harrop]

What happens if you just increase the default size?

Re: [Caml-list] Re: Optimizing garbage collection

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 469 bytes --]

On Mon, Nov 22, 2010 at 11:14 PM, Jon Harrop <
jonathandeanharrop@googlemail.com> wrote:

> What happens if you just increase the default size?
>
>

Well we don't want to be a memory hog like Java do we? It's something that
kind of depends on the app, what would you set it to?

Cheers,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 983 bytes --]

RE: [Caml-list] Re: Optimizing garbage collection

[Jon Harrop]

[-- Attachment #1: Type: text/plain, Size: 1057 bytes --]

I would increase the default minor heap size to something closer to today's
common L2 cache sizes. But I see that Damien already did this for us:

 

http://caml.inria.fr/cgi-bin/viewcvs.cgi/ocaml/version/3.12/byterun/config.h
?rev=10787
<http://caml.inria.fr/cgi-bin/viewcvs.cgi/ocaml/version/3.12/byterun/config.
h?rev=10787&r1=10496&r2=10787> &r1=10496&r2=10787

 

Cheers,

Jon.

 

From: Eray Ozkural [mailto:examachine@gmail.com] 
Sent: 22 November 2010 23:14
To: Jon Harrop
Cc: Sylvain Le Gall; caml-list@inria.fr
Subject: Re: [Caml-list] Re: Optimizing garbage collection

 

On Mon, Nov 22, 2010 at 11:14 PM, Jon Harrop
<jonathandeanharrop@googlemail.com> wrote:

What happens if you just increase the default size?

  

 

Well we don't want to be a memory hog like Java do we? It's something that
kind of depends on the app, what would you set it to?

Cheers,

 

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct


[-- Attachment #2: Type: text/html, Size: 4647 bytes --]

Re: [Caml-list] Re: Optimizing garbage collection

[Goswin von Brederlow]

Eray Ozkural <examachine@gmail.com> writes:

> On Mon, Nov 22, 2010 at 11:14 PM, Jon Harrop <jonathandeanharrop@googlemail.com
>> wrote:
>
>     What happens if you just increase the default size?
>       
>
>
> Well we don't want to be a memory hog like Java do we? It's something that kind
> of depends on the app, what would you set it to?
>
> Cheers,

I would start below the cache size. If that works that is really great.

Limit it by the size of the major heap (at most 10% of the major heap
size?). And grow/shrink it by amount of copying to the major heap that
is required. If less than 10% of the minor heap are still alive on a
sweep then shrink it, if more than 50% are alive then grow it or
something.

Do a lot of tests to find good values for those percentages.

MfG
        Goswin

Re: [Caml-list] Optimizing garbage collection

[John Carr]

> When everything is smooth, the running time decreases something like
> exponentially with the minor heap size, so you'd always want to
> increase the size.  How do you tell when to stop?  And then, if the
> program is not behaving uniformly, when do you decide to reduce
> the size?

I don't understand "smooth".  Minor heap size should be based on the
rate of garbage generation relative to allocation to balance cache
misses with GC cost.  The ratio may be small or large independent of
whether it varies during the program.

The default minor heap size is well tuned for traditional functional
programming behavior: high rate of allocation, short lifetime.

When memory access is smaller than a cache line the cache does not
reward data reuse so much as address reuse.  Collecting a small minor
heap that is mostly garbage allows the allocator to start over at
an address that is already in cache.  Continuing to allocate instead
of collecting leads to write-allocate misses.

Re: [Caml-list] Optimizing garbage collection

[Damien Doligez]

On 2010-11-22, at 19:38, John Carr wrote:

> I don't understand "smooth".  Minor heap size should be based on the
> rate of garbage generation relative to allocation to balance cache
> misses with GC cost.  The ratio may be small or large independent of
> whether it varies during the program.


What I meant is that, if the allocation rate of the program is infinitely
regular and you don't get any threshold effects, the running time decreases
as the minor heap size increases, and it's hard to tell when you should
stop increasing it.

For benchmarks the best choice is probably the physical memory size, but
you certainly don't want your real programs to do that.

-- Damien

Re: [Caml-list] Optimizing garbage collection

[Christophe Raffalli]

[-- Attachment #1.1: Type: text/plain, Size: 1092 bytes --]


Hello,

May be running a minimisation algorithm to minimize (promoted_words per
minor collection / minor_heap_size)  Could be good ?

If we retain the value of this ration for the last N minor_collection,
we can surely guess
a good value for the next cycle (using trichomomy for instance) ...

I will have a look if nobody elso does before me.

Unfortunately to write this in OCaml itself is not so easy: there are no
alarm for minor collection cycle, so will only get values for major
cycle or via a timer with fixed intervals ...

Cheers,
Christophe


-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution 
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #1.2: Christophe_Raffalli.vcf --]
[-- Type: text/x-vcard, Size: 310 bytes --]

begin:vcard
fn:Christophe Raffalli
n:Raffalli;Christophe
org:LAMA (UMR 5127)
email;internet:christophe.raffalli@univ-savoie.fr
title;quoted-printable:Ma=C3=AEtre de conf=C3=A9rences
tel;work:+33 4 79 75 81 03
note:http://www.lama.univ-savoie.fr/~raffalli
x-mozilla-html:TRUE
version:2.1
end:vcard


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Caml-list] Optimizing garbage collection

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 2374 bytes --]

Le 23/11/2010 14:40, Christophe Raffalli a écrit :
> 
> Hello,
> 
> May be running a minimisation algorithm to minimize (promoted_words per
> minor collection / minor_heap_size)  Could be good ?
> 

This was stupid has it converges toward zero when we increase minor_heap_size.

However, the following piece of code worked well for PML benchmark (4'30" became 3'02") :
(remark that HALVING the minor_heap_size does occur too)

I really do not know if such strategy is reasonnable as a default ?
If the 0.10 and 0.005 in the code are any reasonnable ?

-------------------8<---------------------
open Gc

let param = get ()

let old_promoted_words = ref 0.0
let old_minor_collections = ref 0
let minor_heap_size = ref param.minor_heap_size

let _ = create_alarm (fun () ->
  let s = quick_stat () in
  let promoted_words = s.promoted_words in
  let minor_collections = s.minor_collections in
  let delta_promoted_words = promoted_words -. !old_promoted_words in
  let delta_minor_collections = minor_collections - !old_minor_collections in
  old_promoted_words := promoted_words;
  old_minor_collections := minor_collections;
  let ratio = delta_promoted_words /. (float) delta_minor_collections
                                   /. (float) !minor_heap_size
  in
  if ratio > 0.10 then begin
    minor_heap_size := !minor_heap_size * 2;
(*  Printf.fprintf stderr "MHS DOUBLED <- %d (ratio %f)\n" !minor_heap_size ratio;
    flush stderr; *)
    set { get () with minor_heap_size = !minor_heap_size }
  end else if ratio < 0.005 then begin
    minor_heap_size := max 32768 (!minor_heap_size / 2);
(*  Printf.fprintf stderr "MHS HALFED <- %d (ratio %f)\n" !minor_heap_size ratio;
    flush stderr; *)
    set { get () with minor_heap_size = !minor_heap_size }
  end)
-------------------8<---------------------

-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]