From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr 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 3FC4F7EE4B for ; Mon, 30 Sep 2013 17:31:45 +0200 (CEST) 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.44; 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.44 as permitted sender) identity=mailfrom; client-ip=209.85.216.44; 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-qa0-f44.google.com) identity=helo; client-ip=209.85.216.44; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yotambarnoy@gmail.com"; x-sender="postmaster@mail-qa0-f44.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AoMBAFGYSVLRVdgsnGdsb2JhbABahBHAfYElCBYOAQEBAQEGDQkJFCiCJQEBBAFAARsdAQMBCwYFCzsiAREBBQEcBhOHcwEDCQafRIxSgwqEEwoZJw0VT4kAAQUMj0UHhCIDl3+QDxgphGkg X-IPAS-Result: AoMBAFGYSVLRVdgsnGdsb2JhbABahBHAfYElCBYOAQEBAQEGDQkJFCiCJQEBBAFAARsdAQMBCwYFCzsiAREBBQEcBhOHcwEDCQafRIxSgwqEEwoZJw0VT4kAAQUMj0UHhCIDl3+QDxgphGkg X-IronPort-AV: E=Sophos;i="4.90,1008,1371074400"; d="scan'208";a="34941486" Received: from mail-qa0-f44.google.com ([209.85.216.44]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 30 Sep 2013 17:31:43 +0200 Received: by mail-qa0-f44.google.com with SMTP id j7so2432605qaq.10 for ; Mon, 30 Sep 2013 08:31:43 -0700 (PDT) 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=rp2ofC4ZkanVniKb/+HsUu+lrh0JqnCBNt/aV4oMXmQ=; b=J4mtYtkDZnYloNoXqSd64V+Jg4OjCiCXnzrmDKg7IijNOsLisyylu+eRniEvdMWUlU 5CCR/mzRuowhnMEHI+mVOTcHzw0QkT85ic1T2wGQv3dfgISp1E2QqZcUB3FYb8ltTzaX lSWNvlmUAZK30r3yR4EpCe5EzaccT/9NkPrAxw4cyDIo7y8dt4ODndycaZyp4fsKP4qE OfdpUV/q2XVvRGsq/U6W/YAXcocQXnhVNXxPepqBLfJubMstAT4XyTHTeFBu6posJFGw p984hZ6SJ2pR0XqIeeqE8Bwa+H+Nvd57Qs1RQdCgVBVi0AwZXL8/AYc/L3K39LiTY38J ImLQ== X-Received: by 10.49.131.132 with SMTP id om4mr29458993qeb.2.1380555103083; Mon, 30 Sep 2013 08:31:43 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.139.20 with HTTP; Mon, 30 Sep 2013 08:31:23 -0700 (PDT) In-Reply-To: <20130930144842.GE8693@frosties> References: <20130930144842.GE8693@frosties> From: Yotam Barnoy Date: Mon, 30 Sep 2013 11:31:23 -0400 Message-ID: To: Goswin von Brederlow Cc: Ocaml Mailing List Content-Type: multipart/alternative; boundary=047d7beb9a4683253004e79b8807 Subject: Re: [Caml-list] Proposal: re-design of ocaml headers --047d7beb9a4683253004e79b8807 Content-Type: text/plain; charset=ISO-8859-1 On Mon, Sep 30, 2013 at 10:48 AM, Goswin von Brederlow 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 --047d7beb9a4683253004e79b8807 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
On M= on, Sep 30, 2013 at 10:48 AM, Goswin von Brederlow <goswin-v-b@web.de&= gt; wrote:
>
> + For 16-bit and 32-bit architectures:
> =A0 =A0 =A0+---------------+----+----+-----+-------+------+
> =A0 =A0 =A0| =A0 =A0 wosize =A0 =A0| ext|cust|noptr| color | tag =A0|<= br> > =A0 =A0 =A0+---------------+----+----+-----+-------+------+
> bits =A031 =A0 =A0 =A0 =A0 =A0 21 =A020 =A0 19 =A0 18 =A0 17 =A0 16 15= =A0 0
>
> - noptr: no pointers present
> - ext: =A0uses 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)
> =A0 =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+---------------------------------------------+
> bits =A031 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0= =A0 =A0 =A0 =A0 =A0 =A00

Why use a full bit for ext? I would define wosize =3D=3D 0 to m= ean 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, tha= t makes perfect sense. I was feeling like I was wasting the wosize bits wit= h 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 reduc= es the tag space to 8000 tags, which I do think is sufficient.

=A0
> 32 bit custom word (default usage - present only if cust is 1):
> =A0 =A0 =A0+----+----------------------------------------+
> =A0 =A0 =A0|nofp| =A0 =A0 =A0 =A0 =A0 =A0 =A0pfbits =A0 =A0 =A0 =A0 = =A0 =A0 =A0 =A0 =A0 =A0|
> =A0 =A0 =A0+----+----------------------------------------+
> bits =A0 31 =A030 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 = =A0 =A0 =A0 =A0 =A0 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. Starti= ng at
> the highest bit:
> =A0 =A0 - a 0 indicates neither a pointer nor a float
> =A0 =A0 - a 10 indicates a float (double)
> =A0 =A0 - a 11 indicates a pointer
> =A0 =A0 - 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 =3D=3D 0
2) non-pointers with bit 0 =3D=3D 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 indicati= ng what's what, we might as well represent shortcuts to the pointers, w= hich would cut down on the amount of reading, no? In the average case, the = GC would need to access a lot less memory.
=A0
It might be nice to supp= ort 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:

=A0 =A0 - a 00 indicates a tagged value (int or pointer)
=A0 =A0 - a 01 indicates a non-pointer: int, int32, native int, C pointer
=A0 =A0 - a 10 indicates a float (double)
=A0 =A0 - 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:

=A0 =A0 - a 00 indicates no pointers and no double size, no pfbits
=A0 =A0 - a 01 indicates no double size, pfbits indicate tagged / non-point= er
=A0 =A0 - a 10 indicates no pointers but double size, pfbits indicate size<= br> =A0 =A0 - a 11 indicates both pointers and double size, 2 pfbits per field<= br>
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<= br> cases 00 will work.


I really like this idea -- unboxing mo= re types could be really useful. I'm not sure double 'size' wou= ld work, however. It should be fine for the marshal module, but polymorphic= comparison would get messed up because floats have to be compared differen= tly. 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 specif= ying if it's a float or an int64 (as you've outlined). Of course, o= ne cannot have both shortcuts to pointers and enhanced unboxing, so let me = know what you think about the performance increase from shortcutting the ta= g bit.
=A0
Yotam
--047d7beb9a4683253004e79b8807--