A VM in Java with tail-calls and continuations

Friday, July 29, 2005

The second commit?

If you'd kept an eye on the repository, you'd know I've been working on the Frame class, and I'm pretty much done with it for now. =)

As I said, there were different possibilities regarding the implementation of this class - let me present you with two.

Frames must store a stack for the function. This frame's size is well known, so this is not a problem. There are two kinds of things the frame must hold: primitive values (ints, floats, longs and doubles - since booleans, bytes, shorts and chars are stored as ints) and references (subclasses of Object). From these: ints, floats and references take 32 bits for 1 word; and, longs and doubles take 64 bits for 2 words.

First approach: use an Object[] and box primitive values. For longs and doubles store the boxed Long or Double in the first word and null in the second word.

Second approach: use 3 arrays (an int[], a double[] and an Object[]) one to hold 32 bit primitives, another for 64 bit ones and one for references; the double[] can have half the size.

The first approach is conceptually simpler, and it also makes all operations simpler. The second approach was tested to be at least two times faster than the first (even without taking into account the extra garbage the first produces).

The rational for the second approach is that: no primitives are boxed; ints are more common than floats (and doubles more common than longs); intBitsToFloat (and longBitsToDouble, etc) are fast; space wast is minimized (vs. having 5 arrays).

I took the simpler, though slower, approach for now. I have, however, tried to encapsulate inside the Frame class everything necessary to make the move later. Here goes the class's current interface (you can also check an implementation):


package net.sf.jauvm.vm;

import java.io.Serializable;

public final class Frame implements Cloneable, Serializable {
public Frame getParent();
public int getRet();
// public InterpretableMethod getCode();

public Integer popInt();
public void pushInt(Integer val);
public Integer getInt(int var);
public void putInt(int var, Integer val);
public Long popLong();
public void pushLong(Long val);
public Long getLong(int var);
public void putLong(int var, Long val);
public Float popFloat();
public void pushFloat(Float val);
public Float getFloat(int var);
public void putFloat(int var, Float val);
public Double popDouble();
public void pushDouble(Double val);
public Double getDouble(int var);
public void putDouble(int var, Double val);
public Object popObject();
public void pushObject(Object val);
public Object getObject(int var);
public void putObject(int var, Object val);

public Frame popParameters(Class<?>[] parameterTypes, int ret, /*InterpretableMethod code,*/ int maxStack, int maxLocals);
public Object[] popParameters(Class<?>[] parameterTypes);

public void pop();
public void pop2();
public void dup();
public void dupBnth1();
public void dupBnth2();
public void dup2();
public void dup2Bnth1();
public void dup2Bnth2();
public void swap();

public boolean isImmutable();
public void makeParentsImmutable();
public Frame clone() throws CloneNotSupportedException;

The first set of methods are getters for: the return address; this frame's parent frame; and, the corresponding method's code (unimplemented) - these properties are constant.

The second set are basic stack operations. Popping off and pushing into references and primitives, setting and getting reference or primitive local variables. These functions take and return boxed primitives due to the fact that Frames are implemented with an Object[]. However, due to Java 5.0's auto-(un)boxing, this interface can be changed to use primitive values, almost without modification to its clients (besides a recompile).

The third set are methods that help in handling invocations. The first one creates a new Frame for an interpretable invocation, popping the parameters into it. The second one returns an Object[] suitable for invocation through reflection.

The fourth set are the general purpose stack operations of the JVM, that benefit with knowledge of the internal structure of Frame objects.

And, the last set manages the immutability of Frame objects -frames captured by continuations must remain immutable. Accordingly: when you do a new Continuation() you call makeParentsImmutable() on the current frame, effectively marking all parent frames as immutable; when you need to modify a Frame you check its immutability with isImmutable() and, if necessary, you clone that Frame.

That's all for now. I'll work on that InterpretableMethod class now.

No comments: