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 PAA03383; Wed, 7 Jul 2004 15:00:48 +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 PAA03178 for ; Wed, 7 Jul 2004 15:00:47 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i67D0kSH012449 for ; Wed, 7 Jul 2004 15:00:47 +0200 Received: from bourg.inria.fr (bourg.inria.fr [128.93.11.100]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA03473 for ; Wed, 7 Jul 2004 15:00:46 +0200 (MET DST) Received: from basile by bourg.inria.fr with local (Exim 4.34) id 1BiC24-0007C5-IH for caml-list@inria.fr; Wed, 07 Jul 2004 15:00:16 +0200 Date: Wed, 7 Jul 2004 15:00:16 +0200 To: caml-list@inria.fr Subject: Re: [Caml-list] Does Caml have slow arithmetics ? Message-ID: <20040707130016.GA27591@bourg.inria.fr> References: <20040707091308.GA26172@bourg.inria.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.6+20040523i From: "Basile Starynkevitch [local]" X-Miltered: at concorde with ID 40EBF3FE.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 arithmetics:01 basile:01 basile:01 2004:99 pons:01 subsidiary:99 silently:01 pointers:01 doable:01 hacks:01 ocaml's:01 allocates:01 chunks:01 malloc:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wed, Jul 07, 2004 at 02:32:56PM +0200, Diego Olivier Fernandez Pons wrote: (I, Basile Starynkevitch, replied:) > > In principle yes, because int values are represented as tagged > > (31bits) ints (with the LSB set to 1). So conversion is a shift > > followed by an addition (or viceversa). > > Subsidiary question : why LSB instead of MSB ? I thought it would be > simpler to let the computations silently overflow and correct when > necessary the tag bit. I cannot answer for sure, since I did not made the choice, but I see some reasons for it. values which are nontagged integers are pointers to blocks. For obvious reasons, you want to access the block's field as quickly as possible, so the pointer is in fact a machine pointer to the block (with perhaps a constant offset). using the MSB as a tag bit would require that every Ocaml value is in some restricted address range (like e g [0 ... 2^30] on 32 bits machine). And having the heap always inside this range is not doable without tricky system hacks (on Linux, mmap MAP_NORESERVE very early in the Ocaml startup) More simply, Ocaml's GC (IIRC) allocates memory (in big chunks) with malloc, not mmap. Hence, it has no idea of what the memory address is, and what is its MSB. All above is an educated guess (from reading the code and some discussions with Xavier L. & Damien D.) - I may be grossly wrong. I did read many GC related papers, and all the tagging schemes I remember having read about (for some suitably short integers) uses the LSB, not the MSB. So, it is probably a well established habit. If you want to start a functional language implementation from scratch, you might (as Xavier Leroy told me) consider tagging integers with a 0 LSB, and having GC-ed pointers with a 1 LSB. Hence, ordinary C pointers (outside your heap) are handled as integers and remain untouched by the GC. This insight is Xavier's, not mine! (Old dinosaurs like me also remember the tagged-add machine instruction on the Sparc, which had the tags of int in the two lowest bits of the word). This is the first time I'm hearing about tagging integer in the MSB, and I have no more convincing arguments - maybe it is just a habit (and maybe 64 bits processors might change it - since they won't fill their address space for a long time). -- Basile STARYNKEVITCH -- basile dot starynkevitch at inria dot fr Project cristal.inria.fr - phone +33 1 3963 5197 - mobile 6 8501 2359 http://cristal.inria.fr/~starynke --- all opinions are only mine ------------------- 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