I had an idea based on (or actually copied from) something Goswin mentioned earlier in our discussion. What if the bits can be used to indicate embedded values? An embedded value would have a header inside the body of the parent value, making it possible to get rid of all pointers within that parent. This would represent a potentially large saving for the GC, as well as reducing random jumps around memory which are very cache-stressing.

In the spirit of this idea, here is my latest version:

+ For 16-bit and 32-bit architectures:
     +---------------+-------------+-----+-------+------+
     |       wosize  |pfbits type  |noptr| color | tag  |
     +---------------+-------------+-----+-------+------+
bits  31           19  18   17   16   15  14   13 12   0

pfbits type:
- 000: no pfbits
- 001: pfbits indicate embedded header
- 010: pfbits indicate float
- 011: pfbits indicate untagged type
- 100: pfbits indicate int64
- 101: pfbits indicate float/embdedded header/untagged type, 2 bits per field
- 110: pfbits indicate float/untagged type/int64, 2 bits per field
- 111: pfbits indicate embedded header/untagged type/int64, 2 bits per field

- noptr: no pointers present
- if wosize = 0, the extension word is used for wosize
- if both wosize = 0 and the pfbits are used, the wosize_large is first in memory

wosize_large word (if wosize is 0 in the header)
     +---------------------------------------------+
     |                   wosize                    |
     +---------------------------------------------+
bits  31                                          0

32 bit pfbits word (present only if called for by pfbits type in header)
     +---------------------------------------------+
     |                   pfbits                    |
     +---------------------------------------------+
bits   31  30                                     0

- pfbits:
    - If working in 1 bit mode, each bit represents whatever is signaled in the pfbits type field.
    - If working in 2 bit mode, 00 always represents a regular word, and 01, 10, 11 represent their type as signaled in the pfbit type field.



+ For 64-bit architectures:

     +-------------+--------+----------+---+------+-------+------+
     |     pfbits  | wosize |pfbit type|exp| noptr| color | tag  |
     +-------------+--------+----------+---+------+-------+------+
bits  63         40 39    20 19      17 16    15   14   13 12   0


- noptr: a structure with no pointers.
- pfbits: a small pfbits field for smaller objects
- pfbits type: (slightly different than 32-bit architecture)
    - 000: no pfbits, wosize includes pfbits as its upper bits
    - 001: pfbits indicate embedded header
    - 010: pfbits indicate float
    - 011: pfbits indicate untagged type
    - 100: pfbits indicate int64
    - 101: pfbits indicate float/untagged type/embedded header, 2 bits per field
    - 110: pfbits indicate float/untagged type/int64, 2 bits per field
    - 111: pfbits indicate int64/untagged type/embedded header, 2 bits per field
- exp: use pfbits_expanded for signaling pfbits. Pfbits in header become top bits of wosize.


     +--------------------------------------------------------+
     |                pfbits_expanded                         |
     +--------------------------------------------------------+
bits  63                                                     0

- pfbits_expanded: if exp is set, pfbits_expanded takes the place of the pfbits. wo_size is joined with the pfbits in the header.

+ Tags:

- 0: Array, record, tuple tag
- 1: Infix tag (must be 1 mod 4)
- 2: Closure tag
- 3: Lazy tag
- 4: Object tag
- 5: Forward tag
- 6: Abstract tag
- 7: String tag
- 8: Double tag
- 9: Custom tag
- 10: Double_array tag
- 11: Proposed: Int32_array tag
- 12: Proposed: Int64_array tag
- 13: Proposed: Cptr_array tag
- 14: Proposed: float32_array tag
- 1000: first user tag

-Yotam


On Tue, Oct 8, 2013 at 6:52 AM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
On Mon, Sep 30, 2013 at 11:31:23AM -0400, Yotam Barnoy wrote:
> On Mon, Sep 30, 2013 at 10:48 AM, Goswin von Brederlow <goswin-v-b@web.de>wrote:
>
> > >
> > > + For 16-bit and 32-bit architectures:
> > >      +---------------+----+----+-----+-------+------+
> > >      |     wosize    | ext|cust|noptr| color | tag  |
> > >      +---------------+----+----+-----+-------+------+
> > > bits  31           21  20   19   18   17   16 15   0
> > >
> > > - noptr: no pointers present
> > > - ext:  uses extension word
> > > - cust(om): uses custom word. Custom word is normally used to indicate
> > > floats and pointers.
> > >
> > > 32 bit extension word (present only if ext is 1)
> > >      +---------------------------------------------+
> > >      |                   wosize                    |
> > >      +---------------------------------------------+
> > > bits  31                                          0
> >
> > Why use a full bit for ext? I would define wosize == 0 to mean an
> > extension word with the actual size is present. That way sizes up to
> > <16KB can be encoded without extension word.
> >
> >
> Great point! Of course, that makes perfect sense. I was feeling like I was
> wasting the wosize bits with the extension word but couldn't quite get put
> 2 and 2 together.
> BTW, down the thread is a newer version of the design that reduces the tag
> space to 8000 tags, which I do think is sufficient.
>
>
>
> >  > 32 bit custom word (default usage - present only if cust is 1):
> > >      +----+----------------------------------------+
> > >      |nofp|              pfbits                    |
> > >      +----+----------------------------------------+
> > > bits   31  30                                     0
> > >
> > > - nofp: a structure with no floats. All pfbits are used for pointers,
> > with
> > > a 1 signifying a pointer and a 0 signifying a value.
> > > - pfbits: indicates which double words are floats and pointers. Starting
> > at
> > > the highest bit:
> > >     - a 0 indicates neither a pointer nor a float
> > >     - a 10 indicates a float (double)
> > >     - a 11 indicates a pointer
> > >     - If noptr is set, each bit indicates a float. If nofp is set, each
> > bit
> > > indicates a pointer.
> >
> > There are 3 kinds of values:
> >
> > 1) pointers with bit 0 == 0
> > 2) non-pointers with bit 0 == 1
> > 3) floats with all bits used for the type (spanning 2 fields in 32bit)
> >
> > So if pfbits indicates a float then a field (or 2) is a float and all
> > bits are used for the value. Otherwise the bit 0 of the field will
> > tell you wether it is a pointer or not. So why would you want to
> > duplicate that information in the pfbits?
> >
>
> I was thinking of doing it for efficiency. If we're already indicating
> what's what, we might as well represent shortcuts to the pointers, which
> would cut down on the amount of reading, no? In the average case, the GC
> would need to access a lot less memory.
>
>
> > It might be nice to support C values like untagged ints or unaligned
> > pointers. If Custom tag is set then the pfbits become ocaml value
> > bits. The GC will only inspect fields with pfbit set. All other fields
> > are ignored. The custom_operations handle compare, hash, serialize and
> > deserialize so nothing else will access the data.
> >
> > Another thing are int32 and int64. I guess if you want to unbox those
> > then having 2 bits per field in pfbits makes sense again. But then I
> > would allocate them as:
> >
> >     - a 00 indicates a tagged value (int or pointer)
> >     - a 01 indicates a non-pointer: int, int32, native int, C pointer
> >     - a 10 indicates a float (double)
> >     - a 11 indicates an int64
> >
> > The higher bit would indicate a 64bit value, meaning spanning 2 fields
> > on 32bit. Not that those 4 values allow mixing ocaml values, C values,
> > int32, int64 and float in a block.
> >
> > I would combine the noptr and nofp bits into a single 2bit field:
> >
> >     - a 00 indicates no pointers and no double size, no pfbits
> >     - a 01 indicates no double size, pfbits indicate tagged / non-pointer
> >     - a 10 indicates no pointers but double size, pfbits indicate size
> >     - a 11 indicates both pointers and double size, 2 pfbits per field
> >
> > Note: tagged integers can be stored as 00 or 01. I think this would be
> > required for polymorphic types. An 'a could be int or pointer. In both
> > cases 00 will work.
> >
> >
> I really like this idea -- unboxing more types could be really useful. I'm
> not sure double 'size' would work, however. It should be fine for the
> marshal module, but polymorphic comparison would get messed up because
> floats have to be compared differently. So I think 10 in the bit field
> should indicate no pointers but floats, while 11 could allow both pointers
> and double size, with the 2-bits specifying if it's a float or an int64 (as
> you've outlined). Of course, one cannot have both shortcuts to pointers and
> enhanced unboxing, so let me know what you think about the performance
> increase from shortcutting the tag bit.
>
> Yotam

Lets look at an example:

type 'a r = { a:int; b:float; c:int32; d:int64; e:'a; }

For 16-bit and 32-bit architectures:
     +--------------------+----------+-------+------+
     |     wosize         |pfbit type| color | tag  |
     +--------------------+----------+-------+------+
bits  31               20   19   18   17   16 15   0

wosize = 7
pfbit type = 11 (pointers and double size)

     +------------------------------+--+--+--+--+--+
     |                   pfbits     |00|11|01|10|01|
     +------------------------------+--+--+--+--+--+
                                      e  d  c  b  a

The GC only needs to check e since 'a might be a pointer. All other fields
are marked as non pointer.

Comparison does a plain bit comparison on a, c and d, a float
comparison on b and a tagged comparison on e. Similar for marshaling.
There is no confusion between int64 and floats.

MfG
        Goswin