[Caml-list] The tag bit

[Caml-list] The tag bit

[Bauer, Christoph]

[-- Attachment #1: Type: text/plain, Size: 435 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 934 bytes --]

Re: [Caml-list] The tag bit

[Florian Hars]

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

Re: [Caml-list] The tag bit

[Marcin 'Qrczak' Kowalczyk]

W liście z czw, 12-08-2004, godz. 16:31 +0200, Bauer, Christoph napisał:

> 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?

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.

-- 
   __("<         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

Re: [Caml-list] The tag bit

[Olivier Pérès]

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

Re: [Caml-list] The tag bit

[Brian Hurt]

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