[Vm-dev] Immediates

[Eliot Miranda]

On Thu, May 7, 2009 at 4:56 PM, Igor Stasenko <siguctua at gmail.com> wrote:

>
> 2009/5/8 Eliot Miranda <eliot.miranda at gmail.com>:
> >
> >
> >
> > On Thu, May 7, 2009 at 4:13 PM, Jecel Assumpcao Jr <jecel at 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.


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20090507/646e2320/attachment-0001.htm