On Thu, May 7, 2009 at 4:13 PM, Jecel Assumpcao Jr jecel@merlintec.comwrote:
Bert Freudenberg wrote:
Yes. Keep 31-bit SmallIntegers, provide e.g. 24-bit immediate
characters.
Andreas wrote a thorough sketch of this scheme in 2006.
I would like to see this scheme get adopted. My own suggestion for the spare encoding (spare if the GC is changed, that is) was for unboxed 30 bit floats, but that seems to be unpopular and I guess I can live with float arrays instead.
Certainly immediate charaters are very important as we move away from ASCII, and I liked Andreas' suggestions of colors and short points as well. But I would be particularly interested in having an immediate encoding for symbols. You already have a global table from converting to/from strings, so I see no need to store anything in the symbols themselves. Having a trivial way to know that an object is a symbol without chasing a class pointer could make serializing/restoring objects a little faster.
This brings up an important point, which is what immediates are good for and what they're not (IMO). They are good for computation, but not without incurring other costs for compactness.
Yes one can, especially in a 64-bit VM, imagine e.g. a 7 character immediate Symbol, but it won't save you that much because by definition the symbols that become immediate are the smallest, and it will have additional costs, another class in the image, different code for creating immediate symbols from strings, complications in all string comparison code (e.g. the string comparison primitives) to cope with immediate symbols. So computationally immediate symbols are slower and add complication.
Compare that to e.g. 61-bit immediate floats in a 64-bit VM where the cost (an additional class in the image and a set of primitives) is repaid by substantially faster float arithmetic.
IMO, in general use immedates for computational objects where computation is performed on the immediate bit pattern and instantiation rates are high. This applies to integers characters and floats. Do not use them for atoms such as nil, false true, the symbols, etc. These are perfectly fine as ordinary objects. Adding them as immediates complicates (bloats and slows down) the immediate/non-immediate test that is the highest dynamic frequency operation in the VM (e.g. one per send), accessing the class etc.
Short points and compact colours might make sense in a very graphical environment, but the cost of the blits would I think far outweigh the cost of the point & colour manipulation so the advantages would get lost in the noise.
So for me I'm only interested in SmallInteger, SmallFloat & Character, and keeping the immediate test as lean as possible.
One thing I find difficult with Andreas' proposal is the use of 31-bit SmallIntegers instead of 30-bit SmallIntegers because it complicates the immediate test. One can't simply use oop bitAnd: 3 to determine the tag value because both 2r01 and 2r11 are SmallIntegers; instead one has to use (oop bitAnd: 1) ifTrue: [1] ifFalse: [oop bitAnd: 3].
The isImmediate test is fine: isImmediate: oop ^(oop bitAnd: 3) ~= 0 or, if 0 is being used as the SmallInteger tag (a la V8), e.g. isImmediate: oop ^(oop bitAnd: 3) ~= 3 bit the "does this oop have the immediate pattern foo?" test is slow and this is the test that is in in-line caches on every send: oop: oop hasTag: pattern | tagAndLSB | tagAndLSB := oop bitAnd: 3. ^pattern = 2 ifTrue: [tagAndLSB = 2] ifFalse: [(tagAndLSB bitAnd: 1) ~= 0] or some such. Its much nicer if it is just oop: oop hasTag: pattern ^pattern = (oop bitAnd: 3)
I'm told that having 31-bit and opposed to 30-bit SmallIntegers is a bug advantage but I remain to be convinced; VW has always had 30-bit SmallIntegers and seems none the worse for it.
-- Jecel
2009/5/8 Eliot Miranda eliot.miranda@gmail.com:
On Thu, May 7, 2009 at 4:13 PM, Jecel Assumpcao Jr jecel@merlintec.com wrote:
Bert Freudenberg wrote:
Yes. Keep 31-bit SmallIntegers, provide e.g. 24-bit immediate characters. Andreas wrote a thorough sketch of this scheme in 2006.
I would like to see this scheme get adopted. My own suggestion for the spare encoding (spare if the GC is changed, that is) was for unboxed 30 bit floats, but that seems to be unpopular and I guess I can live with float arrays instead.
Certainly immediate charaters are very important as we move away from ASCII, and I liked Andreas' suggestions of colors and short points as well. But I would be particularly interested in having an immediate encoding for symbols. You already have a global table from converting to/from strings, so I see no need to store anything in the symbols themselves. Having a trivial way to know that an object is a symbol without chasing a class pointer could make serializing/restoring objects a little faster.
This brings up an important point, which is what immediates are good for and what they're not (IMO). They are good for computation, but not without incurring other costs for compactness. Yes one can, especially in a 64-bit VM, imagine e.g. a 7 character immediate Symbol, but it won't save you that much because by definition the symbols that become immediate are the smallest, and it will have additional costs, another class in the image, different code for creating immediate symbols from strings, complications in all string comparison code (e.g. the string comparison primitives) to cope with immediate symbols. So computationally immediate symbols are slower and add complication. Compare that to e.g. 61-bit immediate floats in a 64-bit VM where the cost (an additional class in the image and a set of primitives) is repaid by substantially faster float arithmetic. IMO, in general use immedates for computational objects where computation is performed on the immediate bit pattern and instantiation rates are high. This applies to integers characters and floats. Do not use them for atoms such as nil, false true, the symbols, etc. These are perfectly fine as ordinary objects. Adding them as immediates complicates (bloats and slows down) the immediate/non-immediate test that is the highest dynamic frequency operation in the VM (e.g. one per send), accessing the class etc. Short points and compact colours might make sense in a very graphical environment, but the cost of the blits would I think far outweigh the cost of the point & colour manipulation so the advantages would get lost in the noise. So for me I'm only interested in SmallInteger, SmallFloat & Character, and keeping the immediate test as lean as possible. One thing I find difficult with Andreas' proposal is the use of 31-bit SmallIntegers instead of 30-bit SmallIntegers because it complicates the immediate test. One can't simply use oop bitAnd: 3 to determine the tag value because both 2r01 and 2r11 are SmallIntegers; instead one has to use (oop bitAnd: 1) ifTrue: [1] ifFalse: [oop bitAnd: 3]. The isImmediate test is fine: isImmediate: oop ^(oop bitAnd: 3) ~= 0 or, if 0 is being used as the SmallInteger tag (a la V8), e.g. isImmediate: oop ^(oop bitAnd: 3) ~= 3 bit the "does this oop have the immediate pattern foo?" test is slow and this is the test that is in in-line caches on every send: oop: oop hasTag: pattern | tagAndLSB | tagAndLSB := oop bitAnd: 3. ^pattern = 2 ifTrue: [tagAndLSB = 2] ifFalse: [(tagAndLSB bitAnd: 1) ~= 0] or some such. Its much nicer if it is just oop: oop hasTag: pattern ^pattern = (oop bitAnd: 3)
I'm told that having 31-bit and opposed to 30-bit SmallIntegers is a bug advantage but I remain to be convinced; VW has always had 30-bit SmallIntegers and seems none the worse for it.
Eliot, i encourage you to write the Cog in such way, that it would be very easy to replace/change the tagging rules. Then, you can bench the performance and choose best alternative.
-- Jecel
On Thu, May 7, 2009 at 4:56 PM, Igor Stasenko siguctua@gmail.com wrote:
2009/5/8 Eliot Miranda eliot.miranda@gmail.com:
On Thu, May 7, 2009 at 4:13 PM, Jecel Assumpcao Jr jecel@merlintec.com
wrote:
Bert Freudenberg wrote:
Yes. Keep 31-bit SmallIntegers, provide e.g. 24-bit immediate
characters.
Andreas wrote a thorough sketch of this scheme in 2006.
I would like to see this scheme get adopted. My own suggestion for the spare encoding (spare if the GC is changed, that is) was for unboxed 30 bit floats, but that seems to be unpopular and I guess I can live with float arrays instead.
Certainly immediate charaters are very important as we move away from ASCII, and I liked Andreas' suggestions of colors and short points as well. But I would be particularly interested in having an immediate encoding for symbols. You already have a global table from converting to/from strings, so I see no need to store anything in the symbols themselves. Having a trivial way to know that an object is a symbol without chasing a class pointer could make serializing/restoring objects a little faster.
This brings up an important point, which is what immediates are good for
and what they're not (IMO). They are good for computation, but not without incurring other costs for compactness.
Yes one can, especially in a 64-bit VM, imagine e.g. a 7 character
immediate Symbol, but it won't save you that much because by definition the symbols that become immediate are the smallest, and it will have additional costs, another class in the image, different code for creating immediate symbols from strings, complications in all string comparison code (e.g. the string comparison primitives) to cope with immediate symbols. So computationally immediate symbols are slower and add complication.
Compare that to e.g. 61-bit immediate floats in a 64-bit VM where the
cost (an additional class in the image and a set of primitives) is repaid by substantially faster float arithmetic.
IMO, in general use immedates for computational objects where computation
is performed on the immediate bit pattern and instantiation rates are high. This applies to integers characters and floats. Do not use them for atoms such as nil, false true, the symbols, etc. These are perfectly fine as ordinary objects. Adding them as immediates complicates (bloats and slows down) the immediate/non-immediate test that is the highest dynamic frequency operation in the VM (e.g. one per send), accessing the class etc.
Short points and compact colours might make sense in a very graphical
environment, but the cost of the blits would I think far outweigh the cost of the point & colour manipulation so the advantages would get lost in the noise.
So for me I'm only interested in SmallInteger, SmallFloat & Character,
and keeping the immediate test as lean as possible.
One thing I find difficult with Andreas' proposal is the use of 31-bit
SmallIntegers instead of 30-bit SmallIntegers because it complicates the immediate test. One can't simply use oop bitAnd: 3 to determine the tag value because both 2r01 and 2r11 are SmallIntegers; instead one has to use (oop bitAnd: 1) ifTrue: [1] ifFalse: [oop bitAnd: 3].
The isImmediate test is fine: isImmediate: oop ^(oop bitAnd: 3) ~= 0 or, if 0 is being used as the SmallInteger tag (a la V8), e.g. isImmediate: oop ^(oop bitAnd: 3) ~= 3 bit the "does this oop have the immediate pattern foo?" test is slow and
this is the test that is in in-line caches on every send:
oop: oop hasTag: pattern | tagAndLSB | tagAndLSB := oop bitAnd: 3. ^pattern = 2 ifTrue: [tagAndLSB = 2] ifFalse: [(tagAndLSB bitAnd:
- ~= 0]
or some such. Its much nicer if it is just oop: oop hasTag: pattern ^pattern = (oop bitAnd: 3)
I'm told that having 31-bit and opposed to 30-bit SmallIntegers is a bug
advantage but I remain to be convinced; VW has always had 30-bit SmallIntegers and seems none the worse for it.
Eliot, i encourage you to write the Cog in such way, that it would be very easy to replace/change the tagging rules. Then, you can bench the performance and choose best alternative.
I have done just this :) There is an abstraction of the object representation "objectRepresentation" to which the JIT defers whenever accessing objects. So e.g.
genPrimitiveSubtract "Stack looks like receiver (also in ResultReceiverReg) arg return address" | jumpNotSI jumpOvfl | <var: #jumpNotSI type: #'AbstractInstruction *'> <var: #jumpOvfl type: #'AbstractInstruction *'> self MoveMw: BytesPerWord r: SPReg R: TempReg. self MoveR: TempReg R: ClassReg.
jumpNotSI *:=* objectRepresentation genJumpNotSmallIntegerInScratchReg:
TempReg. self MoveR: ReceiverResultReg R: TempReg. self SubR: ClassReg R: TempReg. jumpOvfl *:=* self JumpOverflow: 0.
objectRepresentation genAddSmallIntegerTagsTo: TempReg.
self MoveR: TempReg R: ReceiverResultReg. self flag: 'currently caller pushes result'. self RetN: BytesPerWord * 2. jumpOvfl jmpTarget: (jumpNotSI jmpTarget: self Label). ^0
objectRepresentation takes care of slot access, tagging/detagging, class access and in-line cache tag omparison. In the current VM an in-line cache tag is either the SmallInteger tag bit for a SmallInteger or the compact class index * 4 for an instance with a compact class or the class. The JIT knows nothing of this scheme. So I should be able to create a new object representation without affecting it. But nothing works until it's tested ;)
best Eliot
Sorry about the wrong attribution - Celeste makes a big mess of all of Eliot's emails and most replies to those emails. Unfortunately, fixing this is not currently near the top of my "to do" list so I'll just have to deal with this for a few more months.
I totally agree about the value of immediates being to speed up computations by avoiding allocations. My idea for symbols was not to avoid the costly mapping of strings to new instances but rather speed up class lookup a little bit. This wouldn't help us now, but for a future modular Squeak that would be loading and unloading object graphs all the time, this could make a difference.
Like VisualWorks, Self uses 30 bit integers with a 00 tag (which makes detagging/retagging unnecessary for addition, subtraction and bitwise logical operations). The other tag values represent 30 bit floats, object pointers (you always use a constant offset with these anyway, so the detagging can be built into that constant) and object headers. The memory is divided into segments (generations) and each segment stores tagged data from the bottom and binary data from the top. ByteVectors are normal tagged objects with a SmallInteger pointing to the actual bytes.
The idea of a tag pattern for object headers is that you can "flatten" the memory scanning operations. You just scan from top to the limit until you found what you were looking for and then back up to the previous header to see what object contains that oop. This can be many times faster than a objects do: [ :obj | obj fieldsDo: [ :oop | ....]] nested loop.
For my old RISC42 design I came up with the idea of having the top two bits the same to indicate SmallIntegers. This is hard to check in software, but in hardware is just a two input XOR gate. This allows you to avoid detagging not only for the operations I mentioned above, but also for multiplies, divides, left shift and signed right shift too. A few weeks ago I found out that the old Swamp Smalltalk computer from 1986 used exactly the same scheme (the two patterns where the top two bits were different were used for oops and for pointers to context objects).
-- Jecel
Eliot Miranda wrote:
I'm told that having 31-bit and opposed to 30-bit SmallIntegers is a bug advantage but I remain to be convinced; VW has always had 30-bit SmallIntegers and seems none the worse for it.
I was going to make a contrary argument, except when I was doing the math it didn't go my way ;-) Here is why: Obviously, when having computations that can overflow into large ints the performance difference is huge (factors of 30-100). However, most algorithms that we care about (like crypto) is strictly 32 bit where even with 31 bit SmallIntegers we go LargeInt half the time. Consequently the statistical difference between 31 and 30 bit for those algorithms should be in the range of 50% which, although certainly not insignificant, is nothing compared to when you can run the entire algorithm as SmallInteger computations.
Cheers, - Andreas
On Thu, May 7, 2009 at 7:27 PM, David T. Lewis lewis@mail.msen.com wrote:
On Thu, May 07, 2009 at 04:39:58PM -0700, Eliot Miranda wrote:
I'm told that having 31-bit and opposed to 30-bit SmallIntegers is a bug advantage but I remain to be convinced
I presume a freudian slip in the choice of adjectives here ;)
<blush> :)
Dave
vm-dev@lists.squeakfoundation.org