Yabasic 3

Many interpreters use an internal stack to keep track of values. For example,

print "Hello, " + "world!"

would typically be represented internally as

cPushString "Hello, "
cPushString "world!"
cConcatenate
cPrint

This is pretty self-explanatory: the string “Hello, ” is pushed onto the interpreter’s stack, followed by the string “world!”; then the two strings are popped off the stack, concatenated (joined together), and the result is pushed back onto the stack; and, finally, the value at the top of the stack is output.

This would be all well and good if pushing onto and popping off the stack were cheap operations. And, with a good stack implementation, they are remarkably cheap. But the number of pushes and pops in an average program tends to be high, with the unfortunate consequence that stack overhead is quite noticeable.

There is another less commonly used model that involves using virtual fixed registers to record values internally. Under a register-based implementation, we might re-write the program above as

cStoreString r1 "Hello, "
cStoreString r2 "world!"
cConcatenate r3 r1 r2
cPrint r3

This stores the string “Hello, ” in register 1, stores the string “world!” in register 2, and then concatenates the strings in registers 1 and 2, storing the result in register 3, which is then outputted. In this model, there is no stack overhead, because the interpreter already knows exactly where to store values.

Yesterday I wrote an experimental version of Yabasic—a very experimental version—that uses a virtual register machine rather than a virtual stack machine. As an unusual twist, commands are registers, so we have

1 cConstantString "Hello, "
2 cConstantString "world!"
3 cConcatenate 1 2
4 cPrint 3

The results are pretty promising. On my computer,

a = 0

while (a < 10000000)
   a = a + 1
wend

runs in around 0.4 seconds under the new implementation. Under Yabasic 2.9.16, the same program takes around 0.9 seconds to run. Under Yabasic 2.763, the program runs in about 1.1 seconds.

And, you know, it really wasn’t all that hard to make the register-based version of Yabasic. It’s still really incomplete at the moment, but so far there’s been very little of the fiddling I was afraid of.

Check it out: Yabasic-3-experimental2.