Re: [Caml-list] The tag bit

[Brian Hurt <bhurt@spnz.org>]

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