So Hi!<\/p>\n
I’m delighted to say that Qwaq<\/a> has taken me on to write a fast\u00c2\u00a0Croquet\u00c2\u00a0VM and that the VM is to be released under the Qwaq open source licence (an MIT license<\/a>).\u00c2\u00a0 I’m going to blog about the VM here as I implement it.\u00c2\u00a0 The blog is a chance for me to record design decisions as I go along, receive better ideas from you, dear reader, and to hand out the whitewash<\/a>.<\/p>\n This VM will have a dynamic translator, or JIT for short.\u00c2\u00a0 It will dynamically compile Smalltalk bytecodes to machine code transparently to the programmer, and execute this machine code instead of interpreting bytecode. Initially I’m aiming at performance equivalent to the VisualWorks VM, hps.\u00c2\u00a0 This VM should execute pure Smalltalk code some 10 to 20 times faster than the current Squeak VM.\u00c2\u00a0 Subsequently I hope to do adaptive optimization and exceed VisualWorks’ performance significantly.\u00c2\u00a0 I expect to be able to release the first fast version within a year.<\/p>\n The VM is called Cog after the Honda advert<\/a>.\u00c2\u00a0 Fast VMs tend to have something of the Heath Robinson<\/a> or Rube Goldberg<\/a> about them.\u00c2\u00a0 But one of my rules in Cog (rules are meant to be broken) is to do the simplest thing that could possibly work<\/a> (TSTTCPW).\u00c2\u00a0 My principles for Cog, in the sense of fundamental propositions governing my behaviour, are that<\/p>\n – any changes in the image to accomodate the fast VM will not slow down the standard\u00c2\u00a0Croquet\u00c2\u00a0VM (the interpreter)<\/p>\n – any changes in the image to accomodate the fast VM will not increase overall footprint<\/p>\n – the fast VM will be compatible with the Hydra VM<\/a><\/p>\n – there will be some form of source code compatibility for Slang plugins so they can function both in the interpreter and in\u00c2\u00a0the fast VM<\/p>\n I want the Cog to be used by as many people as possible, but I realise there are those interested in small machines or in VM experimentation for whom the interpreter will still be a better choice.\u00c2\u00a0 I hope the principles above will avoid schism and mean the Squeak community can still use a common image format and preserve image portability.<\/p>\n That said I do intend to change the image format somewhat.\u00c2\u00a0\u00c2\u00a0I’ve already implemented closures.\u00c2\u00a0\u00c2\u00a0These, when\u00c2\u00a0implemented appropriately<\/a>, have a significant impact on the performance of a JIT VM.\u00c2\u00a0\u00c2\u00a0This has meant a slight change in the bytecode set; gone are the 6 experimental bytecodes 139 through 143.\u00c2\u00a0\u00c2\u00a0I’ll blog on closures in a subsequent post quite soon.<\/p>\n Hydra is an interesting approach to concurrency, and something Qwaq is interested in.\u00c2\u00a0 BTW, I think Hydra would better be called String, strings being composed of threads or fibers.\u00c2\u00a0 String, like a cog, is typically a small part of a larger whole<\/a>.<\/p>\n \u00c2\u00a0<\/p>\n For the detail-oriented let me dive down a level and say a little more about the project, especially preparatory changes that pave the way for a fast VM.\u00c2\u00a0 I apologize for the density.\u00c2\u00a0 I’m interested in knowing what level of detail I should go into.\u00c2\u00a0 Obviously people who want to collaborate on Cog will want a high level of detail.\u00c2\u00a0 But if the architecture of a fast VM is of more general interest then I need plenty of feedback to help me explain things at the right level of detail.\u00c2\u00a0 Please feel free to comment on this!<\/p>\n OK then, some details.\u00c2\u00a0 Both TSTTCPW and the Principles imply keeping the existing CompiledMethod format.\u00c2\u00a0 In Squeak<\/a>, as in Blue Book Smalltalk-80<\/a> CompiledMethod is an anomalous hybrid<\/a>, its first part being object references used mainly for literals, and its second part being raw bytes used mainly for bytecodes. This is a good choice for an interpreter since both literals and bytecodes can be fetched from the same object, but it causes minor complications in the garbage collector and gets in the way of adding instance variables to CompiledMethod and hence subclassing.\u00c2\u00a0 I’ll blog on why I’m keeping the format and how to get round its limitations soon.<\/p>\n The existing bytecode set is all very well but inflexible.\u00c2\u00a0 It has pressing limits on the size of blocks (1023 bytes of bytecode) and the number of literals (255).\u00c2\u00a0 Being designed for a 16-bit system it misses some compact encoding opportunities, such as a bytecode that pushes a given SmallInteger other than -1, 0, 1 & 2.\u00c2\u00a0\u00c2\u00a0Pushing 3 requires a minimum of 1 byte for the push literal bytecode plus 4 bytes for the literal slot holding the object 3. \u00c2\u00a0A two byte bytecode could push -128 to 127 but take only 2 bytes and be faster. \u00c2\u00a0Luckily migrating to a new bytecode encoding is quite easy.\u00c2\u00a0 Most opcodes – a name I’ll use for an abstract operation such as pushInstVar: – occur in multiple bytecodes – a name I’ll use for a specific encoding such as 0-15<\/a><\/span>, <\/a><\/span>0000iiii<\/a><\/span>, Push Receiver Variable <\/a><\/span>#iiii<\/a><\/span>.\u00c2\u00a0 For all short-form encodings there is an equivalent long-form, and one can modify the compiler to generate only the long forms, allowing the ranges allocated to short-form encodings to be reused.\u00c2\u00a0 I’ve already recompiled a 3.8 image to long-form.<\/p>\n One of the most important optimizations in a fast VM is that of context-to-stack mapping<\/a>.\u00c2\u00a0 Conceptually every method or block activation in Smalltalk is represented by a context object, each of which has its own small stack holding its temporaries and intermediate results.\u00c2\u00a0 Each context points to its caller via a sender slot.\u00c2\u00a0 This has lots of advantages, such as ease of implementing the debugger, implementing an exception system, being able to implement “exotic” control structures such as coroutines and backtracking, and persisting processes, all with no VM support beyond unwind-protect.\u00c2\u00a0 The downsides are that a naive implementation incurs considerable overhead.\u00c2\u00a0 Each send involves allocating a new context and the moving of receiver and arguments from the caller to the callee context.\u00c2\u00a0 Each return involves (eventually) reclaiming the returned-from context, unless<\/em> of course something has kept a reference to it.\u00c2\u00a0 Compared to stack organization in conventional languages, contexts are sloooow.<\/p>\n The idea in context-to-stack-mapping (you’ve guessed it, details in a subsequent post<\/a>) is to house method and block activations on a conventional stack, hidden in the VM and invisible to the Smalltalk programmer.\u00c2\u00a0 Sends look more like conventional calls, passing arguments in the stack in the conventional way, the callee directly accessing the arguments pushed by the caller on to the stack. \u00c2\u00a0The VM then creates contexts only when needed.\u00c2\u00a0 To the Smalltalk programmer contexts still exist, and have the same useful semantics as ever, but the overheads for the common case (send and return) are much reduced.\u00c2\u00a0 While context-to-stack mapping is essential to a fast VM that still provides contexts, it is also useful in an interpreter.\u00c2\u00a0 Andreas Raab suggested I implement context-to-stack mapping in the interpreter as a milestone on the way to the JIT VM.\u00c2\u00a0 I think this is a great idea.\u00c2\u00a0 It should provide a decent speed-up to the Squeak interpreter and help motivate things like the closure implementation.<\/p>\n I think that’s enough for a first post.\u00c2\u00a0 Let me wrap up with a road map of the project “going forward”<\/a>.\u00c2\u00a0 None of this is set in stone, but it’s a plan<\/a>.<\/p>\n Main line:<\/p>\n – restructure the bytecode compiler to decouple parse nodes from specific bytecode encodings (complete)<\/p>\n – replace non-reentrant BlueBook blocks with closures using the restructured compiler (~ 75% complete, currently working on temp names in the debugger)<\/p>\n – implement context-to-stack mapping in the interpreter (to be released Septemberish)<\/p>\n – implement a JIT to replace the interpreter on x86 (to be released Aprilish)<\/p>\n \u00c2\u00a0<\/p>\n In parallel:<\/p>\n – design a bytecode set that uses prefix bytecodes to eliminate limits and provides encodings that provide benefits for 32 and 64-bit images<\/p>\n – provide the ability to subclass and add\/remove instance variables to CompiledMethod and subclasses while retaining the compact interpreter-friendly hybrid format<\/p>\n – target the JIT to other ISAs such as ARM, THUMB, PowerPC and x86-64<\/p>\n – general VM improvements such as<\/p>\n <\/span>– add per-object immutability support, work I’ve already done for Squeak at Cadence, and previously for the VisualWorks VM<\/p>\n <\/span>– move garbage collection out of allocation and into the primitive failure code for new, new: basicNew basicNew: et al so that the VM doesn’t have to deal with moving pointers all over the place. <\/span>– add primitive error codes so the reason for a primitive’s failure is communicated<\/p>\n