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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 585C8BBAF for ; Sat, 30 Oct 2010 22:40:43 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqIAALofzExKfVK0k2dsb2JhbACTHYFTjFIIFQEBAQEJCQoJEQMfojaLcQEFjkoBBIMDCII5 X-IronPort-AV: E=Sophos;i="4.58,265,1286143200"; d="scan'208";a="77435460" Received: from mail-wy0-f180.google.com ([74.125.82.180]) by mail2-smtp-roc.national.inria.fr with ESMTP; 30 Oct 2010 22:40:42 +0200 Received: by wyb32 with SMTP id 32so4152743wyb.39 for ; Sat, 30 Oct 2010 13:40:43 -0700 (PDT) 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:content-transfer-encoding:x-mailer:thread-index :content-language; bh=QHJPm09ECJR/5RrsobclbHzMJSZt58wYEPHs8npTWU4=; b=hYr4CHviUM1s7QG1n/yUKCZ+RJcYchwD1Xk983DO5IAZdiDnxxWzVn96BZqxCbI5Do l789nj5khDGqltKBRMcy4y5gyFumqnjHpajfYwn6hejR83trQ4rsCbJpzilhia/VsiWS welXCkuqe9Onad03OURMA1uK3qczcsAmd7jk4= 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:content-transfer-encoding:x-mailer :thread-index:content-language; b=YYtMSU4Bb4X7+ravyMl1Z5nPo7AZGU3vvsX1vBDYJbGx6GpwCWDpdBWXbMxx7iqmci t9n2qlv8iRtgRCvF7pxm5wCpojtJBj1J9Efw25y5kDjSVQTz5EfX5FlCNuAkXegAcBH0 y2ch1FVigffxj0dfwkyuTKnPrpffTNYYS7DsM= Received: by 10.216.26.194 with SMTP id c44mr13486215wea.104.1288471242858; Sat, 30 Oct 2010 13:40:42 -0700 (PDT) Received: from WinEight ([87.112.186.137]) by mx.google.com with ESMTPS id l14sm2634845weq.11.2010.10.30.13.40.40 (version=SSLv3 cipher=RC4-MD5); Sat, 30 Oct 2010 13:40:41 -0700 (PDT) From: Jon Harrop To: "'Michael Ekstrand'" , References: <418632253.26199.1288302511712.JavaMail.root@zmbs1.inria.fr> <8277D889-83E2-4037-91B3-3EB5E9EB2EA9@inria.fr> <018c01cb7856$1e228350$5a6789f0$@com> <4CCC5802.4080909@elehack.net> In-Reply-To: <4CCC5802.4080909@elehack.net> Subject: RE: [Caml-list] How does OCaml update references when values are moved by the GC? Date: Sat, 30 Oct 2010 21:40:32 +0100 Organization: Flying Frog Consultancy Message-ID: <019501cb7872$b56856b0$20390410$@com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook 12.0 Thread-Index: Act4WVmMvaKJp1qdTri1JQPXL0MPXwAELwaQ Content-Language: en-gb X-Spam: no; 0.00; ocaml:01 ocaml:01 pointers:01 cheers:01 pointers:01 compaction:01 runtime:01 mutable:01 pointer:01 mutable:01 runtime:01 run-time:01 traversing:01 unboxed:01 arrays:01 Hi Michael, Thanks for the info. I stumbled upon Richard's excellent web page describing the internals of OCaml and the write barrier but it does not describe how the pointers actually get rewritten. Cheers, Jon. > -----Original Message----- > From: caml-list-bounces@yquem.inria.fr [mailto:caml-list- > bounces@yquem.inria.fr] On Behalf Of Michael Ekstrand > Sent: 30 October 2010 18:38 > To: caml-list@yquem.inria.fr > Subject: Re: [Caml-list] How does OCaml update references when values > are moved by the GC? > > On 10/30/2010 12:15 PM, Jon Harrop wrote: > > I was hoping for a little more detail, of course. :-) > > > > How is the mapping from old to new pointers stored? Does the GC > rewrite all > > of the thread-local stacks in series before allowing any of them to > > continue? > > I imagine so. > > > Does the write barrier record pointers written into the major heap > > so only those specific locations are rewritten at minor heap > collections but > > the entire major heap is rewritten upon compaction? > > Yes. The runtime maintains a 'remembered set', a list of pointers from > the major heap back to the minor heap. Maintaining this set is why > mutable data can be expensive in OCaml - any time you store a pointer > into a mutable field, the runtime must check whether the new link is > from the major to the minor heap and update the refs list accordingly. > Richard WM Jones has details here: > > http://rwmj.wordpress.com/2009/08/08/ocaml-internals-part-5-garbage- > collection/ > > > Can the GC distinguish > > between an array of ints and an array of pointers at run-time in > order to > > avoid traversing all of the ints when trying to rewrite pointers? > > Not that I know of. The tag block does not have a documented reserved > value to indicate that - there are values to indicate an unboxed float > array, a string, and an array of opaque values, but not an integer > array > (unless the opaque value flag is set for integer arrays). > > > Also, any idea what the maximum proportion of the running time of a > program > > is spent doing this rewriting? For example, if you fill a float- > >float hash > > table with values does updating the pointers in the major heap > account for a > > significant proportion of the total running time of the program? > > In my data analysis jobs (which wind up allocating quite large heaps), > the compactor almost never (detectably) runs. Minor cycles and major > slices are a much larger concern in my experience. I work around that > by increasing the minor heap size to decrease minor heap thrashing (my > general rule of thumb is that I want each "work unit", whatever that > may > be, to fit in the minor heap). > > It could well be that other applications will have different > characteristics that trigger more compactions. I cannot speak for > those > applications. Further, when I have huge floating-point data > structures, > I'm usually using bigarrays (not because I choose them over arrays, > typically, but because such code in my work frequently has to interact > with BLAS or SPARSKIT at some point). > > - Michael > > _______________________________________________ > 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