I meant it more as a prototype for how an entire function (containing one or more loops, plus other operations) could be structured, if jumps are known to be local to that function.
What do you make of this test case that I put together?
jsperf.com/case-inside-loop
Thanks for the correction Zarf.
Ben, Your second test case is broken, try jsperf.com/case-inside-loop/3
The setup is only run between tests, so after it had run once jump would remain undefined and the test would turn into a loop that never ran. Once I fixed it the fasted test was the third, which is what I expected. While and for loops are basically equivalent, except that your for loop increments two variables but your while loop only incremented one.
After thinking a bit longer I finally understand what your switch idea is meant to do. I think though that the call instructions will make it impractical. jsperf isn’t ideal for testing such a thing though, because your other two test cases don’t represent what our VMs do, with all their extra infrastructure. Hence why I want to make a glulx performance test suite.
Thanks, I figured something must be broken but I didn’t know what.
I have just pushed forward an update, so that ZVM is now the default Z-Machine engine! In addition, the problems I listed in the first post have been fixed.
Quote boxes are displayed, however they sometimes take part of the status line with them too. I don’t know why this is - I’ll consult some other Z-Machine implementations soon to see how they do it.
Which is only a problem because you want to work JIT, right? Otherwise one might turn each goto into a function call, and make all the functions local inside one main function. Presumably the JS compiler would then turn all those function calls into gotos again. Or am I missing something?
I don’t really understand what you’re suggesting. Can you put some pseudo code together?
All right, with a HUGE stress on “preudo”. Thinking in Scheme and currently programming in Lua probably makes for a weird parody of JS, and not knowing the Z-machine VM may make the whole proposal unapplicable.
I assume, possibly wrongly, that the VM code looks somewhat like:
Label1: (* Probably line numbers are used, but put an L before them and they become legal JS function names *)
Do a
Do b
...
Do c
Goto Label2
Label3:
Do d
Do e
if F goto Label3 end
Do g
Do h
Goto Label4 (* Or at some point there is an end instruction, or we simply run off the end of the code *)The level 1 translation of this is a switch; the level 2 translation - I understand - a set of mutually recursive functions:
function Label1() {
<Do a>
<Do b>
...
<Do c>
Label2()
}
function Label3() {
<Do e>
<Do f>
if (F) Label3()
else {
<Do g>
<Do h>
Label4()
}
}If the ZVM has subroutine calls, they will translate in non-tail calls, and use the JS call stack. Also, it may be useful to pass a standard set of arguments around (which doesn’t affect my point). There may be elected jump targets (goto targets[j]), but this assumes there are no freely computed ones. Am I correct so far?
Now this approach with functions is a show stopper on both sides. For you, because you cannot create one huge function, because that would mean once-for-all compilation instead of JIT, and for SJ, because it cannot get rid of those function calls. JS being an imperative language, the function definitions might change at ny time, so it must go through the environment lookup process for each call.
With once-for-all compilation, one might wrap the whole collection of functions up, thus:
function play() {
var Label1 = function() {
...
}
var Label3 = function() {
...
}
...
Label1()
}Now JS ought to be able to deduce that there is no assignment to any LabelN variable, nor a general eval or other spoilgame, so the values of the function variables will never change, and therefore function calls can be translated into direct jumps to the code.
Does that make things clearer, or only more muddled? Or am y clearly muddled?
I can’t speak to whether it’s possible for a JS interpreter to translate function calls to jumps, but it doesn’t seem like any of them currently do.
I added your scenario to the jsperf benchmarks I made a while back:
jsperf.com/case-inside-loop/6
It’s slightly better than the other functional approach I tried, but not by much.
I’ve been pleasantly surprised by the performance of a switch statement inside a labeled for(;
loop. It’s something I came up with trying to optimize away the conditional branch from the while statement.
Biep, thanks for the more detailed explanation.
Branches and jumps really aren’t that big of a problem, and my solution of identifying idioms is quite successful. It doesn’t catch every branch, but that just means I need to add more idioms. There are other solutions which account for every branch, some of which Ben has in his benchmark. Your example with functions for branches seems more convoluted than these, and doesn’t look like an improvement to me. Note however that jump addresses can be calculated at run time (though normally they are constant addresses), you can jump to another function, and you can jump/call code in RAM, which allows for dynamic code generation. I don’t know anyone who uses that functionality though.
What you don’t seem to have accounted for is that we need to manage the VM’s call stack ourselves, because we need to be able to serialise it (when we save) as well as to halt in the middle of a function when we request input. These function calls are the real show stopper, because it means that we must run a function to add a stack frame, drop back to the main VM loop, and then run the new function. Function acceleration is a way of taking a short cut - it allows us to directly run a very limited set of functions which we know we can safely run off the VM call stack. I have started experimenting with doing the same for potentially any function, but it’s still a long way off being ready (or even being as fast as it is now), and it’s not a high priority for me.
I’m not sure if once-for-all compilation would be an improvement, or if it’s even possible. But for browsers with support for Web Workers, we could compile functions in advance while waiting for the user’s input. Shouldn’t be too hard to add once Worker support is added.
Freely computed jump addresses kills the idea, of course. Using the equivalence of tail calls and goto’s is a time-honoured technique in Scheme compilation, basically starting with the paper “Lambda, the ultimate GOTO”. JS being very close to Scheme, it seemed a natural approach.
Another, slightly younger, technique is compiling with continuations.
And yes, save/restore is equivalent to call/cc in Scheme, which JS doesn’t have. So indeed, whenever intermediate saving would be possible, subroutine calls ought to manage their own call stack. I don’t quite see the problem with IO, though - simply calling a blocking IO procedure and afterwards continuing would deal with that, wouldn’t it?
But again, I am badly informed, and local circumstances conspire to keep it that way 
. (Living in Bénin, West-Africa, I have a very intermittent Internet connection with an average throughput of 200 bytes/second, so e.g. visiting the site where bcressey put my code has so far only resulted in frustration. Opening a web page may take scores of attempts, either the DNS server or the site not being reached, or the connection being interrrupted halfway.)
call/cc seems like a kind of mix of throw/catch and yield (or instead, using yield to implement throw/catch). Now changing ZVM to use yield would actually be an interesting thing to try… but it’s not supported enough to become our solution. Even if we did use yield it wouldn’t help convert the JS call stack to one we can store in a save file.
And we have to assume that any function could potentially be on the call stack when we serialise it, until we can prove that a particular function won’t be. The experiment I mentioned before is a start to solving that challenge by gradually marking functions as safe and unsafe, marking one as safe when all its dependent functions are also safe (and marking others as unsafe if any of theirs are unsafe). These safe functions then can be run directly, without add a frame to the call stack. But it’s not easy, and at the moment it’s slower than the current codebase.
Are you suggesting that we run a loop and poll for input? Because that’s never going to happen, the performance would be terrible.
A cleaner VM design might have been to have the VM completely empty its call stack before looking for input events, and when we receive one then run an event handler function. But we’re stuck with what we have.
Ahh, I understand, I live in PNG and get on the net using my phone’s 2G connection. It’s never that slow, though sometimes it’s only a little more than 1kb/s. I have a tightly controlled list of websites allowed to load images of scripts - this forum has made the cut for scripts but not for images haha.
It is rather the base brick to build any control structure with. Operationally it is equivalent with saving the stack, and calling the continuation with restoring it. A continuation is a first-class function, and may be called more than once. (Of course call/cc tends to be implemented in a much more efficient way.)
Conceptually it is saving the “future” - all that is to happen with the current value. In “1 + 34", the continuation of 4 is "function(x) return 1+3x”. In practice a continuation may capture e.g a deep recursion, and calling it will bring the computation back into that deep recursion.
The concept tends to be elusive until one “gets it”, and then it is quite natural.
All right, I clearly don’t see what is going on here, so I’m going to drop this, at least until I’ve done some homework.