From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id DDC10BC57 for ; Sat, 20 Nov 2010 03:20:49 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ao8CAB+/5kzRVaG0k2dsb2JhbACUL4YpAYgCCBUBAQEBCQkKCREDH6JAiWKCGIUTLohZAQEDBYVGBIFciH8 X-IronPort-AV: E=Sophos;i="4.59,226,1288566000"; d="scan'208";a="88778931" Received: from mail-gx0-f180.google.com ([209.85.161.180]) by mail1-smtp-roc.national.inria.fr with ESMTP; 20 Nov 2010 03:20:49 +0100 Received: by gxk8 with SMTP id 8so3222848gxk.39 for ; Fri, 19 Nov 2010 18:20:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:cc:content-type; bh=W7c9ol4+FztyusON8WUAsjo0RDpzeYZePjF411B32ws=; b=PQCOSFCd+jzc4jbJn0WV6UCXZJYIh9/FNsvODaFpScRu3eBMReQ8gC7M62sq26jhnN FYlY58d9mCH855/oiD0GkVLnFhh5/Nr3786lCs59fBKRTrVxmn8k55bxryinFtuuDXNm DDSQPCCH2O7WQWnfEQi0MggW5LzvojbGL/Nb0= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=iZ6cgYTJDdO6qTgIHFPEJ2y6CuXXwDGs6/P1ujZ+A+PXtgPGMKKz3e/af6ZJVx5nTn TVi6FWEL2WjD4TesVdSucqs0fEnCK249aTeGDI7eJocgSVLv6X9M2birz+7iclnauH0O MzQeqqRYDpYSK+C2sat7LYrlXojcU89SGKb4M= MIME-Version: 1.0 Received: by 10.90.27.14 with SMTP id a14mr2114692aga.113.1290219647815; Fri, 19 Nov 2010 18:20:47 -0800 (PST) Received: by 10.91.154.3 with HTTP; Fri, 19 Nov 2010 18:20:47 -0800 (PST) In-Reply-To: <4CE68FAB.6020102@elehack.net> References: <4CE68FAB.6020102@elehack.net> Date: Sat, 20 Nov 2010 04:20:47 +0200 Message-ID: Subject: Re: [Caml-list] Optimizing garbage collection From: Eray Ozkural To: Michael Ekstrand Cc: caml-list@yquem.inria.fr Content-Type: multipart/alternative; boundary=001636163d99ca4f20049572abff X-Spam: no; 0.00; eray:01 ozkural:01 dfs:01 rsize:01 speedup:01 eray:01 ozkural:01 ocaml:01 ocaml:01 libref:01 beginner's:01 bug:01 bilkent:01 dfs:01 rsize:01 --001636163d99ca4f20049572abff Content-Type: text/plain; charset=ISO-8859-1 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 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 --001636163d99ca4f20049572abff Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable 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&= #39;ve been trying to set it to a higher value, now testing with the OCAMLR= UNPARAM 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:<= br>
On 11/18/2010 09:51 AM, E= ray 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 s= aw
> 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].
=A0I would tweak those. =A0In particular, I would recommend increasing the<= br> minor heap size so that more of your data can be quickly discarded. =A0You<= br> can also increase the space overhead, thereby causing the GC to be less
aggressive at the expense of higher memory usage/more waste. =A0Lastly, 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. =A0I 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 conc= ept,
should fit in the minor heap. =A0Collecting dead structures from the minor<= br> 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. =A0I 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-tuni= ng

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.in= ria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs



--
Eray Ozkural, PhD candi= date.=A0 Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-phil= osophy
http://myspace.com/arizanesil= http://myspace.com/malfunct
--001636163d99ca4f20049572abff--