Type Tags: Re: IRHG - GC Memory Fragmentation?

Gary Wright wrote:
>
> On Jan 1, 2008, at 9:27 PM, Kurt Stephens wrote:
>>
>> I have a question: why were Symbols made immediate with a dedicated
>> type tag in VALUE?
>>
>> http://kurtstephens.com/node/52
>
> re: your blog posting:
>
> If Fixnums had a two-bit tag of 00, how would you distinguish between
> fixnum instances and pointers to objects?  Wouldn't you have to do
> some bit twiddling before dereferencing every object pointer?
>
Ruby Fixnums and other types are already distinguished by the type tags.
The rationale for choosing a fixed-size lower 2-bit type tag, opposed to
a dynamic-length type tag, as in Ruby, or high-bit tags, like some older
Lisp implementations, is as follows:

C compilers and dynamic memory allocators will align allocations to
word-boundaries for performance reasons, so there cannot not be a
pointer to an object that would require the lower bits of a pointer,
except for sub-word access, e.g.: char *.  32-bit words are 4 bytes
long; the lower two-bits of any object pointer will always be zero, and
is free to be used for type tagging.

If references to allocated objects are encoded using a 0x03 type tag,
tag removal could be:

  #define RBASIC(X) ((struct RBasic*)((X)-3))

Assuming that most of the time the interpreter is referencing structure
members of the object, and does not need the actual address of the object:

  struct RBasic {
      VALUE flags; /* struct offset: 0 */
      VALUE klass; /* struct offset: 4 */
  };

  RBASIC(X)->klass =>
  ((struct RBasic*)((X)-3))->klass

C compilers convert the -> operator into an offset from an address.  For
32-bit VALUEs:

  RBASIC(X)->flags => *(VALUE*)((X)-3+0)
  RBASIC(X)->klass => *(VALUE*)((X)-3+4)

Using subtraction as the tag removal operation, instead of (X &~3),
allows the C compiler to constant fold the tag removal and the structure
offset:

  RBASIC(X)->flags => *(VALUE*)((X)-3)
  RBASIC(X)->klass => *(VALUE*)((X)+1)

Therefore, there is no additional tag removal cost to reference
structure members with non-zero offsets.  I would reorder the members
depending on which is "hotter".

Research shows that tag manipulation is a heavy cost, esp. for numerics;
any tagging scheme should be as simple and consistent as possible.

For example, determining the class of a VALUE could be inlined:

  #define CLASS_OF(v) ((v) & 3) ? RBASIC(v)->klass : rb_cFixnum)

Kurt Stephens