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 0F0B1BC37 for ; Fri, 13 Nov 2009 09:38:04 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlcDALap/EpQRFuwWWdsb2JhbACcDgEUFwS4Z4Q8BA X-IronPort-AV: E=Sophos;i="4.44,735,1249250400"; d="scan'208";a="40038990" Received: from furbychan.cocan.org ([80.68.91.176]) by mail1-smtp-roc.national.inria.fr with ESMTP; 13 Nov 2009 09:38:03 +0100 Received: from rich by furbychan.cocan.org with local (Exim 4.63) (envelope-from ) id 1N8rfO-0000ya-Hl; Fri, 13 Nov 2009 08:38:02 +0000 Date: Fri, 13 Nov 2009 08:38:02 +0000 To: Goswin von Brederlow Cc: caml-list@inria.fr Subject: Re: [Caml-list] How to write a GC for size > memory Message-ID: <20091113083802.GA3468@annexia.org> References: <87vdhfxb6c.fsf@frosties.localdomain> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <87vdhfxb6c.fsf@frosties.localdomain> User-Agent: Mutt/1.5.13 (2006-08-11) From: Richard Jones X-Spam: no; 0.00; 0100,:01 generational:01 mutables:01 node:01 nodes:01 nodes:01 generational:01 ocaml:01 ocaml:01 invariants:01 2009:98 freeing:98 wrote:01 heap:01 caml-list:01 On Fri, Nov 13, 2009 at 06:10:03AM +0100, Goswin von Brederlow wrote: > Normaly the GC would switch between defrag and freeing chunk > mode. Both would be concurrent to normal filesystem > operations. Possibly only run when the filesystem is idle. The > compation mode would only happen in situations where the FS would > otherwise have to return ENOSPC. > > To further improve this I would like to add a generational component > into the GC. I have no mutables (except the roots) so an old chunk (or > an old B-Tree node) can hold no references to a newer chunk. Also new > files are far more likely to be deleted again than old files and new > B-Tree nodes more likely to be modified again than old B-Tree > nodes. Seems to screem for a generational approach. A generational > approach should allow the GC to only scan a fraction of the B-Tree for > its sweep. But I'm not quite sure how to go about that. > > Comments, Ideas, Improvements, Urls welcome. As I said on IRC I still think ocaml-ancient is a good fit to this, unless you are planning to modify the OCaml GC itself. ocaml-ancient essentially converts parts of the heap to use manual memory allocation, on top of which you can write a more suitable GC in OCaml for your long-lived rarely-changing blocks (eg. one based on reference counting). The invariants you describe above are exactly the ones which ocaml-ancient needs. Rich. -- Richard Jones Red Hat