<html>
<head>
<style>
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
</style>
</head>
<body class='hmmessage'>
The heap allocation and pressure on the garbage collector -- such a small struct is reasonably efficient to pass around by value.<BR>
<BR>
- Jay<BR><BR> <BR>
<HR id=stopSpelling>
From: hosking@cs.purdue.edu<BR>To: jay.krell@cornell.edu<BR>Date: Thu, 9 Apr 2009 14:22:52 +1000<BR>CC: m3devel@elegosoft.com<BR>Subject: Re: [M3devel] small objects<BR><BR>
<DIV><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate">
<DIV style="WORD-WRAP: break-word"><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate"><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate"><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate"><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate"><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate"><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate"><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate"><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate">
<DIV>I don't know what you are saving over just allocating:</DIV>
<DIV><BR></DIV>
<DIV>NEW(OBJECT i: INTEGER END)</DIV>
<DIV>NEW(OBJECT r: REFANY END)</DIV>
<DIV><BR></DIV>
<DIV>Each is only 2 words: one for the object header and the other for the value.</DIV>
<DIV><BR></DIV></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></DIV></SPAN></DIV>
<DIV>
<DIV>On 9 Apr 2009, at 13:59, Jay wrote:</DIV><BR class=EC_Apple-interchange-newline>
<BLOCKQUOTE><SPAN class=EC_Apple-style-span style="WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate">
<DIV class=EC_hmmessage style="FONT-SIZE: 10pt; FONT-FAMILY: Verdana">Um, what do folks think of, like:<BR> <BR>struct<BR>{<BR> void* Type;<BR> union<BR> {<BR> size_t Integer;<BR> void* Pointer;<BR> } Value;<BR>} Variant;<BR> <BR>?<BR>You know -- something that is two pointers, one pointer for the type, one for the value or integer?<BR>void* Type would actually be a pointer to something actually defined and elaborate.<BR> <BR>Obviously this is twice as large, not as small as it could be, but much more general and portable. No need to determine how many of bits can be the tag.<BR> <BR>And hope/assume for perf that such a small struct is passed in registers.<BR>On x86/NT 4 and 8 byte structs I think are.<BR> <BR>Type could also be an integer, index into some table, with some predefined values.<BR>#define TYPE_INTEGER 0<BR>#define TYPE_FLOAT 1<BR>#define TYPE_DOUBLE 2<BR>#define TYPE_ADDRESS 3<BR> <BR>more generally the union would have a float, and maybe a double on 64bit platforms.<BR> <BR>OR, on 64bit platforms, you probably can, with some porting work, dedicate a whole 8 bits or so to a type index, and still the thing in one "word". How many bits of address space does any 64bit platform these days or forseeable future actually implement?<BR> <BR>But 32 bits doesn't seem big enough to afford that, and still this is a portability problem -- anything less than a full pointer.<BR> <BR> - Jay<BR><BR> <BR>> From:<SPAN class=EC_Apple-converted-space> </SPAN><A href="mailto:hosking@cs.purdue.edu">hosking@cs.purdue.edu</A><BR>> To:<SPAN class=EC_Apple-converted-space> </SPAN><A href="mailto:rodney.m.bates@cox.net">rodney.m.bates@cox.net</A><BR>> Date: Thu, 9 Apr 2009 13:01:13 +1000<BR>> CC:<SPAN class=EC_Apple-converted-space> </SPAN><A href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</A><BR>> Subject: Re: [M3devel] small objects<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> Sounds like you want something like:<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> TAGGED REFANY FOR T<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> where T must be a type that fits into BITS(REFANY)-1?<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> Branding could be used to prevent mixing otherwise structurally<SPAN class=EC_Apple-converted-space> </SPAN><BR>> equivalent TAGGED REFANY.<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> TAGGED BRANDED REFANY FOR T<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> Where this breaks down is what are the subtyping rules, since I assume<SPAN class=EC_Apple-converted-space> </SPAN><BR>> you'd like to store these in a REFANY and dynamically test for the<SPAN class=EC_Apple-converted-space> </SPAN><BR>> appropriate tagged type:<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> TAGGED REFANY FOR T <: REFANY<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> But then how do we distinguish all the different TAGGED REFANY from<SPAN class=EC_Apple-converted-space> </SPAN><BR>> each other at run-time?<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> On 9 Apr 2009, at 12:13, Rodney M. Bates wrote:<BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR>> > Mika Nystrom wrote:<BR>> >> Hmm, ok, there's one big difference between what you're saying and<BR>> >> what Tony and I have been talking about. (I think your understanding<BR>> >> sounds pretty correct.)<BR>> >><BR>> >> You want to do objects other than small integers. Like what? And<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >> why?<BR>> >> I was thinking the trick would apply only to one specific type of<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >> integer.<BR>> >><BR>> ><BR>> > Yes, I want a language mechanism that can be used by various<BR>> > modules to implement various abstract data types, each of which<BR>> > can perform the sometimes dramatic space optimization of putting<BR>> > values that are common and will fit directly in the word.<BR>> > One module I spoke of implements general sets of integers with<BR>> > dynamically variable and sometimes large range. This differs from<BR>> > the builtin SET OF.., which must have a static (and probably<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > relatively<BR>> > small) base subrange. Thus the general, heap-allocated values contain<BR>> > open arrays of Word.T, treated as sets, or if you prefer, packed<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > arrays<BR>> > of booleans, although I manipulate them with bit-twiddling operations<BR>> > from Word.<BR>> > There is another, static-sized, heap-allocated object in front of<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > each array,<BR>> > containing biases on what bits correspond to what integers in the<BR>> > abstract set, etc. It all works fine now, but the usage pattern of<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > some<BR>> > clients has a high percentage very small sets that would fit in a<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > word,<BR>> > and there would be an 11-to-1 space savings if that could be done.<BR>> > BTW, there are also two different kinds of heap objects, one that<BR>> > represents a range set by just its bounds. So I am TYPECASEing<BR>> > these already. It would be very convenient if I could just add<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > another<BR>> > alternative to the TYPECASE for in-word values.<BR>> ><BR>> > In another case, I need truly dynamically variable sized arrays of<BR>> > integers in [0..15], and the great majority are 7 elements or less,<BR>> > which would fit directly in the word, but I still the need full<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > generality<BR>> > to be available, so it's open arrays all the time, with three<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > additional<BR>> > words each.<BR>> ><BR>> > If you can pack a union of a pointer and an integer into a word and<BR>> > can separate them with runtime checks, then you can use the<BR>> > separated integer any way you want, with bit twiddling, type<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > conversions,<BR>> > LOOPHOLE, or whatever. That is what I am trying to get, not just<BR>> > Smalltalk-like integers.<BR>> > Note that Smalltalk has zero static typing, so only one internal<BR>> > representation must do for the union of all possible values in<BR>> > the language. In Modula-3, it would be very inconsistent with<BR>> > the language's philosophy to be this restricted.<BR>> >> Hmm, so your idea is to statically determine what type the references<BR>> >> can have if they are non-references. So you are thinking to put<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >> various<BR>> >> kinds of subranges into the "TAGGED" types. But you have to be<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >> able to<BR>> >> determine, statically, which subrange it is... am I understanding<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >> this<BR>> >> correctly?<BR>> >><BR>> ><BR>> > From the language, all I want is to be able to dynamically determine<BR>> > whether it is a true pointer to a heap object or a value stored<BR>> > directly in the word, while preserving the safety principles and<BR>> > the semantics of everything already there. So I want some new<BR>> > types, different from any existing types, that statically are known<BR>> > to hold this kind of valueset union and can be converted/assigned<BR>> > to a variable of existing type that is statically known to be either a<BR>> > pointer or an integer (but not both), with a suitable runtime check.<BR>> > It is also necessary to have a way to do this without risking a<SPAN class=EC_Apple-converted-space> </SPAN><BR>> > runtime<BR>> > error, if your code doesn't know yet which kind of value it has.<BR>> > Various ADT modules can take it from there.<BR>> >> Mika<BR>> >><BR>> >> "Rodney M. Bates" writes:<BR>> >><BR>> >>> Tony Hosking wrote:<BR>> >>><BR>> >>>> On 8 Apr 2009, at 11:49, Rodney M. Bates wrote:<BR>> >>>><BR>> >>>><BR>> >>>>> Mika Nystrom wrote:<BR>> >>>>><BR>> >>>>>> Hendrik, I think Tony's and my arguments that you can't break any<BR>> >>>>>> existing code by allowing the squirreling away of integers into<BR>> >>>>>> REFANYs are pretty solid. Pre-existing code simply can't do<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>>>> anything<BR>> >>>>>> useful with unrevealed REFANYs.<BR>> >>>>>><BR>> >>>>> This is only true of _unrevealed opaque subtypes_ of REFANY,<BR>> >>>>> not of REFANY itself. There is lots of existing code that uses<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>>> REFANY,<BR>> >>>>> and there, ISTYPE, NARROW, TYPECASE, and assigment can be and<BR>> >>>>> regularly are used on it. It is essential not to alter the<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>>> semantics there.<BR>> >>>>><BR>> >>>> Pre-existing code won't be able to do anything useful with tagged<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> REFANYs:<BR>> >>>><BR>> >>>> Suppose we have<BR>> >>>><BR>> >>>> VAR r: REFANY = SmallInteger.FromInt(0);<BR>> >>>><BR>> >>>> then<BR>> >>>><BR>> >>>> ISTYPE(r, REFANY) => TRUE<BR>> >>>> ISTYPE(r, T) => FALSE for any T # REFANY<BR>> >>>><BR>> >>>> Similarly, for TYPECASE, r will only trigger the REFANY branch.<BR>> >>>><BR>> >>>> NARROW(r, REFANY) => r<BR>> >>>> NARROW(r, T) => run-time error for any T #REFANY<BR>> >>>><BR>> >>>> VAR x: REFANY => assignment succeeds<BR>> >>>> VAR x: T := r => run-time error for any T # REFANY (because of<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> implicit NARROW)<BR>> >>>><BR>> >>> I think I am getting a bit lost in all the proposals, variations,<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> counterproposals, etc., but<BR>> >>><BR>> >> >from this argument I am inferring that your plan is that only<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >> variables<BR>> >>> declared REFANY<BR>> >>> and not any proper subtype of REFANY can ever have a value with a<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> tag bit set? Then<BR>> >>> the 4 narrowing operations, when and only when applied to an<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> expression of static<BR>> >>> type REFANY, would change to make a runtime check for a tag bit<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> and fail if it's set?<BR>> >>> It would take this to prevent a tagged value from getting into a<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> variable declared a<BR>> >>> proper subtype of REFANY, which can be dereferenced.<BR>> >>><BR>> >>> This would preclude making your abstract data type an opaque<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> subtype of REFANY,<BR>> >>> and would mean all supposedly unrelated ADT modules that used the<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> tag technique<BR>> >>> could be broken by client code that mixed up the REFANY values of<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> one of them with<BR>> >>> those of another. I consider this a definite breach of Modula-3's<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>> otherwise bulletproof<BR>> >>> type safety.<BR>> >>>> It is impossible to dereference an expression statically typed as<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> REFANY, so there is no need for a "tagged" check on dereference.<BR>> >>>> Because a tagged REFANY cannot be assigned to anything other than<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> something typed REFANY, it can never propagate to a place where<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> it can be dereferenced.<BR>> >>>><BR>> >>>><BR>> >>>>> Aside from actual semantic changes, I agree with Tony that we<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>>> should<BR>> >>>>> not burden any existing type with additional runtime work. Even<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>>> though<BR>> >>>>> I expect small objects to support big performance gains in certain<BR>> >>>>> important cases, non-tagged references will still greatly<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>>> predominate<BR>> >>>>> in most code. Create new type(s) for tagged references.<BR>> >>>>><BR>> >>>> I'm not sure that we are seeing any semantic changes at all. And<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> with Mika's definition of SmallInteger.T as a "boxed" INTEGER<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> object (actually it would be a subrange for values that fit into<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> BITSIZE(Word.T)-1 bits), it is essentially transparent. It just<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> happens to be a run-time optimization that unboxes the INTEGER<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> value.<BR>> >>>><BR>> >>>><BR>> >>>> I think I can implement the compiler and run-time support for<SPAN class=EC_Apple-converted-space> </SPAN><BR>> >>>> this very quickly.<BR>> >>>><BR>> >>>><BR>> >>>><BR>> >><BR>> >><BR>><SPAN class=EC_Apple-converted-space> </SPAN><BR></DIV></SPAN></BLOCKQUOTE></DIV><BR></body>
</html>