256339 - Stackless interpreter

Status: RESOLVED FIXED

(Rhino Graveyard :: Core, enhancement)

Description

[Igor Bukanov]

Currently interpreter uses Java stack frame per each script frame. That limits
script recursion to the maximum depth of Java stack and since interpreter
consumes a lot of stack space for its local variables, a script that runs OK
with optimizer can cause StackOverflowException.

So the idea is to dynamically allocate space to hold local variables and
eliminate recursive usage of Java stack eliminating probably last limit in Rhino
on code complexity.

This should also allow to implement tail recursion optimization later and simply
integration of continuation patch to Rhino that was originally developed against
Rhino 1.5R2 by Christopher Oliver.

Comment 1

[Igor Bukanov]

Attachment: Implementation

The patch adds the new internal class, State, and uses it to store the state of
JS frames.

The patch wraps the current interpreter frame into additional loop that is used
to transfer control between function and during stack unwind.

The patch tries to keep the overhead of additional indirection via caching in
local variables frequently used runtime objects like stack and string table
references etc.

The patch also takes advantage of the fact that catch and finally handlers are
statements in JS and expression stack should be empty when they executes. Thus
it is possible to use a local variable to track stack references and
save/restore in to the state structure only during call/normal return
implementation.

Note that PC counter should always be accessed through state since virtually
all call to ScriptRuntime methods can throw catchable exceptions. So the patch
introduces some overhead but it also allow to simplify code since many helper
functions now takes only State and Context arguments instead of stack, sdBl,
scope etc lists.

Comment 2

[Igor Bukanov]

I run benchmarks from mozilla/js/benchmarks directory and on average the patch
slows down the interpreter performance by less then 3%. 

Comment 3

[Igor Bukanov]

The previous comments are wrong: with the patch
mozilla/js/benchmarks/all_bench.js runs faster by 2-3% then without. In addition
although mozilla/js/benchmarks/BenchPress.js runs slower, the difference is less
then 1%.

Comment 4

[Igor Bukanov]

I committed the patch given the above results and the fact that with the patch
script recursion is really limited only by the amount of available memory.