In executing programs, there is a tension among the need to execute quickly, to not take excessive space, and to be able to debug. This paper discusses using a combination of Continuation-PassingStyle for native code in combination with a Threaded-Execution model to address this tension and provide the best of all worlds. Programs can execute at full native speed and then drop instantly into a fully-debuggable execution. Threaded code can be the first level of compilation and then can be easily translated into CPS-style native code that runs approximately 4 times as fast. The execution models can be interleaved seamlessly even within a method.
This paper explores diferent execution models for Smalltalk[
One of the intrinsic tensions in computer science is the space-time tradeof. Nowhere is this
more obvious than in the compilation process. Many of the most important optimizations in
the compiler-writer’s toolkit exhibit this tradeof and many heuristics have been developed to
address this.[
Beyond optimizations, code representation and execution models both exhibit this. Bytecode interpreters lie near one end of the spectrum - very compact representation, but slow execution. Native code lies at the other end of the spectrum - very fast execution, but significantly larger. Ideally we would like to have small code where it’s not performance critical, and fast code where it is.
The rest of this paper is structured as follows: Section 2 describes Continuation Passing Style and Threaded Execution; Section 3 talks about some of the key implementation parameters that enable seamless transition between the execution models; Section 4 presents some preliminary validation of the principles; references to related work are throught the paper; finally, Section 5 provides some concluding thoughts and plans for future work.
There are a range of execution models that can be used to implement a programming language. The most common are native code and bytecode interpreters.
An intermediate option between those extremes is threaded execution. The basic idea is that programs are constructed by stringing together “words”, where each word is the address of some code that performs its operation and then passing control to the next “word” without using the traditional procedure calls. This makes threaded code as easy to generate as bytecode. While it is not quite as compact as bytecode, it runs significantly faster than byte-code interpreters. Rather than traditional procedure calls/returns these threads pass along the current continuation (stack and context in our case), and execute the next “word” via a tailcall.
If we want to smoothly inter-operate native code with threaded code, we have to write the native code so it it uses the same parameters. The compilation technique that aligns with those parameters is continuation passing style.
Continuation Passing Style (CPS)[
In CPS, the control flow is explicit in the form of jumps. Thus all returns are in the form of tail calls that pass control to the next function without pushing any parameters or return addresses onto a stack. Return is explicit by tail-calling a continuation (the return address in the Context).
In our system, CPS means that a call to a new method involves saving the address of the next
code - that is the next word in the threaded representation, and the next native function - in
the Context, and then tail-calling the new method. Returning is simply tail-calling the saved
address. In assembler/machine code the address of the next code is directly accessible. In a
higher-level language such as our implementation language, Zig[
1 const n = 0; // position in context 2 const sum = 1; // position in context 3 fn foo(caller: Context) void { 4 const newContext = caller.push(); 5 newContext.save(n,10); 6 newContext.save(sum,0); 7 tailcall foo1(newContext); 8 } 9 fn foo1(context: Context) void { if (context.get(n)>0) { context.setReturn(foo2); tailcall bar(context,context.get(n)); 10 11 12 13 } 14 const returnC = context.pop(); 15 tailcall returnC.getReturn()(returnC,
context.get(sum)); 1 fn foo() u64 { 2 var n:u64 = 10; 16 } 3 var sum: u64 = 0; 17 fn foo2(context: Context, result: u64) 4 while (n>0) { void { sum=sum+bar(n); 18 context.save(sum,context.get(sum)+result n=n-1; ); 19 context.save(n,context.get(n)-1);
tailcall foo1(context); 5 6 7 } 8 return sum; 20 9 } 21 } 10 fn bar(v: u64) u64 { 22 fn bar(caller: Context, v: u64) void { 11 return v+1; 23 tailcall caller.getReturn()(caller,v+1); 12 } 24 }
Threaded Execution is a form of execution where rather than a sequence of calls to other functions, a function is a sequence of addresses of functions. The hardware stack is unchanged by the sequence of functions (although internally any of them may do so, as long as there is no net change). Figure 3 gives an example of a normal function that calls a sequence of functions. For each call, the language would push the parameters (just ptr in this case) and the return addresses onto the hardware stack.1
Figure 4 shows the same sequence in threaded mode. Note that since each threaded function
passes control to the next, there is no activity on the hardware stack. Since the pc and ptr
parameters are likely to be passed in registers, there is no overhead of memory trafic apart from
fetching the next function address, and the only other overhead is advancing pc to point to the
1Note that the [*] Zig syntax means a pointer to multiple values.
1 fn foo(_ptr: [*]data) [*]data {
2 var ptr = _ptr;
3 ptr = foo1(ptr);
4 ptr = foo2(ptr);
5 ptr = foo3(ptr);
6 return ptr;
7 }
8 n foo1(ptr: [*]data) [*]data {
9 // do something using the data at ptr,
10 // possibly modifying to newPtr
11 return newPtr;
12 }
13 ...
1 const foo = [_]ThreadedFn {&foo1,&foo2,&foo3,&end};
2 fn executeFoo(ptr: [*]data) [*]data {
3 tailcall foo[0].*(&foo[
The first example of threaded program execution known to the author, was the FORTRAN
compiler for the PDP-11 [
The same instruction made the first FORTH [
[
Threaded code has been used in Smalltalk compilers [
The SableVM compiler converts Java byte codes to a threaded execution model [
[
To enable seamless transition between CPS and threaded execution we have to make some particular implementation decisions.
1. the stack cannot reasonably be woven into the hardware stack with function calls; 2. contexts have to contain not only native return points, but also threaded return points; 3. CompiledMethods have to facilitate seamless switching between execution modes.
But first let’s look at some background on the memory model.
The Smalltalk system we are building is designed to support multiple Smalltalk processes executing simultaneously on multiple cores.2 Each process has a private stack. In addition there is a heap, details of which are outside the scope of this paper. Most objects are allocated on the heap, with the exception of three kinds of objects described below.
As was observed by Deutsch and Schifman [
Values can escape in one of two ways: 1. a reference to an object is assigned to a heap object (since we must maintain the invariant that an object cannot point to a younger area of storage, the pointed-to object must be promoted to the heap); 2. a reference to an object is returned from the Context in which it is defined, in which case we must promote the object to the heap.
Promotion of BlockClosure or Context objects may force the promotion of ClosureData objects that they reference. Promotion of a Context object may force the promotion of other Context objects that it references. The word ’may’ is because, while the object must come to reside in the heap, the object may have already been promoted to the heap. 2The Smalltalk processes are executed with operating system threads, but we will use ’process’ to avoid confusion with ’thread’ed execution.
There are 3 data structures that are the connection points for moving between the execution models: the Stack, the Method, and the Context. Figure 5 shows the relationship among the header ctxtStructure d o h selector t e
M · · · references *
· · · header ? threaded PC ? native PC ? previous tcNumber method header ? method threaded PC native PC previous tcNumber · · · ? ? ? · · · ? ?
parameter 2 for M3 parameter 1 for M3 self/result for M3
temp1 for M2 self/result for M2
Heap header method subsequent t x te next word n o c previous 1 M tcNumber temp1 for M1 temp2 for M1 self for M1 header method t x ten ignored o c e exit CPS s a Bprevious=Nil tcNumber stack, heap, Contexts, and Methods. This represents the state of execution where a method, M1, has called M2, which has called M3 which is executing, but hasn’t called any other method. 3.2.1. Stack The first decision is to not use the hardware stack, but instead use a stack allocated per process, with overflow to the heap. In addition to supporting this multiple execution model, by putting all roots in this stack there is no confusion or complexity of tagged values, tagged pointers, and native pointers; everything on the stack is tagged. This simplifies the garbage collector significantly. 3.2.2. Method Every CompiledMethod regardless of execution model has a code area (at a fixed ofset in the CompiledMethod object). Execution of a CompiledMethod begins with a threaded call to the ifrst word. The interpretation of the remainder of the code area is completely defined by this function.
1. For a pure native code method, this will be an array of pointers to the CPS chunks. 2. For a pure threaded method, this will be the threaded code addresses, preceded by a selectorVerify function - which might be replaced at some point with a pointer to native code. 3. For native code backed by threaded code, this would be as in the previous example, except the first word points to the native code. 4. For interpreted code, such as the proof of concept mentioned in Section 4, the first word points to the interpreter, and the remainder of the area would contain the byte-codes.
This could even support multiple interpreters for diferent byte-codes. 3.2.3. Contexts A Context is the representation of a method/function activation record or stack frame. These are initially allocated on the top of the stack, but may migrate to the heap when the stack gets too large or the Context escapes, as explained in Section 3.1. When they are allocated on the stack, they are only partially populated, because they will likely be discarded before they need to be treated as proper objects. Before a Context migrates to the heap, the remaining ifelds are filled in and it can then be treated as a first-class object and can be used to implement Scheme’s call-with-current-continuatiion, light-weight threads, or other control lfows as well as return.
Method pointer points to the method/function for the context. This is set up when the context is created on the stack. threaded PC is the address of the next pointer in the threaded version of the method. This is only filled in when a method/function is called. native PC is the address of the next CPS part of the native implementation. This is only filled in when a method/function is called. For a native CPS method, this will be the next CPS chunk address If there is no native implementation of this method, this will be the next threaded word in the method. If this method were interpreted, this would be the address of the interpreter. Therefore return from a call always just invokes the native PC, passing the threaded PC. Previous context points to the context that invoked the current method/function. This is set up when the context is created on the stack. tcNumber is used to handle non-local returns eficiently in the face of handling exceptions. This is set up when the context is created on the stack. temps are the temporary values for the method. They are initialized to Nil when the context is created on the stack.
BlockClosure and ClosureData references Any BlockClosure or ClosureData is allocated above the Context, with references here. They are accessed as temp indices. parameters are the parameters being passed to the method. This is part of the caller’s stack. These, and everything above are discarded when the method returns. They are accessed as temp indices. result is the location of the result of the current function, and also is the self value in an object-oriented language or the first parameter in non-OO languages. As part of the caller’s stack, it will be left on the stack when the method returns. It is accessed as the last temp index. stack is the rest of the caller’s stack. This is diferent from a context in traditional Smalltalk VMs, where the stack for the method is part of the method’s context. The reason for the change is that it eliminates the need to move the stack values around in the normal context-on-stack case. On return from a Context that resides in the heap, the result value and stack will need to be copied to the stack, becoming the complete stack, as all of the Contexts implicitly reside in the heap.
If a Context is on the stack, then when it is returned from, all of the context before the result is discarded by simply adjusting the stack pointer. This makes the round-trip cost of creating and deleting a Context on the order of 20 instructions - only a small factor worse than a native function call.
If a Context is on the heap, then when it is returned from, the stack portion of the context is copied to the stack area. Combined with the creation and migration of the Context to the heap this is about 3-4 times the round-trip cost of the simpler on-stack cost.
Our contexts are similar to [
Smalltalk is conceptually a very simple language. The only operations are message sends, assignment of simple variables, and return. The connection to the underlying hardware all happens through primitives. Figure 6 shows the addition operation for SmallInteger. The annotation <primitive: 1> says that this method will attempt to evaluate by invoking primitive 1, which is implemented in the runtime/virtual-machine. If the primitive is successful, <primitive: 1> ^ super + aNumber the parameters will be consumed and the result returned. If the primitive fails, then the following Smalltalk code will be executed with the parameters unchanged. This gets translated into the Zig code in Figure 7. Here the &primitive.p1 refers to primitive 1. Normally a Context 1 &primitive.p1, 2 &embedded.superTailSend,sym.@"+", would be created if the primitive failed. However in this case, since there are no local variables, and there is only one message send in tail-call position we avoid creating a Context.
The Zig code for the primitive is shown in Figure 8. It first checks that the message sent was
1 pub fn p1(pc: [*]const Code, sp: [*]Object, process: *Process,
context: ContextPtr, selector: Object) void {// SmallInteger
>>#+
2 if (!sym.@"+".equals(selector))
3 tailcall dnu(pc,sp,process,context,selector);
4 sp[
For completeness, Figure 9 shows the inline code that does the sum operation. We assume that self is a SmallInteger, and if the other value is a SmallInteger, and the result of the summation is a SmallInteger, then we return that new object. Otherwise we return an error.
One of the key compilation/performance approaches for this system is aggressive inlining
of Smalltalk code. The details are outside the scope of this paper, but if a method is inlined
3The reason we check is related to how dispatch is handled, and is outside the scope of this paper.
5
6
7
8 }
}
return error.primitiveError;
1 pub inline fn p1(self: Object, other: Object) !Object { // Add
2 if (other.isInt()) {
3 const result =
4 @bitCast(Object,self.i()+%other.toUnchecked(i64))
;
if (result.isInt()) return result;
that starts with a primitive, we need to embed that primitive call in the method that sends the
message. This looks like &embedded.p1 and Figure 10 shows the code that is referenced in
this case. For a method to invoke an embedded primitive that could fail, a Context must have
1 pub fn @"+"(pc: [*]const Code, sp: [*]Object, process: *Process
, context: ContextPtr, selector: Object) [*]Object {
2 sp[
As mentioned in Section 3.2.2 when execution of a method commences, the first threaded word of the code area is invoked. This means that execution will proceed in the manner defined by that method, so threaded code can call native code and native code can call threaded code with no conditional code required.
Similarly, as mentioned in Section 3.2.3 when a return is made to a Context, the native PC ifeld is invoked, passing the threaded PC field. Hence any kind of executing mode can return to any other with no conditional code required.
In fact, moving in both directions could easily support other execution models such as interpreters.
Starting Debug Mode The first three modes of program execution described in Section 3.2.2 seamlessly support interruption and single-stepping of code. Support for interpreter execution modes would need to be implemented slightly diferently, e.g. with recognition that the return was an interpreter and setting the return to a debugging entry point to the interpreter.. The first word for each method, along with checking for the correct selector, checks to see if interruption is required. This interruption could be debugging, interaction with the global garbage collector, a user or other process requesting interruption, etc. Performance would be negatively afected if this checking is performed too frequently, so it currently is done at the entry point for a method, and at the top of loops.
While executing within native code, if an interruption is required, execution is switched to threaded execution, which can easily be single-stepped. The native PC field in a Context can similarly be set to the threaded function equivalent, which is accessible from the threaded PC ifeld.
This is still a work in progress, but here we will describe a hand-compiled implementation of ifbonacci.
1 fibonacci 2 self <= 2 ifTrue: [ ^ 1 ]. 3 ^ (self - 1) fibonacci + (self - 2) fibonacci
Figure 11 shows a simple Smalltalk version.
Figure 12 shows the threaded implementation.4 All of the benchmarks use direct early-binding of the recursive calls to make them as comparable as possible (dynamic dispatch is covered in another paper). This is similar to the IR code for the Integer>>#fibonacci function in Pharo. p5 is <= which leaves a boolean on top of the stack. If true, then lines 6-8 replace self with 1, and then return. Line 10 creates a Context (which we hadn’t needed because no error was possible and we hadn’t called anything). Then we subtract the literal 1 from self and call recursively in lines 11-13, then the same -2, and finally at lines 17-18 we add the values and return.
Figure 13 shows the first part of the CPS native code paralleling the threaded code. This covers lines 1-13 of Figure 12, Lines 3-6 check for the base case and return 1. Lines 7-8 create the Context (the 0, 2, 0 parameters say 0 locals, 2 max needed stack, and self is temp/local 0, and fibThread refers to the code in Figure 12). Line 9 tries to subtract 1. If it fails, line 10 switches 4This is somewhat de-optimized from the actual benchmark for explanatory purposes. &embedded.verifySelector, ":recurse", &embedded.dup, // self &embedded.pushLiteral, Object.from(2), &embedded.p5, // <= &embedded.ifFalse,"label3", &embedded.drop, // self &embedded.pushLiteral1, &embedded.returnNoContext, ":label3", &embedded.pushContext,"^", &embedded.pushLocal0, // self &embedded.pushLiteral1, &embedded.p2, // &embedded.callRecursive, "recurse", &embedded.pushLocal0, //self &embedded.pushLiteral2, &embedded.p2, // &embedded.callRecursive, "recurse", &embedded.p1, // + &embedded.returnTop, to the threaded code to try the operation, because we obviously have underflow. 5 Line 11-13 sets up for, and makes the recursive call. Line 11 is pointing to line 14 of Figure 12, and line 12 points to the actual code.
Figure 14 shows the second part of the CPS code, corresponding to lines 14-16 of Figure 12.
Finally, Figure 15 shows the end of the CPS code, including possible overflow. Line 8 calls back the native PC from the saved Context.
5Can’t actually underflow here, but this is the correct code. } const newContext = context.push(sp,process,fibThread.
asCompiledMethodPtr(),0,2,0);
const newSp = newContext.asObjectPtr()-1;
newSp[0] = inlined.p2L(sp[0],1) catch tailcall pc[
prim(pc+1,sp,process,context,fibSym); 3 const result = context.pop(process); 4 const newSp = result.sp; 5 newSp[0] = sum; 6 const callerContext = result.ctxt; 7 tailcall callerContext.npc(callerContext.tpc,newSp,process, callerContext,selector); 8 }
The Pharo data is from running on Pharo 10, on the Pharo version of the OpenSmalltalk VM. Pharo JIT is running on a JIT VM, and Pharo Stack is using the Stack Interpreter VM.
Native is the straightforward implementation in Zig using 64 bit integers. Not surprisingly it is very fast, but interestingly the native optimized code for this micro-benchmarks is also very small.
Object is the straightforward implementation in Zig using tagged Objects, with local Zig variables and recursion. This is as good as we could hope to be, using the well-supported hardware stack and call/return semantics. It also demonstrates that using tagged integers doesn’t add too much overhead.
CPS is the CPS conversion of this using our Context objects. This doesn’t use any of the standard conventions - stack, hardware recursion, static types. The fact that this is only 20% slower, at least on AArch64 is surprisingly good. It’s also 10-40% faster than the Pharo JIT’ed code. We don’t know the size of the Pharo JIT’ed code, but we suspect that the CPS code is larger.
Threaded is the fully threaded version. This is extremely easy to generate, and is rewarding that it is only 2-3 times slower than the Pharo JIT’ed code. There was almost no optimization available for such a simple method, so we are very optimistic about the potential for our system. The threaded code is about 25 the size of the CPS code and 3-5 times slower, which seems like a good trade-of.
ByteCode is an unoptimized byte-code interpreter. It is about 12 the size of the threaded version and almost 4 times slower. Since it doesn’t save much space, and is actually slightly more dificult to generate than the threaded version, it doesn’t seem worth pursuing at this time.
As a micro-benchmark of hand-compiled code, this should be taken as simply a validation that this a viable approach to a Smalltalk runtime.
Summary We have shown how we support two (or more) modes of program execution, particularly the seamless transition between the modes. This supports code in either dense or fast modes. We also can easily enter and exit debugging modes.
The decisions to support the easy simultaneous support for native (CPS) and threaded execution (use of a separate stack, and our design for contexts and methods), seem to have been validated. Now we can work on the optimizations
The current benchmark cannot be taken too seriously, but appears to show, in some cases, that the CPS form is only 20% slower than optimal, and the threaded code is only a factor of 5 slower.
Future Work This describes work in progress. The next stage is to automatically compile code so we can get some real performance numbers.
Then we will be working on the optimizations that are enabled by the decisions that we’ve discussed here as well as others we’re exploring. We are very optimistic.
As mentioned in Section 3.1, Context, BlockClosure, and ClosureData objects are initially allocated on the stack. This could also apply to small, known-sized objects, and experiments should be run to see if this is advantageous. 1984, p. 290–296. URL: https://doi.org/10.1145/800017.800541. doi:10.1145/800017. 800541. [21] PLDI, Conference Record of the 1993 ACM SIGPLAN Conference on Programming Language Design and Implementation, volume 28, Association for Computing Machinery, Albuquerque, NM, USA, 1993. [22] Proceedings of the 11th Annual ACM Symposium on Principles of Programming Languages, POPL ’84, Association for Computing Machinery, 1984.