Vm-dev May 2009

vm-dev@lists.squeakfoundation.org

16 participants
24 discussions

Re: [Vm-dev] stack vm questions
by Igor Stasenko 14 May '09

14 May '09

2009/5/14 Jecel Assumpcao Jr <jecel(a)merlintec.com>: > > Thanks Eliot and Igor for your comments! > > Eliot is right that what Igor wrote is a good way to do a JIT but the > problem is that my hardware is essentially an interpreter and must deal > at runtime with expressions that the JIT would optimize away. > yes, i was proposed it for JIT only. For bytecode interpteter such separation really could be much less effective. What is bad, that to test the idea (how much its more [not]effective comparing to single stack) it requires a huge implementation effort. So, its a bit risky spend many hours changing the code generator & data formats only to discover that in practice, it gives much less significant benefits than expected :) > My design is described in: > > http://www.squeakphone.com:8203/seaside/pier/siliconsqueak/details > > What is missing from that description is what the control registers (x0 > to x31) do, and that depends on the stack organization. Certainly it is > possible to have three registers as Eliot suggested. A separate control > stack is not only used on Forth processors but was also popular in Lisp > Machine designs. > > Registers t0 to t29 are really implemented through a small amount of > hardware as a range of words in the stack cache. Having to split this > set differently for each method would make the hardware larger and > slower. With a separate control stack the mapping is really simple. > > About the JIT having to use call which pushes the PC, that is not true > on RISC processors. But I suppose the focus for Cog is making Squeak > fast on the x86. > >> There's a tension between implementing what the current compiler >> produces and implementing what the instruction set defines. For >> example should one assume arguments are never written to? I lean >> on the side of implementing the instruction set. > > That is specially a good idea if the same VM ends up being used for > other languages like Newspeak. Certainly the Java VM runs many languages > that the original designers never expected. > >> Yes. In the JIT an interpreted frame needs an extra field to hold >> the saved bytecode instruction pointer when an interpreted frame >> calls a machine code frame because the return address is the "return >> to interpreter trampoline" pc. There is no flag word in a machine >> code frame. So machine code frames save one word w.r.t. the >> stack vm and interpreted frames gain a word. But most frames >> are machine code ones so most of the time one is saving space. > > Ok, so the JIT VM will still have an interpreter. Self originally didn't > have one but most of the effort that David Ungar put into the project > when it was restarted was making it more interpreter friendly. The > bytecodes became very similar to the ones in Little Smalltalk, for > example. > > Will images be compatible between the JIT VM and the Stack VM? Or do you > expect the latter to not be used anymore once the JIT is available? I > had originally understood that the Stack VM would be compatible with > older images (since you divorce all frames on save and remarry them on > reload) but I had missed the detail of the different bytecodes for > variable instance access in the case of Context objects. > >> I guess that in hardware you can create an instruction that will >> load a descriptor register as part of the return sequence in parallel >> with restoring the frame pointer and method so one would never >> indirect through the frame pointer to fetch the flags word; instead >> it would be part of the register state. But that's an extremely >> uneducated guess :) > > Well, I am trying to avoid having a flags word even though in hardware > it is so easy to have any size fields that you might want. I can check > if context == nil very efficiently. For methods, t0 is the same value as > the "self" register (x4, for example) while for blocks it is different. > And with three pointers (fp, sp and control pointer) I shouldn't need to > keep track of the number of arguments. > >> Jecel can also design the machine to avoid taking interrupts on >> the operand stack and provide a separate interrupt stack. > > Hmmm... it has been a while since I designed hardware with interrupts, > but have normally used Alto style coroutines instead. The stack cache is > divided up into 32 word blocks and can hold parts of stacks from several > threads at once. Checking for overflow/underflow only needs to happen > when the stack pointer moves from one block to a different one (and even > then, only in certain cases which aren't too common). An interesting > feature of this scheme is that only 5 bit adders are needed (which are > much faster than 16 or 32 bit adders, for example. Wide adders could > reduce the clock speed or make the operation take an extra clock). > Another detail is that having operand or control frames split among two > stack pages is no problem at all. > > address of tN in the stack cache: > > raddr := fp[4:0] + N. > scaddr := (raddr[5] ? tHigh : tLow) , raddr[4:0]. > > When fp[5] changes value, then tLow := tHigh and tHigh := head of free > block list (if fp was going up). If there are no free blocks, then some > have to be flushed to their stack pages in main memory. When going down, > tLow is loaded from a linked list, which might have to be extended by > loading blocks from stack pages. With a 4KB stack cache, for example, > there are 32 blocks with 32 words each and so block 0 can dedicate a > word for each of the other 31 blocks. The bottom 7 bits of that word > (only 5 actually needed, but it is nice to have a little room to grow) > can form the "previous" linked list (tHigh and tLow would also be 5 bits > wide) while the remaining bits can hold the block's address in main > memory. > > This might seem far more complicated than a split arg/temp frame and it > certainly would be if implemented in software. In hardware, it is mostly > wires, a multiplexer and a small adder. > > -- Jecel > > -- Best regards, Igor Stasenko AKA sig.

1 0

Re: [Vm-dev] stack vm questions
by Eliot Miranda 14 May '09

14 May '09

Hi Jecel, you ask some pointed questions on the Stack & JIT Cog VMs that need good answers and I suspect are generally interesting so I'll answer to squeak-dev also. On Thu, May 14, 2009 at 4:36 AM, Jecel Assumpcao Jr <jecel(a)merlintec.com>wrote: > [snip] > Eliot wrote: > > Yes. In the JIT an interpreted frame needs an extra field to hold > > the saved bytecode instruction pointer when an interpreted frame > > calls a machine code frame because the return address is the "return > > to interpreter trampoline" pc. There is no flag word in a machine > > code frame. So machine code frames save one word w.r.t. the > > stack vm and interpreted frames gain a word. But most frames > > are machine code ones so most of the time one is saving space. > > Ok, so the JIT VM will still have an interpreter. Self originally didn't > have one but most of the effort that David Ungar put into the project > when it was restarted was making it more interpreter friendly. The > bytecodes became very similar to the ones in Little Smalltalk, for > example. > > Will images be compatible between the JIT VM and the Stack VM? At least in the first version of the JIT yes. There are a couple of restrictions. - the code that rebuilds the Character table in SystemDictionary>>recreateSpecialObjectsArray has to be replaced by code that simply copies the table. This is because the JIT caches the Character table's oop in the generated machine-code for the at: primitive - the use (e.g. in Pharo) of the SmallInteger primitives 1 through 17 on LargePositiveInteger must be replaced by the relevant large integer primitives, which will be included in both the Stack and JIT Cog VMs. But I do expect to evolve the object representation quite soon, and this will break image backward-compatibility altogether. But I will want to produce a Stack VM that is compatible with the new format, not just a JIT VM because platform spread is very important to maintain and it'll be a while before more ISAs than x86 will be supported. Or do you > expect the latter to not be used anymore once the JIT is available? I expect that an interpreted Stack VM will survive for a long time and be the standard VM on ISAs such as SPARC, Itanium, MIPS, while the JIT will be available probably in the following order IA32/x86, ARM32, x86-64, PowerPC. I had originally understood that the Stack VM would be compatible with > older images (since you divorce all frames on save and remarry them on > reload) but I had missed the detail of the different bytecodes for > variable instance access in the case of Context objects. No, the Stack VM is not compatible with older images. The Context VM with closure bytecode extensions (e.g. John's current 4.0 beta VM) is backward-compatible and is the bridge over which one can bring forward pre-closure images to the Stack VM and JIT VM which are Closure-only VMs. One could make the Stack VM run older images but it would be difficult (and hence probably buggy) and I think unnecessary. One can always run older images on older VMs for as long as OSs support the older executables (and that other VM technology makes that easier these days). One can migrate an older image forward to the Stack VM using the bootstrap and the Context VM with Closure extensions. Packaging technologies such as Monticello make images much less important these days. One should expect to be able to export one's code in the form of a package and load it into a newer image, perhaps with a little massage. So keeping those dusty decks running on up-to-date VMs is IMO both wasted effort and a hindrance to obtaining maximum performance on newer VMs. Best Eliot

1 0

Re: [Vm-dev] stack vm questions
by Eliot Miranda 14 May '09

14 May '09

On Wed, May 13, 2009 at 5:05 PM, Jecel Assumpcao Jr <jecel(a)merlintec.com>wrote: > > Eliot, > > > [JIT code uses call which pushes PC first] > > Ok, so this can't be helped. > > > So while one could I don't see that its worth-while. Even if one did > > keep the arguments and temporaries together one would still have the > > stack contents separate from the arguments and temporaries and > > temporary access bytecodes can still access those so arguably one > > would still have to check the index against the temp count. > > Really? I wouldn't expect the compiler to ever generate such bytecodes > and so wasn't too worried if the VM did the wrong thing in this > situation. There's a tension between implementing what the current compiler produces and implementing what the instruction set defines. For example should one assume arguments are never written to? I lean on the side of implementing the instruction set. > In the JIT the flag is a bit in the method reference's LSBs and is set for > free > > on frame build. > > That sounds like a neat trick. Are the stack formats for the interpreted > stack vm and the jit a little diffeent? Yes. In the JIT an interpreted frame needs an extra field to hold the saved bytecode instruction pointer when an interpreted frame calls a machine code frame because the return address is the "return to interpreter trampoline" pc. There is no flag word in a machine code frame. So machine code frames save one word w.r.t. the stack vm and interpreted frames gain a word. But most frames are machine code ones so most of the time one is saving space. Thanks for the explanations. I haven't figured out how to do this in > hardware in a reasonable way and so might have to go with a > different design. I guess that in hardware you can create an instruction that will load a descriptor register as part of the return sequence in parallel with restoring the frame pointer and method so one would never indirect through the frame pointer to fetch the flags word; instead it would be part of the register state. But that's an extremely uneducated guess :) > > -- Jecel > >

3 6

Re: [Vm-dev] stack vm questions
by Eliot Miranda 14 May '09

14 May '09

Hi jecel, On Wed, May 13, 2009 at 3:46 PM, Jecel Assumpcao Jr <jecel(a)merlintec.com>wrote: > > I have read the description of the stack vm again: > > > > http://www.mirandabanda.org/cogblog/2009/01/14/under-cover-contexts-and-the… > > It seems to me that it would be possible to keep the arguments and the > remaining temporaries together. This would require keeping the numTemps > in the flags word instead of the numArgs. It would also mean moving the > code to nil out the temps towards the beginning of > #internalActivateNewMethod and #activateNewClosureMethod:numArgs: > (before pushing the IP). The idea is that then #temporary:in: would > become simpler, which is important since it is a very popular operation. But the split arguments/temporaries organization is determined by frame build order, and the anticipation of a JIT. The caller pushes receiver and arguments, and in a JIT then pushes the return pc (as part of the call instruction that makes up the send). Then a frame is built at the end of which temporaries are initialized. In the JIT there will always be at least the return pc/caller's saved instruction pointer between the arguments and the temporaries, and since the offsets to access each can be determined at compile time the cost of separating them is low. So while one could I don't see that its worth-while. Even if one did keep the arguments and temporaries together one would still have the stack contents separate from the arguments and temporaries and temporary access bytecodes can still access those so arguably one would still have to check the index against the temp count. In practice the cost is not that high in the stack vm, or at least the stack vm is still substantially faster than the context vm with arguments and temporaries split. And in the JIT it really isn't a performance issue at all. This change would make it a little harder to fix the bug in #marryFrame: > but I don't see any other changes that would be needed. Is there some > important design issue with keeping the arguments and temps separate > that I am missing? I can imagine a compiler that avoids initially > filling out the temps with nils by creating them lazily on first > assignment and that wouldn't work with my change. But I don't know if > this is a planned feature (it complicates reflection a bit since you > have to fake the uninitialized temps in order not to confuse the > debugger). > > I found the use of a one byte flag to indicate that the context pointer > is valid interesting since it seems to me that the same information is > available by looking at the pointer itself (nil or not). Is this just a > performance issue or are there situations where the flag can be zero but > the pointer is not nil? It was my original intent to avoid having to write the context pointer field. It used to be important to avoid unnecessary writes but on current processors with good cache interfaces I don't think avoiding the write makes any difference and I write it anyway in the current VM (which has moved on a little from the blog posts). But it is quicker to test the flag than test against nil simply because he reference to nil is an arbitrary 32-bit value, not simply 0 or 1. In the JIT the flag is a bit in the method reference's LSBs and is set for free on frame build. Some small details that seem like errors to me but could be a lack of > understanding on my part: > > - the drawing above the definition of "activateNewClosureMethod: > blockClosure numArgs: numArgs" shows the flag word right after fp but > the code indicates that it should be a method pointer instead. You're right. I missed out the methods my accident in the left-hand stack page. > - callersFPOrNull is used in #commonCallerReturn but not assigned to. Ah > - I see that the first definition near the top of the text is > incomplete. The real definition in the discussion about return does have > the assignment. > > Cheers, > -- Jecel Thanks!

2 1

Re: [Vm-dev] stack vm questions
by Eliot Miranda 14 May '09

14 May '09

On Wed, May 13, 2009 at 3:46 PM, Jecel Assumpcao Jr <jecel(a)merlintec.com> wrote: > [snip] > Some small details that seem like errors to me but could be a lack of > understanding on my part: > > - the drawing above the definition of "activateNewClosureMethod: > blockClosure numArgs: numArgs" shows the flag word right after fp but > the code indicates that it should be a method pointer instead. > fixed. thanks again!

1 0

stack vm questions
by Jecel Assumpcao Jr 14 May '09

14 May '09

I have read the description of the stack vm again: > http://www.mirandabanda.org/cogblog/2009/01/14/under-cover-contexts-and-the… It seems to me that it would be possible to keep the arguments and the remaining temporaries together. This would require keeping the numTemps in the flags word instead of the numArgs. It would also mean moving the code to nil out the temps towards the beginning of #internalActivateNewMethod and #activateNewClosureMethod:numArgs: (before pushing the IP). The idea is that then #temporary:in: would become simpler, which is important since it is a very popular operation. This change would make it a little harder to fix the bug in #marryFrame: but I don't see any other changes that would be needed. Is there some important design issue with keeping the arguments and temps separate that I am missing? I can imagine a compiler that avoids initially filling out the temps with nils by creating them lazily on first assignment and that wouldn't work with my change. But I don't know if this is a planned feature (it complicates reflection a bit since you have to fake the uninitialized temps in order not to confuse the debugger). I found the use of a one byte flag to indicate that the context pointer is valid interesting since it seems to me that the same information is available by looking at the pointer itself (nil or not). Is this just a performance issue or are there situations where the flag can be zero but the pointer is not nil? Some small details that seem like errors to me but could be a lack of understanding on my part: - the drawing above the definition of "activateNewClosureMethod: blockClosure numArgs: numArgs" shows the flag word right after fp but the code indicates that it should be a method pointer instead. - callersFPOrNull is used in #commonCallerReturn but not assigned to. Ah - I see that the first definition near the top of the text is incomplete. The real definition in the discussion about return does have the assignment. Cheers, -- Jecel

1 0

confirm that messageSelector needs less coddling
by Eliot Miranda 13 May '09

13 May '09

Hi All, "coddling" is an English term meaning to treat in an over-protective way, so one may for example coddle a baby. In primitivePerform and primitivePerformAt some care is taken to save messageSelector and restore it if either primitive fails during lookup. Failure occurs when the number of arguments in the perform does not match the found method, but this is by the way. As far as I can see saving and restoring messageSelector is unnecessary because it cannot be read after failure. This is in contrast to newMethod which is read on failure when the failing perform method is activated. I wanted to confirm with you in case I've missed something. I think I'm right even if the perform is wrapped inside any number of other performs or executeMethods, but more heads are better than one. best Eliot

2 1

Re: [Vm-dev] Immediates
by Eliot Miranda 11 May '09

11 May '09

On Fri, May 8, 2009 at 2:26 PM, Jecel Assumpcao Jr <jecel(a)merlintec.com>wrote: > > 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. One of the things I think would really helps here is to have a way of assigning the id-hash of a Symbol based on its string hash. Then MethodDictionaries and the like don't have to be rehashed on load. I could imagine a new:withHash: primitive that creates an object with a specified hash atomically, whihc is safer than adding a separate setIdHash: primtive; VW has the latter. Like VisualWorks, Self uses 30 bit integers with a 00 tag (which makes > detagging/retagging unnecessary for addition, subtraction and bitwise > logical operations). FYI, VW does not use 00 for SmallIntegers; it uses 00 for objects. So it does have to detag for certain operations. But of course it optimizes addition/subtraction by only detagging one of the two values so it doesn't have to retag. Self, Strongtalk and V8 all do use 00. 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. Yes, this is neat. They use it in become operations which are very common as slots are added and removed right? > 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 > >

2 1

Re: [Vm-dev] Immediates
by Eliot Miranda 08 May '09

08 May '09

On Thu, May 7, 2009 at 4:13 PM, Jecel Assumpcao Jr <jecel(a)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. > > > -- Jecel > >

5 6

mantis http://bugs.squeak.org/view.php?id=7349
by John M McIntosh 08 May '09

08 May '09

Folks should try the fix and see Ihttp://idisk.mac.com/bertfreudenberg-Public/temp Double-click EtoysToGo.app and drop in wendy.pr for it to explode, well or not after the fix is applied. -- = = = ======================================================================== John M. McIntosh <johnmci(a)smalltalkconsulting.com> Twitter: squeaker68882 Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com = = = ========================================================================

8 29

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

Vm-dev May 2009