30 bit unboxed floats
Locked
12
12
 
|
We have had several discussions about the tags in Squeak. xxxxxx1 is a
SmallInteger and xxxxxx00 is an object pointer, but xxxxxx10 is not generally used. In one of the previous discussions somebody did mention a very obscure case in which this is actually used, but I can't find this email right now and don't remember the details. I do remember that at the time it seemed to me that it wouldn't be hard to change this to free up the 10 tag for some other use. The most interesting use, in my opinion, would be to have unboxed floating point numbers. A very common reaction here to this is that we will all be moving to 64 bits anyway so it is not worth the trouble to make this change. I might have agreed a few years ago, but today it looks like we will have to deal with 32 bit Squeak for quite a while yet. And with 4.2 introducing some important image format changes anyway, this might be the right time to revisit this issue. Boxed floats have the disadvantage of requiring an object allocation for every operation. Their great advantage is being 64 bits, even in 32 bit images. The unboxed floats would have to be 30 bits, not even 32 bits. So the fraction size goes from 53 bits to only 21. And while they would mostly speed things up, the current tag tests would have to go from two alternatives to three and that would slow them down. The extra tests would be in what is already a slow path anyway, so it wouldn't hurt as much as it would initially seem. Does anybody have any data related to this or any opinions? -- Jecel |
|
|
On Mon, Oct 18, 2010 at 11:31 AM, Jecel Assumpcao Jr. <[hidden email]> wrote: We have had several discussions about the tags in Squeak. xxxxxx1 is a I think immediate characters are much more generally useful, especially considering unicode. The current implementation of only codes 0 to 255 being == is error-prone. The problem 30 bit floats have is that they're not a useful subset of Float. A 60-bit immediate float is a different beast altogether. You really need the number of bits to be sihnificanty greater than the size of the mantissa. With 30 bits it is still 23 bits short.
2¢ Eliot
|
|
|
On Mon, Oct 18, 2010 at 1:38 PM, Eliot Miranda <[hidden email]> wrote:
> I think immediate characters are much more generally useful, especially > considering unicode. The current implementation of only codes 0 to 255 > being == is error-prone. I enthusiastically agree. I think string handling in Squeak is pretty weak, and having efficient Characters would provide a solid basis for improving it. Colin |
|
|
In reply to this post by Eliot Miranda-2
On Mon, 18 Oct 2010, Eliot Miranda wrote:
> On Mon, Oct 18, 2010 at 11:31 AM, Jecel Assumpcao Jr. > <[hidden email]>wrote: > >> We have had several discussions about the tags in Squeak. xxxxxx1 is a >> SmallInteger and xxxxxx00 is an object pointer, but xxxxxx10 is not >> generally used. In one of the previous discussions somebody did mention >> a very obscure case in which this is actually used, but I can't find >> this email right now and don't remember the details. I do remember that >> at the time it seemed to me that it wouldn't be hard to change this to >> free up the 10 tag for some other use. >> >> The most interesting use, in my opinion, would be to have unboxed >> floating point numbers. A very common reaction here to this is that we >> will all be moving to 64 bits anyway so it is not worth the trouble to >> make this change. I might have agreed a few years ago, but today it >> looks like we will have to deal with 32 bit Squeak for quite a while >> yet. And with 4.2 introducing some important image format changes >> anyway, this might be the right time to revisit this issue. >> >> Boxed floats have the disadvantage of requiring an object allocation for >> every operation. Their great advantage is being 64 bits, even in 32 bit >> images. The unboxed floats would have to be 30 bits, not even 32 bits. >> So the fraction size goes from 53 bits to only 21. And while they would >> mostly speed things up, the current tag tests would have to go from two >> alternatives to three and that would slow them down. The extra tests >> would be in what is already a slow path anyway, so it wouldn't hurt as >> much as it would initially seem. >> >> Does anybody have any data related to this or any opinions? >> > > I think immediate characters are much more generally useful, especially > considering unicode. The current implementation of only codes 0 to 255 > being == is error-prone. The problem 30 bit floats have is that they're not > a useful subset of Float. A 60-bit immediate float is a different beast > altogether. You really need the number of bits to be sihnificanty greater > than the size of the mantissa. With 30 bits it is still 23 bits short. > > 2? > Eliot +1 Levente > >> >> -- Jecel >> >> >> > |
|
|
In reply to this post by Colin Putney-3
i'd say, depending for what purpose you using a language and
applications implemented in it (float math, or web server), the choice between chars/immediate floats are not obvious. My own opinion, it should be floats. Because characters in fact is nothing more than integer number , identifying a code point in some encoding. And in general, this means, that with proper design, one could avoid using encapsulated integers (which Character are), but instead use integer values directly. So, there are many places, where impact of boxing characters on performance could be minimized. Because one could manipulate with (sub)strings, instead of individual characters. In contrast, floats having much less potential for optimization like that. Of course , we having a FloatArray-s and stuff like that, but once you writing down a code to evaluate some formula, it going to deal with a single floating-point value(s). This is what you never doing with characters , writing formulae... :) On 18 October 2010 23:49, Colin Putney <[hidden email]> wrote: > On Mon, Oct 18, 2010 at 1:38 PM, Eliot Miranda <[hidden email]> wrote: > >> I think immediate characters are much more generally useful, especially >> considering unicode. The current implementation of only codes 0 to 255 >> being == is error-prone. > > I enthusiastically agree. I think string handling in Squeak is pretty > weak, and having efficient Characters would provide a solid basis for > improving it. > > Colin > > -- Best regards, Igor Stasenko AKA sig. |
|
|
Oh.. sorry.. i forgot to say that it makes no sense for 32-bit systems.
Eliot is right by saying that 27-bit floats are useless.. As for characters, i also don't see it worth the effort (especially if we take into account a slowdown for all integer operations, since we have to pick from 3 tag variants instead of 2) -- Best regards, Igor Stasenko AKA sig. |
|
|
In reply to this post by Igor Stasenko
On 10/18/2010 2:09 PM, Igor Stasenko wrote:
> My own opinion, it should be floats. Because characters in fact is > nothing more than integer number , identifying a code point in > some encoding. And in general, this means, that with proper design, > one could avoid using encapsulated integers (which Character are), but > instead use integer values directly. Uhm ... Integer>>isLowercase? I don't think so. The only realistic alternative in my opinion is to use Strings exclusively (i.e., Characters being strings of length 1; potentially even a 'special' subclass of String). But I'm not a particularly big fan of that design either. Cheers, - Andreas > So, there are many places, where impact of boxing characters on > performance could be minimized. Because one could manipulate with > (sub)strings, instead of individual characters. > > In contrast, floats having much less potential for optimization like > that. Of course , we having a FloatArray-s and stuff like that, > but once you writing down a code to evaluate some formula, it going to > deal with a single floating-point value(s). > This is what you never doing with characters , writing formulae... :) > > > On 18 October 2010 23:49, Colin Putney<[hidden email]> wrote: >> On Mon, Oct 18, 2010 at 1:38 PM, Eliot Miranda<[hidden email]> wrote: >> >>> I think immediate characters are much more generally useful, especially >>> considering unicode. The current implementation of only codes 0 to 255 >>> being == is error-prone. >> >> I enthusiastically agree. I think string handling in Squeak is pretty >> weak, and having efficient Characters would provide a solid basis for >> improving it. >> >> Colin >> >> > > > |
|
|
On 19 October 2010 00:24, Andreas Raab <[hidden email]> wrote:
> On 10/18/2010 2:09 PM, Igor Stasenko wrote: >> >> My own opinion, it should be floats. Because characters in fact is >> nothing more than integer number , identifying a code point in >> some encoding. And in general, this means, that with proper design, >> one could avoid using encapsulated integers (which Character are), but >> instead use integer values directly. > > Uhm ... Integer>>isLowercase? I don't think so. The only realistic > alternative in my opinion is to use Strings exclusively (i.e., Characters > being strings of length 1; potentially even a 'special' subclass of String). > But I'm not a particularly big fan of that design either. > No, i was talking about conversion layers, like reading file(s)/streams. They should be always a binary, so stuff like utf8 encoder/decoder will deal with integer values. In this way, one could really avoid dealing with individual character(s), and only topmost layers will have to produce strings as output. We might require some additional primitives to speed things up. Like in addition of converting ByteArray -> ByteString also provide a primitive, for converting Array -> WideString, or WordArray->WideString. Again, when rendering text, you turning a character(s) into an integer(s) to look-up a glyph in some font. So, it also could be done in more straightforward way to avoid boxing/unboxing overhead. What i meant to say, that there are definitely much more space for improvement to handle Characters in a way to minimize the impact of boxing/unboxing, comparing to what could be done with boxed floats. It simply because the way how they are used. > Cheers, > - Andreas > >> So, there are many places, where impact of boxing characters on >> performance could be minimized. Because one could manipulate with >> (sub)strings, instead of individual characters. >> >> In contrast, floats having much less potential for optimization like >> that. Of course , we having a FloatArray-s and stuff like that, >> but once you writing down a code to evaluate some formula, it going to >> deal with a single floating-point value(s). >> This is what you never doing with characters , writing formulae... :) >> >> >> On 18 October 2010 23:49, Colin Putney<[hidden email]> wrote: >>> >>> On Mon, Oct 18, 2010 at 1:38 PM, Eliot Miranda<[hidden email]> >>> wrote: >>> >>>> I think immediate characters are much more generally useful, especially >>>> considering unicode. The current implementation of only codes 0 to 255 >>>> being == is error-prone. >>> >>> I enthusiastically agree. I think string handling in Squeak is pretty >>> weak, and having efficient Characters would provide a solid basis for >>> improving it. >>> >>> Colin >>> >>> >> >> >> > > > -- Best regards, Igor Stasenko AKA sig. |
|
|
In reply to this post by Jecel Assumpcao Jr
On 10/18/10 10:31 , Jecel Assumpcao Jr. wrote:
> We have had several discussions about the tags in Squeak. xxxxxx1 is a > SmallInteger and xxxxxx00 is an object pointer, but xxxxxx10 is not > generally used. How does the mark and sweep GC handle mark stack overflows? Is there a bit in the object header for that? Andres. |
|
|
On Mon, Oct 18, 2010 at 2:50 PM, Andres Valloud <[hidden email]> wrote:
The Squeak GC uses a pointer-reversal algorithm for marking and so is immune to mark stack overflow.
cheers, Eliot
|
|
|
In reply to this post by Jecel Assumpcao Jr
On Mon, Oct 18, 2010 at 06:31:15PM -0300, Jecel Assumpcao Jr. wrote:
> We have had several discussions about the tags in Squeak. xxxxxx1 is a > SmallInteger and xxxxxx00 is an object pointer, but xxxxxx10 is not > generally used. In one of the previous discussions somebody did mention > a very obscure case in which this is actually used, but I can't find > this email right now and don't remember the details. I do remember that > at the time it seemed to me that it wouldn't be hard to change this to > free up the 10 tag for some other use. There is no shortage of bits to use for flagging immediate values. Treating an object memory pointer as a (signed) sqInt of size 32 or 64, then for a 32-bit object memory the valid pointer values are 0, 4, 8, 12 ... through end of memory. In the forseeable future, object memory sizes of more than one or two GB are of no practical use. One or more high order bits in the object memory pointer space are available for other uses. Thus: if pointer bitAt: 1 is set, then the pointer is an immediate integer, else if pointer < 0, then the pointer is an immediate float, else if pointer bitAt: 2 is set, then the pointer is an immediate character. For immediate floats in a 32-bit object memory, bits 2 through 31 are the float data. For a 64-bit object memory, bits 2 through 63 contain the float data. For immediate characters, bits 3 through 31 are available. Assuming tables of 16-bit characters this could be further segmented into multiple character tables, presumably with some image-side mapping support. Dave |
|
|
On Mon, Oct 18, 2010 at 4:24 PM, David T. Lewis <[hidden email]> wrote:
> In the forseeable future, object memory sizes of more than one or two GB are of no practical use. Why do you say that? Colin |
|
|
On 19 October 2010 02:29, Colin Putney <[hidden email]> wrote:
> On Mon, Oct 18, 2010 at 4:24 PM, David T. Lewis <[hidden email]> wrote: > >> In the forseeable future, object memory sizes of more than one or two GB are of no practical use. > > Why do you say that? > Because there is really something wrong with your data model, when you need so much resident memory, which you can't page/swap using disk IO :) > Colin > > -- Best regards, Igor Stasenko AKA sig. |
|
|
In reply to this post by Colin Putney-3
On 18.10.2010, at 13:49, Colin Putney wrote:
> On Mon, Oct 18, 2010 at 1:38 PM, Eliot Miranda <[hidden email]> wrote: > >> I think immediate characters are much more generally useful, especially >> considering unicode. The current implementation of only codes 0 to 255 >> being == is error-prone. > > I enthusiastically agree. I think string handling in Squeak is pretty > weak, and having efficient Characters would provide a solid basis for > improving it. Disagree. You don't want to be manipulating single characters if speed matters. Much better to add primitive support to speed up WideStrings. Also, adding more immediate objects will slow down the system as a whole. I remember changing the tag bit check in the early days of Squeak did have a performance impact. Whether new immediates would result in a net speed win remains to be seen. - Bert - |
|
|
On Mon, Oct 18, 2010 at 4:41 PM, Bert Freudenberg <[hidden email]> wrote:
But there are many places in the system that deal with characters. They are an extremely common datatype in the compiler, in the UI.
Also, adding more immediate objects will slow down the system as a whole. I remember changing the tag bit check in the early days of Squeak did have a performance impact. Whether new immediates would result in a net speed win remains to be seen. It won't slow the system down, and I speak form VW experience where we had either immediate characters and integers (32-bit) or immediate characters integers and floats (64-bits). You're basically talking about the cost of masking by 1 or masking by 3 (or 7 in 64-bits) and on last century's machines that could make a difference. But on contemporary hardware it makes no difference; only memory access makes a difference and adding immediate characters can only reduce memory access. Therefore it will likely speed-up the system, but will certainly not slow it down.
|
|
|
In reply to this post by Colin Putney-3
On Mon, Oct 18, 2010 at 04:29:54PM -0700, Colin Putney wrote:
> On Mon, Oct 18, 2010 at 4:24 PM, David T. Lewis <[hidden email]> wrote: > > > In the forseeable future, object memory sizes of more than one or two GB are of no practical use. > > Why do you say that? > Well, basically the garbage collector has a lot of work to do if it's managing a lot of memory. Try making a large image and judge for yourself. Dave |
|
|
On Mon, Oct 18, 2010 at 4:50 PM, David T. Lewis <[hidden email]> wrote:
Yes, but some of us are about to start work on a better GC :) VW has had users that have been using > 2Gb heaps for almost a decade. I should have a new GC running next year and it'd /better/ work well with > 2Gb heaps.
BTW, tags belong in the least significant bits because a) testing them involves smaller manifest constants and so smaller code size (*) and b) aligning objects on larger boundaries can have efficiency benefits (e.g. 64 bit writes to initialize objects) and that has the side-effect of making more tag bits available.
(*) yes testing the msb is cheap iff oop size == word size, but that's only 1 bit that's cheap to test best, Eliot
|
|
|
In reply to this post by Bert Freudenberg
Can't help but remind people of this little post I did a couple years
back on how to add new immediate types: http://lists.squeakfoundation.org/pipermail/vm-dev/2006-January/000429.html Cheers, - Andreas On 10/18/2010 4:41 PM, Bert Freudenberg wrote: > On 18.10.2010, at 13:49, Colin Putney wrote: > >> On Mon, Oct 18, 2010 at 1:38 PM, Eliot Miranda<[hidden email]> wrote: >> >>> I think immediate characters are much more generally useful, especially >>> considering unicode. The current implementation of only codes 0 to 255 >>> being == is error-prone. >> >> I enthusiastically agree. I think string handling in Squeak is pretty >> weak, and having efficient Characters would provide a solid basis for >> improving it. > > Disagree. > > You don't want to be manipulating single characters if speed matters. Much better to add primitive support to speed up WideStrings. > > Also, adding more immediate objects will slow down the system as a whole. I remember changing the tag bit check in the early days of Squeak did have a performance impact. Whether new immediates would result in a net speed win remains to be seen. > > - Bert - > > > |
|
|
HeaderTypeGC refers to a bit in the object header, not to a bit in an
object memory pointer. The usage of this bit in the object header does not in any way conflict with bit assignment for object memory pointers. Dave On Mon, Oct 18, 2010 at 05:08:56PM -0700, Andreas Raab wrote: > Can't help but remind people of this little post I did a couple years > back on how to add new immediate types: > > http://lists.squeakfoundation.org/pipermail/vm-dev/2006-January/000429.html > > Cheers, > - Andreas > > > On 10/18/2010 4:41 PM, Bert Freudenberg wrote: > >On 18.10.2010, at 13:49, Colin Putney wrote: > > > >>On Mon, Oct 18, 2010 at 1:38 PM, Eliot Miranda<[hidden email]> > >>wrote: > >> > >>>I think immediate characters are much more generally useful, especially > >>>considering unicode. The current implementation of only codes 0 to 255 > >>>being == is error-prone. > >> > >>I enthusiastically agree. I think string handling in Squeak is pretty > >>weak, and having efficient Characters would provide a solid basis for > >>improving it. > > > >Disagree. > > > >You don't want to be manipulating single characters if speed matters. Much > >better to add primitive support to speed up WideStrings. > > > >Also, adding more immediate objects will slow down the system as a whole. > >I remember changing the tag bit check in the early days of Squeak did have > >a performance impact. Whether new immediates would result in a net speed > >win remains to be seen. > > > >- Bert - > > > > > > > |
|
|
In reply to this post by Eliot Miranda-2
I looked into this and from my quick impression, all pointers in
reachable object bodies will be written to twice by the algorithm. However, a stack approach would only write such pointers once (copying them from the object into the mark stack). Doesn't that imply that the pointer reversal algorithm is more memory intensive than a stack approach? On 10/18/10 14:55 , Eliot Miranda wrote: > > > On Mon, Oct 18, 2010 at 2:50 PM, Andres Valloud > <[hidden email] > <mailto:[hidden email]>> wrote: > > On 10/18/10 10:31 , Jecel Assumpcao Jr. wrote: > > We have had several discussions about the tags in Squeak. > xxxxxx1 is a > SmallInteger and xxxxxx00 is an object pointer, but xxxxxx10 is not > generally used. > > > How does the mark and sweep GC handle mark stack overflows? Is > there a bit in the object header for that? > > > The Squeak GC uses a pointer-reversal algorithm for marking and so is > immune to mark stack overflow. > > cheers, > Eliot > > > Andres. > > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |