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 QAA31673; Thu, 12 Aug 2004 16:31:24 +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 QAA30796 for ; Thu, 12 Aug 2004 16:31:23 +0200 (MET DST) Received: from kaiserslautern1.lms-gmbh.de (kaiserslautern1.lms-gmbh.de [212.43.68.201]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7CEVMRM005455 for ; Thu, 12 Aug 2004 16:31:22 +0200 Received: by mail.lms-gmbh.de with Internet Mail Service (5.5.2653.19) id ; Thu, 12 Aug 2004 16:31:17 +0200 Message-ID: From: "Bauer, Christoph" To: caml-list@inria.fr Subject: [Caml-list] The tag bit Date: Thu, 12 Aug 2004 16:31:14 +0200 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C48079.057924C0" X-Miltered: at concorde with ID 411B7F3A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; bauer:01 bauer:01 caml-list:01 floats:01 unboxed:01 caml-list:01 floats:01 unboxed:01 int:01 int:01 arithmetic:01 arithmetic:01 pointer:03 pointer:03 bits:05 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk This message is in MIME format. Since your mail reader does not understand this format, some or all of this message may not be legible. ------_=_NextPart_001_01C48079.057924C0 Content-Type: text/plain Hello Caml-list, why is the tag bit for a int/pointer is stored in and not next to a int/pointer. Isn't it possible to divide the memory in blocks of 33 (65 on 64 bit machines) Words and the first Word contains all the tag bits? Then we can enjoy an extra bit, some arithmetic operations could be done faster and all floats could be unboxed. Of couse this is just a naive idea, but please tell me why ;-) Regards, Christoph Bauer ------_=_NextPart_001_01C48079.057924C0 Content-Type: text/html The tag bit

Hello Caml-list,

why is the tag bit for a int/pointer is stored in and not next to a int/pointer.
Isn't it possible to divide the memory in blocks of 33 (65 on 64 bit machines)
Words and the first Word contains all the tag bits? Then we can enjoy an
extra bit, some arithmetic operations could be done faster and all floats could
be unboxed.

Of couse this is just a naive idea, but please tell me why ;-)

Regards,
Christoph Bauer

------_=_NextPart_001_01C48079.057924C0-- ------------------- 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 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 QAA00504; Thu, 12 Aug 2004 16:55:29 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA32675 for ; Thu, 12 Aug 2004 16:55:28 +0200 (MET DST) Received: from grisu.bik-gmbh.de (grisu.bik-gmbh.de [217.110.154.194]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7CEtPmL018258 for ; Thu, 12 Aug 2004 16:55:27 +0200 Received: from [192.168.125.193] ([192.168.125.193]) by grisu.bik-gmbh.de (8.12.8p2/8.12.8) with ESMTP id i7CEtJ1w037585; Thu, 12 Aug 2004 16:55:19 +0200 (CEST) (envelope-from hars@bik-gmbh.de) Message-ID: <411B84D2.7050705@bik-gmbh.de> Date: Thu, 12 Aug 2004 16:55:14 +0200 From: Florian Hars User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.7) Gecko/20040616 X-Accept-Language: de, de-de, en-us, en MIME-Version: 1.0 To: "Bauer, Christoph" CC: caml-list@inria.fr Subject: Re: [Caml-list] The tag bit References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, hits=-2.6 required=5.0 tests=EMAIL_ATTRIBUTION,IN_REP_TO,QUOTED_EMAIL_TEXT,REFERENCES, REPLY_WITH_QUOTES,USER_AGENT_MOZILLA_UA,X_ACCEPT_LANG version=2.55 X-Spam-Checker-Version: SpamAssassin 2.55 (1.174.2.19-2003-05-19-exp) X-Miltered: at nez-perce with ID 411B84DD.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; florian:01 hars:01 hars:01 bik-gmbh:01 caml-list:01 bauer:01 pointers:01 florian:01 compiler:01 ints:01 byte:01 byte:01 int:01 bytes:02 wrote:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bauer, Christoph wrote: > Isn't it possible to divide the memory in blocks of 33 (65 on 64 bit > machines) Words and the first Word contains all the tag bits? Good idea, but lets go the whole way: I always thougth the decision to have eight bits to a byte instead of nine most unfortunate. Why don't we just add a bit to all our bytes, we could express so much more per byte? Just imagine the possibilities in I18N: UTF-18 would need considerably less plane shifting that UTF-16. (On a more serious note: You propose to turn the tag bit into a tag long word, requiring two memory acesses instead of one and blowing up the storage requriments for ints and pointers by a factor of two, which will slow down about everything. You can get more or less the same effects now without any change to the compiler by using Int32.) Yours, Florian. ------------------- 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 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 QAA31613; Thu, 12 Aug 2004 16:56:26 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA00145 for ; Thu, 12 Aug 2004 16:56:25 +0200 (MET DST) Received: from qrnik.knm.org.pl (paf87.warszawa.sdi.tpnet.pl [217.96.225.87]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7CEuOmL018377 for ; Thu, 12 Aug 2004 16:56:24 +0200 Received: from qrnik ([192.168.0.1] ident=qrczak) by qrnik.knm.org.pl with esmtp (Exim 3.36 #1) id 1BvH06-0006Mb-00; Thu, 12 Aug 2004 16:56:18 +0200 Subject: Re: [Caml-list] The tag bit From: "Marcin 'Qrczak' Kowalczyk" To: "Bauer, Christoph" Cc: caml-list@inria.fr In-Reply-To: References: Content-Type: text/plain; charset=ISO-8859-2 Date: Thu, 12 Aug 2004 16:56:17 +0200 Message-Id: <1092322577.19848.87.camel@qrnik> Mime-Version: 1.0 X-Mailer: Evolution 1.5.9.2 Content-Transfer-Encoding: quoted-printable X-Miltered: at nez-perce with ID 411B8518.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 marcin:01 'qrczak':01 kowalczyk:01 qrczak:01 bauer:01 passing:01 marcin:01 kowalczyk:01 qrczak:01 ints:01 int:01 int:01 0200,:01 knm:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk W li=B6cie z czw, 12-08-2004, godz. 16:31 +0200, Bauer, Christoph napisa=B3= : > why is the tag bit for a int/pointer is stored in and not next to a > int/pointer. =20 > Isn't it possible to divide the memory in blocks of 33 (65 on 64 bit > machines) =20 > Words and the first Word contains all the tag bits? Value passing would be more complicated. If you apply a function to 2 arguments, now you pass it 2 words. In your scheme you would have to find and pass it 2 words plus 2 tag bits in a 3rd register. Currently a list of ints uses 3 words per element (a block whose first word is the header, and remaining words are head and tail). With your scheme it would be 4 words, i.e. 1/3 larger, not 1/32 larger. --=20 __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/ ------------------- 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 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 RAA01730; Thu, 12 Aug 2004 17:07:19 +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 RAA01458 for ; Thu, 12 Aug 2004 17:07:18 +0200 (MET DST) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from pierce.numericable.net (pierce.numericable.net [80.236.0.150]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7CF7IRM010015 for ; Thu, 12 Aug 2004 17:07:18 +0200 Received: (qmail 4516 invoked from network); 12 Aug 2004 15:07:17 -0000 Received: from unknown (HELO laposte.net) ([81.220.100.229]) (envelope-sender ) by pierce.numericable.net (qmail-ldap-1.03) with SMTP for ; 12 Aug 2004 15:07:17 -0000 Message-ID: <411B884C.3020508@laposte.net> Date: Thu, 12 Aug 2004 17:10:04 +0200 From: =?ISO-8859-1?Q?Olivier_P=E9r=E8s?= User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6) Gecko/20040206 X-Accept-Language: br, fr-fr, fr, en MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] The tag bit References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 411B87A6.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 bauer:01 65.:99 olivier:02 olivier:02 address:96 wrote:03 registers:07 registers:07 naive:08 precious:91 memory:09 processors:09 whereas:10 msb:89 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bauer, Christoph wrote: > Of couse this is just a naive idea, but please tell me why ;-) Well, I can see several reasons : * processors like powers of two, especially when it comes to the size of a memory address, because of cache issues, so you'd better make it 32 or 64 words than 33 or 65. * If the tag bit can be anywhere in a word you have to spend extra time to extract it, whereas when it is at a fixed place, especially LSB or MSB, it is very cheap and easy. * You would need two registers to access a value and its tag instead of one, and registers are very precious, at least on IA-32 architectures. Olivier. ------------------- 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 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 RAA00788; Thu, 12 Aug 2004 17:22:39 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA01151 for ; Thu, 12 Aug 2004 17:22:38 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7CFMamL021333 for ; Thu, 12 Aug 2004 17:22:37 +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 i7CFMVJ24210; Thu, 12 Aug 2004 10:22:31 -0500 (CDT) Date: Thu, 12 Aug 2004 10:30:18 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: "Bauer, Christoph" cc: caml-list@inria.fr Subject: Re: [Caml-list] The tag bit In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at nez-perce with ID 411B8B3C.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 bauer:01 caml-list:01 floats:01 unboxed:01 vaguely:01 slows:01 slows:01 ocaml:01 ocaml:01 garbage:01 garbage:01 int:01 int:01 arithmetic:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thu, 12 Aug 2004, Bauer, Christoph wrote: > Hello Caml-list, > > why is the tag bit for a int/pointer is stored in and not next to a > int/pointer. Isn't it possible to divide the memory in blocks of 33 (65 > on 64 bit machines) Words and the first Word contains all the tag bits? > Then we can enjoy an extra bit, some arithmetic operations could be done > faster and all floats could be unboxed. > > Of couse this is just a naive idea, but please tell me why ;-) My understanding: 1) The "extra overhead" of the tag bit is less than you might think in most code. Yeah, you have to do an instruction or two to adjust for the tag bit in some cases- but Ocaml is pretty good at omitting them when they're not needed (when a variable is stored in a register, for example). And the cost of these extra instructions is not great- especially compared to other costs you might hit without knowing it. They cost one, maybe two, clock cycles (assuming they aren't executed in parallel with other stuff, in which case they cost less than one clock cycle). A mispredicted branch costs 12-30 clock cycles. An L2 cache *hit* costs 20-30 clock cycles, and a cache *miss* that has to go to main memory 100-300 clock cycles. You can no longer even vaguely predict performance by counting instructions with modern CPUs. 2) Moving the tag bit out of the word slows down the garbage collector, according to experiments the maintainers did. It slows down the garbage collector by more than omitting the tag bit handling instructions speeds up the rest of the code. 3) Moving the tag bit out of word complicates handling variables of unknown type. Currently, Ocaml can just move whole words, and be sure the type information (int vr.s pointer) the GC needs moves with the word. With the tag bits stored elsewhere, moving a value of unknown type becomes a lot more complicated, as you have to move the tag bits seperately. -- "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