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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 94852BC57 for ; Thu, 18 Nov 2010 16:51:51 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnsDAKva5EzRVaC0k2dsb2JhbACGOY1ohikBhzZKCBUBAQIJCQoJEQMfRqN6iWKCGIUnLohZAQEDBYVGBIpa X-IronPort-AV: E=Sophos;i="4.59,217,1288566000"; d="scan'208";a="67193641" Received: from mail-gy0-f180.google.com ([209.85.160.180]) by mail3-smtp-sop.national.inria.fr with ESMTP; 18 Nov 2010 16:51:50 +0100 Received: by gyg8 with SMTP id 8so1934602gyg.39 for ; Thu, 18 Nov 2010 07:51:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:date:message-id :subject:from:to:content-type; bh=cRNke2fnPbSOpu8cqeBvG5i7I0BbMPZi9pO+rw4lSWU=; b=T3Pa0zKj6TZT89PK2yRO/dhhAphiqS6x2L7ImAnlH9Jei4nQw21CvpXu5u+vWe3rKE R+fyjGo7PLEjuMx64UhQhY+B1S3euJcVT6ZxnIsu4whtO8lvEZMg6J1aQrQQArYem/OE wG7y/HDDVwT5goeX7Ob1PTTqggLdUzFQ1P6Bw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type; b=YWCNaLO63NV7H1sPdx5YlLfBEM3QYCxn4JJAv+EPsBAWIsSV1BU+hnurXV+LCMJdZW ACgE8uMeWb4hFIojqKVx3+x0IveGnphWLKTOGVBMQX5Fsww/ici0iI5fKdEN4gjbNVVz uQJpHeaMCzhmaYn3xUjI3MBSMLeJQl3dEmijQ= MIME-Version: 1.0 Received: by 10.90.2.18 with SMTP id 18mr1246619agb.86.1290095507085; Thu, 18 Nov 2010 07:51:47 -0800 (PST) Received: by 10.91.154.3 with HTTP; Thu, 18 Nov 2010 07:51:46 -0800 (PST) Date: Thu, 18 Nov 2010 17:51:46 +0200 Message-ID: Subject: Optimizing garbage collection From: Eray Ozkural To: caml-list Content-Type: multipart/alternative; boundary=0016363102e96d1be2049555c424 X-Spam: no; 0.00; eray:01 ozkural:01 ocaml:01 granularity:01 byte:01 alloc:01 alloc:01 eray:01 ozkural:01 bilkent:01 ocaml:01 granularity:01 byte:01 bilkent:01 0.05:98 --0016363102e96d1be2049555c424 Content-Type: text/plain; charset=ISO-8859-1 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] ----------------------------------------------- [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 --0016363102e96d1be2049555c424 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
A program I wrote constructs a lot of small lists, and strings and dis= cards 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 outp= ut on linux:

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

index % time= =A0 =A0self =A0children =A0 =A0called =A0 =A0 name
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.00 =A0 =A01.31 =A0 =A03777/1340632= 3 =A0 =A0 caml_alloc [139]
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.00= =A0 =A02.45 =A0 =A07076/13406323 =A0 =A0 caml_alloc_small [94]
= =A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.00 =A0 =A06.42 =A0 18532/13406323 =A0 = =A0 caml_copy_double [119]
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.05 =A0405.30 1169992/13406323 =A0 = =A0 caml_alloc_string [16]
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.10= =A0721.02 2081381/13406323 =A0 =A0 caml_check_urgent_gc [27]
=A0= =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.48 3507.65 10125565/13406323 =A0 =A0 caml_= garbage_collection [3]
[1] =A0 =A0 53.5 =A0 =A00.63 4644.15 13406323 =A0 =A0 =A0 =A0 caml_min= or_collection [1]
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A02.13 2625.29 = 13406323/13406323 =A0 =A0 caml_major_collection_slice [5]
=A0=A0 = =A0 =A0 =A0 =A0 =A0 =A0 =A02.25 2014.36 26812646/26812646 =A0 =A0 caml_empt= y_minor_heap [6]
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.13 =A0 =A00.00 13406323/13406323 = =A0 =A0 caml_final_do_calls [308]
-------------------------------= ----------------
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 = =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 <spontaneous>
[2] =A0 =A0 40.4 =A0 =A00.66 3508.19 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 c= aml_call_gc [2]
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.03 3508.16 10= 125565/10125565 =A0 =A0 caml_garbage_collection [3]
-------------= ----------------------------------
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.03 3508.16 10125565/10125565 =A0 =A0 ca= ml_call_gc [2]
[3] =A0 =A0 40.4 =A0 =A00.03 3508.16 10125565 =A0 = =A0 =A0 =A0 caml_garbage_collection [3]
=A0=A0 =A0 =A0 =A0 =A0 = =A0 =A0 =A00.48 3507.65 10125565/13406323 =A0 =A0 caml_minor_collection [1]=
=A0=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00.03 =A0 =A00.00 10125565/10125627 = =A0 =A0 caml_process_pending_signals [429]
----------------------= -------------------------

--
Eray Ozkural, PhD candidate.=A0 C= omp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo= .com/group/ai-philosophy
h= ttp://myspace.com/arizanesil ht= tp://myspace.com/malfunct

--0016363102e96d1be2049555c424--