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 mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 7958DBC57 for ; Sun, 28 Nov 2010 20:41:20 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArEEAJQ/8kxKfVIukGdsb2JhbACCA5JTMoEjg191AYgACBUBAQEBCQkMBxEDH6cti3wBBY0GAQSFRw X-IronPort-AV: E=Sophos;i="4.59,272,1288566000"; d="scan'208,217";a="80349507" Received: from mail-ww0-f46.google.com ([74.125.82.46]) by mail4-smtp-sop.national.inria.fr with ESMTP; 28 Nov 2010 20:41:03 +0100 Received: by wwb28 with SMTP id 28so3084102wwb.3 for ; Sun, 28 Nov 2010 11:41:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=domainkey-signature:received:received:from:to:references :in-reply-to:subject:date:organization:message-id:mime-version :content-type:x-mailer:thread-index:content-language; bh=ffUZSbNtbRARGd40rZqPZSstXJ3xR17dLUm0v07B7g4=; b=nTbbNEC8ihU68yqB9hblp1NvKVdybXRJmCLGcL1fx+zYzPb71/+ZvxWhmiOohQQl4m 3VU+a0kjEOLh+m4du3Wpgr7NkY8ksf/m3RI2HlqT2oBmHOod4SWUm3V2T3/FA58D2qzI GGRp6tPIUvB/t3Ry0VQRkSIYAfVO9P7rLxhzo= DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma; h=from:to:references:in-reply-to:subject:date:organization:message-id :mime-version:content-type:x-mailer:thread-index:content-language; b=FLK5Dpi1uh2MO74MlKzYtA2+YrkQXlH/EIcAbMlV7Ed5iS4yqMae5b2x9vbDOgPiid GTuWvLmxuiKbWxeEKagtUg4VZunv+r5mnvkvPXu2n0x5p1rlgxjf5OwnYO8uesHWpUkJ 8wiScOtE84EJZPDv8iNtoddoR4YpdPpqN9ays= Received: by 10.216.180.133 with SMTP id j5mr3960137wem.79.1290973262610; Sun, 28 Nov 2010 11:41:02 -0800 (PST) Received: from WinEight ([87.113.160.118]) by mx.google.com with ESMTPS id e12sm2017648wer.12.2010.11.28.11.40.56 (version=SSLv3 cipher=RC4-MD5); Sun, 28 Nov 2010 11:41:01 -0800 (PST) From: Jon Harrop To: References: <1290434674.16005.354.camel@thinkpad> <582306206.731582.1290438133628.JavaMail.root@zmbs4.inria.fr> <20101122203334.7adc5ee6@deb0> <20101127221121.0920db65@ordinaves.concept-micro.com> <4CF25878.4060202@univ-savoie.fr> In-Reply-To: Subject: RE: [Caml-list] OCaml GC [was Is OCaml fast?] Date: Sun, 28 Nov 2010 19:40:43 -0000 Organization: Flying Frog Consultancy Message-ID: <08df01cb8f34$299d5800$7cd80800$@com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_08E0_01CB8F34.299D5800" X-Mailer: Microsoft Office Outlook 12.0 Thread-Index: AcuPLkUNVtuako+dQB+q5vuB09W3KQABH33A Content-Language: en-gb X-Spam: no; 0.00; ocaml:01 ocaml:01 iirc:01 allocating:01 cheers:01 eray:01 ozkural:01 generational:01 generations:01 locality:01 doable:01 vars:01 eray:01 ozkural:01 bilkent:01 This is a multi-part message in MIME format. ------=_NextPart_000_08E0_01CB8F34.299D5800 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I don't understand why this would help here though. Wouldn't that help when a long-lived structure was single large block but, in this case, the long-lived structure is a tree composed of many small heap-allocated blocks and, therefore, they would undergo the same wasteful "allocate in young only to be copied to old" pathological behaviour? Surely what you really want the ability to spot when a full minor heap contains mostly live objects and, therefore, make the whole minor heap part of the major heap, allocate yourself a new minor heap and clear the remembered sets. IIRC, G1 does something like this. On a related note, When designing HLVM I thought that a mallocs function that allocated many small blocks of the same size such that they could be freed individually would be helpful. Another option might be to preallocate larger numbers of blocks at the same time under the assumption that a thread allocating many small surviving blocks would continue to do so, as a kind of pool hybrid. Cheers, Jon. From: caml-list-bounces@yquem.inria.fr [mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of Eray Ozkural Sent: 28 November 2010 18:57 To: Benedikt Meurer Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] OCaml GC [was Is OCaml fast?] On Sun, Nov 28, 2010 at 4:29 PM, Benedikt Meurer wrote: Speaking of the OCaml GC in general, wouldn't it make sense to replace the current generational collector with a collector framework that requires less copying in the common case. For example, dividing the heap into two parts, "large object space" and "small object space", where LOS is managed by mark-sweep/mark-compact (could use the current major heap) and SOS is managed by a recent mark-copy/mark-region collector (Immix [1] comes to mind here). That way objects would no longer need to be copied between generations, and using Immix may also reduce cache misses and improve locality of small/medium sized objects (with proper evacuation heuristics). This should be doable with a moderate amount of work, and should require no incompatible changes, while opening the door for concurrent/parallel garbage collection (this would require incompatible changes then, replacing caml_young_ptr/caml_young_limit with TLS vars, etc.). Benedikt [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.3640 I was suggesting dealing with small fixed-size objects differently in another post. This doesn't sound like a bad combination, nice idea :) 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 ------=_NextPart_000_08E0_01CB8F34.299D5800 Content-Type: text/html; charset="US-ASCII" Content-Transfer-Encoding: quoted-printable

I don’t understand why this would help here though. = Wouldn’t that help when a long-lived structure was single large = block but, in this case, the long-lived structure is a tree composed of = many small heap-allocated blocks and, therefore, they would undergo the = same wasteful “allocate in young only to be copied to old” = pathological behaviour?

 

Surely what you really want the ability to spot when a full minor = heap contains mostly live objects and, therefore, make the whole minor = heap part of the major heap, allocate yourself a new minor heap and = clear the remembered sets. IIRC, G1 does something like = this.

 

On a related note, When designing HLVM I thought that a mallocs = function that allocated many small blocks of the same size such that = they could be freed individually would be helpful. Another option might = be to preallocate larger numbers of blocks at the same time under the = assumption that a thread allocating many small surviving blocks would = continue to do so, as a kind of pool hybrid.

 

Cheers,

Jon.

 

From:= = caml-list-bounces@yquem.inria.fr = [mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of Eray = Ozkural
Sent: 28 November 2010 18:57
To: Benedikt = Meurer
Cc: caml-list@yquem.inria.fr
Subject: Re: = [Caml-list] OCaml GC [was Is OCaml = fast?]

 

On Sun, = Nov 28, 2010 at 4:29 PM, Benedikt Meurer <benedikt.meurer@googlemail= .com> wrote:

Speaking of the = OCaml GC in general, wouldn't it make sense to replace the current = generational collector with a collector framework that requires less = copying in the common case. For example, dividing the heap into two = parts, "large object space" and "small object = space", where LOS is managed by mark-sweep/mark-compact (could use = the current major heap) and SOS is managed by a recent = mark-copy/mark-region collector (Immix [1] comes to mind here). That way = objects would no longer need to be copied between generations, and using = Immix may also reduce cache misses and improve locality of small/medium = sized objects (with proper evacuation heuristics). This should be doable = with a moderate amount of work, and should require no incompatible = changes, while opening the door for concurrent/parallel garbage = collection (this would require incompatible changes then, replacing = caml_young_ptr/caml_young_limit with TLS vars, = etc.).

Benedikt

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=3D10.1= .1.144.3640


I was = suggesting dealing with small fixed-size objects differently in another = post. This doesn't sound like a bad combination, nice idea = :)
 
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=

------=_NextPart_000_08E0_01CB8F34.299D5800--