From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 83D487F75D for ; Thu, 30 Jan 2014 21:54:13 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of yotambarnoy@gmail.com) identity=pra; client-ip=209.85.216.171; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yotambarnoy@gmail.com"; x-sender="yotambarnoy@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of yotambarnoy@gmail.com designates 209.85.216.171 as permitted sender) identity=mailfrom; client-ip=209.85.216.171; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yotambarnoy@gmail.com"; x-sender="yotambarnoy@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-qc0-f171.google.com) identity=helo; client-ip=209.85.216.171; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yotambarnoy@gmail.com"; x-sender="postmaster@mail-qc0-f171.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqMCAMe66lLRVdirlGdsb2JhbABPCoQbvSSBBAgWDgEBAQEHCwsJEiqCJgEBBEABGx0BAwwGBQs7IgERAQUBHAaIAwEDEZ9cjFyDCZMMChknDWSIMhEBBQyOGlwHhDgEiUmKd4NokDIYKYR3Hg X-IPAS-Result: AqMCAMe66lLRVdirlGdsb2JhbABPCoQbvSSBBAgWDgEBAQEHCwsJEiqCJgEBBEABGx0BAwwGBQs7IgERAQUBHAaIAwEDEZ9cjFyDCZMMChknDWSIMhEBBQyOGlwHhDgEiUmKd4NokDIYKYR3Hg X-IronPort-AV: E=Sophos;i="4.95,752,1384297200"; d="scan'208";a="56139994" Received: from mail-qc0-f171.google.com ([209.85.216.171]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 30 Jan 2014 21:54:12 +0100 Received: by mail-qc0-f171.google.com with SMTP id n7so5912538qcx.30 for ; Thu, 30 Jan 2014 12:54:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=XJcyWvaivcDJDwtXpDQBlM5MhqogMl7PjEgGnp+lpd0=; b=V9p2rB9kr/AYmOWA9VWtqqFv+FUCv38FsWZvhV4IrgeWMaAK3FG0dzF0ze967IP88a ttLXttmp3z9J+L1uYCIgx4v8mwvvW1cuQVzGiszZQrPglJqXz8NYZFI74XIGmRp8V54h VlILW2+N4ZH2m2v8RcwO1UyVfqLTAz4ArsFJZy07txOX+e7gkRhAgUlc5/22LYyX4Ihu 4zbTzloe+mF2JozkARpkSM908kOSFSy31e82QKTVfEnOnwwWEbvdaNzmeDVllBLuciGS 6wRY3eIiOfVtmvPuHrHn7NZ4t8MBXbzj2lPtbApRlTCtnd1+WclLT6iL3eHxO4mvXD7b 5F/w== X-Received: by 10.140.107.138 with SMTP id h10mr23946171qgf.30.1391115251742; Thu, 30 Jan 2014 12:54:11 -0800 (PST) MIME-Version: 1.0 Received: by 10.224.106.137 with HTTP; Thu, 30 Jan 2014 12:53:51 -0800 (PST) In-Reply-To: References: <20130930144842.GE8693@frosties> <20131008105246.GA15550@frosties> From: Yotam Barnoy Date: Thu, 30 Jan 2014 15:53:51 -0500 Message-ID: To: Goswin von Brederlow Cc: Ocaml Mailing List Content-Type: multipart/alternative; boundary=001a11395ae06bfc4004f13642b5 Subject: Re: [Caml-list] Proposal: re-design of ocaml headers --001a11395ae06bfc4004f13642b5 Content-Type: text/plain; charset=ISO-8859-1 I'm resurrecting this thread. Given the recent discussion about optimization, I've done some more thinking and simplification work on my proposal for a better ocaml header. Much of this is just adopting Goswin's proposal, which made a lot of sense. I tried to also reduce the variations while allowing for a lot of useful unboxing of floats, int64s etc. I've also tried to tackle tuples in this version -- basically, in order to be compatible with polymorphic functions, you really want tuples and all other polymorphic types (as in 'a embedded inside records) to be of uniform size. Expanding that size under some circumstances to 64 bits on 32 bit platforms makes sense if, for example, the tuple contains many floats. I don't think handling both what I call narrow and wide polymorphic types (for lack of a better name) will make the code much more complex -- I certainly don't want it to result in heavy register spilling. Also, the dynamic parts of the header now appear BEFORE the header itself. Their highest bit is 0 to indicate that they're not the main header. This will be seen by GC code, which can afford to do the few extra comparisons. Mutator code will always have the main header available right before the data. So here it is: + For 32-bit architectures: --------------------------- Wide Types ---------- - For polymorphic types (containing 'a), member sizes need to be uniform for speed. Tuples are fully polymorphic. These polymorphic members can either be narrow (32 bit) as they are now or wide (64 bit) to accomodate float/int64 unboxing. +-----------+--------------+------+-----+-------+------+ | 1 | wosize| fbits |ebits |noptr| color | tag | +-----------+--------------+------+-----+-------+------+ bits 31 30 21 20 15 14 13 12 11 10 0 - noptr: no pointers present. - fbits: wide types cannot be represented unless extbits is used - 00: tagged (int/pointer) - 01: int32/native int, C pointer - 10: float - 11: int64 - if wosize = 0, the size word is used for wosize size word --------- - only present if wosize is 0 in the header. Precedes the main header +---------------------------------------------+ | 0 | wosize | +---------------------------------------------+ bits 31 30 0 - bit 31 is used to identify this as a header extension ext word -------- - Only present if ebits is 1. Describes the first 15 members of the object (+ 3 members from fbits) +----------+----------------------------------+ | 0 | wide | extbits | +----------+----------------------------------+ bits 31 30 29 0 - bit 31 is used to identify this as a header extension - wide: determines if 'a types in the first 18 words are wide (64 bit) or narrow (32 bits) - extbits: same as fbits Tuples ------ - Tuples with any fbits on in the header word are automatically wide tuples (64 bit) for the first 3 words - Tuples with ebits are automatically wide tuples for the first 18 words. wide is ignored. Strings ------- - In strings, the last fbit, ebits and noptr function as the string size modifier (currently present at the end of the string). This improves cache locality on large strings. Wosize expands to include the fbits. Arrays ------ - Arrays of integers, int64, floats, C pointers etc can all be handled with the regular array type. - Only 2 lower fbits are needed for the type. The other fbits are joined with wosize. + 64-bit architectures: -------------------------- +-----------+------------------+------+-----+-------+------+ | 1 | wosize| fbits |ebits |noptr| color | tag | +-----------+------------------+------+-----+-------+------+ bits 63 62 43 42 15 14 13 12 11 10 0 - noptr: a structure with no pointers. - fbits: 2 bits per object member - 00: tagged (int/pointer) - 01: int32 - 10: float - 11: int64/native int/C pointer - ebits: use ext word for signaling bits. fbits in header become bottom bits of wosize. ext_word -------- - Only present if ebits is 1. Describes the first 31 members of the object. +---------------------------------------------+ | 0 | - | extbits | +---------------------------------------------+ bits 63 62 61 0 - bit 31 is used to identify this as a header extension - extbits: same as fbits Strings ------- - In strings, the last fbit, ebits and noptr function as the string size modifier (currently present at the end of the string). This improves cache locality on large strings. Wosize expands Arrays ------ - Only the 2 lowest fbits are needed to discriminate the type. All other fbits are joined to wosize. + Tags: ------- - 0: Array tag - 1: Record tag - 2: Tuple tag - 3: Infix tag - 4: Closure tag - 5: Lazy tag - 6: Object tag - 7: Forward tag - 8: Abstract tag - 9: String tag (pfbit type used for size completion) - 10: Primitive value tag (double, int64, int32) - 11: Custom tag - 100: First user tag Comments? Yotam --001a11395ae06bfc4004f13642b5 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
I'm resurrecting this thread.

Given t= he recent discussion about optimization, I've done some more thinking a= nd simplification work on my proposal for a better ocaml header. Much of th= is is just adopting Goswin's proposal, which made a lot of sense. I tri= ed to also reduce the variations while allowing for a lot of useful unboxin= g of floats, int64s etc. I've also tried to tackle tuples in this versi= on -- basically, in order to be compatible with polymorphic functions, you = really want tuples and all other polymorphic types (as in 'a embedded i= nside records) to be of uniform size. Expanding that size under some circum= stances to 64 bits on 32 bit platforms makes sense if, for example, the tup= le contains many floats. I don't think handling both what I call narrow= and wide polymorphic types (for lack of a better name) will make the code = much more complex -- I certainly don't want it to result in heavy regis= ter spilling.

Also, the dynamic parts of the header now appear BEFORE the = header itself. Their highest bit is 0 to indicate that they're not the = main header. This will be seen by GC code, which can afford to do the few e= xtra comparisons. Mutator code will always have the main header available r= ight before the data.


So here it is:


+ For 32-bit architectures:
------------------= ---------

Wide Types
----------
- For polymorphic types (conta= ining 'a), member sizes need to be uniform for speed. Tuples are fully = polymorphic. These polymorphic members can either be narrow (32 bit) as the= y are now or wide (64 bit) to accomodate float/int64 unboxing.

=A0=A0=A0=A0 +-----------+--------------+------+-----+-------+------+=A0=A0=A0=A0 | 1 | wosize|=A0=A0=A0 fbits=A0=A0=A0=A0 |ebits |noptr| colo= r | tag=A0 |
=A0=A0=A0=A0 +-----------+--------------+------+-----+-----= --+------+
bits=A0 31=A0 30=A0=A0 21 20=A0=A0=A0=A0=A0=A0=A0=A0=A0 15=A0= =A0 14=A0=A0=A0=A0 13=A0 12=A0=A0 11 10=A0=A0 0

- noptr: no pointers present.
- fbits: wide types cannot be represen= ted unless extbits is used
=A0=A0=A0 - 00: tagged (int/pointer)
=A0=A0=A0 - 01: int32/n= ative int, C pointer
=A0=A0=A0 - 10: float
=A0=A0=A0 - 11: int64

- if wosize =3D 0, th= e size word is used for wosize

size word
---------
- only pre= sent if wosize is 0 in the header. Precedes the main header
=A0=A0=A0=A0= +---------------------------------------------+
=A0=A0=A0=A0 | 0 |=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 wosize=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 |
=A0=A0=A0=A0 +----= -----------------------------------------+
bits=A0 31=A0 30=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0 0

- bit 31 is used to identify this as a he= ader extension


ext word
--------
- Only present if ebits is 1. Describes the= first 15 members of the object (+ 3 members from fbits)
=A0=A0=A0=A0 +-= ---------+----------------------------------+
=A0=A0=A0=A0 | 0 | wide |= =A0=A0=A0=A0=A0=A0=A0 extbits=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0 |
=A0=A0=A0=A0 +----------+----------------------------------+
bits=A0=A0 = 31=A0 30=A0=A0=A0=A0 29=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 0

- bit 31 is used to identify = this as a header extension
- wide: determines if 'a types in the fir= st 18 words are wide (64 bit) or narrow (32 bits)
- extbi= ts: same as fbits


Tuples
------
- Tuples with any fbits on in the= header word are automatically wide tuples (64 bit) for the first 3 words - Tuples with ebits are automatically wide tuples for the first 18 words. w= ide is ignored.

Strings
-------
- In strings, the last fbit, e= bits and noptr function as the string size modifier (currently present at t= he end of the string). This improves cache locality on large strings. Wosiz= e expands to include the fbits.

Arrays
------
- Arrays of integers, int64, floats, C pointers etc= can all be handled with the regular array type.
- Only 2 lower fbits ar= e needed for the type. The other fbits are joined with wosize.


+ 64-bit architectures:
--------------------------

=A0=A0=A0=A0 += -----------+------------------+------+-----+-------+------+
=A0=A0=A0=A0= | 1 | wosize|=A0=A0=A0 fbits=A0=A0=A0=A0=A0=A0=A0=A0 |ebits |noptr| color = | tag=A0 |
=A0=A0=A0=A0 +-----------+------------------+------+-----+---= ----+------+
bits=A0 63=A0 62=A0=A0 43 42=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 15=A0= =A0 14=A0=A0=A0=A0 13=A0 12=A0=A0 11 10=A0=A0 0


- noptr: a struc= ture with no pointers.
- fbits: 2 bits per object member
=A0=A0=A0 -= 00: tagged (int/pointer)
=A0=A0=A0 - 01: int32
=A0=A0=A0 - 10: float=
=A0=A0=A0 - 11: int64/native int/C pointer

- ebits: use ext word for= signaling bits. fbits in header become bottom bits of wosize.


e= xt_word
--------
- Only present if ebits is 1. Describes the first 31= members of the object.
=A0=A0=A0=A0 +---------------------------------------------+
=A0=A0=A0= =A0 | 0 | - |=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 extbits=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 |
=A0=A0=A0=A0 +-------------------------= --------------------+
bits=A0=A0 63=A0 62=A0 61=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= 0

- bit 31 is used to identify this as a header extension
- extbits: s= ame as fbits

Strings
-------
- In strings, the last fbit, ebit= s and noptr function as the string size modifier (currently present at the = end of the string). This improves cache locality on large strings. Wosize e= xpands

Arrays
------
- Only the 2 lowest fbits are needed to discriminat= e the type. All other fbits are joined to wosize.

+ Tags:
-------=
- 0: Array tag
- 1: Record tag
- 2: Tuple tag
- 3: Infix tag - 4: Closure tag
- 5: Lazy tag
- 6: Object tag
- 7: Forward tag- 8: Abstract tag
- 9: String tag (pfbit type used for size completion)=
- 10: Primitive value tag (double, int64, int32)
- 11: Custom tag
- 100: First user tag

Comments?
Yota= m
--001a11395ae06bfc4004f13642b5--