From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA18437; Fri, 13 Aug 2004 17:32:50 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA17039 for ; Fri, 13 Aug 2004 17:32:49 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7DFWmRM010119 for ; Fri, 13 Aug 2004 17:32:48 +0200 Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id i7DFWKJ12358; Fri, 13 Aug 2004 10:32:21 -0500 (CDT) Date: Fri, 13 Aug 2004 10:40:09 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Christophe Raffalli cc: Jacques Garrigue , , Subject: Re: AW: [Caml-list] The tag bit In-Reply-To: <411CBAF6.3010101@univ-savoie.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 411CDF20.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 raffalli:01 pointers:01 ocaml's:01 allocating:01 slower:01 allocating:01 christophe:01 tagged:01 ocaml:01 ocaml:01 garbage:01 garbage:01 int:01 int:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 13 Aug 2004, Christophe Raffalli wrote: > There is a less costly way to avoid the tag bit in integer: > "conservative GC": any int which happens to point in an alloccated block > (or only at the beginning if you do not consider C but ML) is considered > as a pointer. You will have very few wrong pointers (especially in the > second case). Moreover, array of int or float, or block of memory can be > tagged with a flag saying they do not old pointer. > > The Boehm GC for C and C++ is very succefull to do that and very often > allow you to share data-structure in C as you would in ML (not caring > about who will release first the data) and gain both speed and memory. This works well for languages like C/C++, where allocation is (compartively) rare. Ocaml programs allocate like crazy (most of the stuff they allocate becomes garbage almost immediately, which is why they don't take 300 terabytes of ram to run). Cost of allocation is a very important number to Ocaml's performance. The problem with Boehm-style conservative GC is that you can't do copying collection with it. You're not *sure* if that word is an integer or a pointer, so you can't change it to move the object it's pointing to- you might be changing an integer, with catastrophic consequences for the program. With copying garbage collection, allocation is very, very fast. Ocaml, on the x86, takes five simple instructions to allocate a block of memory (if you don't kick off a garbage collection). So a high allocation rate isn't a big problem. But this only works because Ocaml keeps the heap compact by moving objects around. So allocating on the heap is not much slower than allocating on the stack- you just bump a pointer. If you can't move objects around, the heap becomes fragmented- free and used blocks mixed together. And you end up searching the heap for a free space when you want to allocate. This isn't a problem if allocation is rare, but it's deadly for Ocaml. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners