198086 - optimizer enhancement: generate only single class per script and all its functions

Status: VERIFIED FIXED

(Rhino Graveyard :: Compiler, enhancement)

Description

[Igor Bukanov]

Currently Rhino optimizer generates one Java class per JavaScript function which
may lead to significant runtime overhead. I think it would be worth to try to
replace that by a single class with a switch dispatch to select code for a
particular function. I open this report to record work on it.

Comment 1

[Igor Bukanov]

Attachment: Storing numerical constants in the single class

This is a small step to address the issue, but it makes sense on its own since
currently script containing

function f() { return 1; }
function g() { return 1; }

print(f()+g()+Math.sqrt(1));

would create 3 classes each contain a code to generate a wrapper Number object
to represent 1 and with the patch the single constant from the class for the
main script will be used.

Comment 2

[Igor Bukanov]

Attachment: All function implementations are generated in the single class.

This is an extension of the previous patch to place code implementing functions
bodies in single class. 

With the new patch classes implementing functions contain only constructor and
a call method that calls a static method 

c<function-index>(<FunctionClass> function, Context cx. Scriptable scope,
Scriptable thisObj, <possible-direct-call-params>, Object[] args)

In this way almost all strings representing JS names and strings are stored in
the main class reducing total amount of memory that generated classes occupy.

Comment 3

[Igor Bukanov]

Attachment: All script and function specific code are generated in one class

With this patch the first generated class will contain all code to initialize
and execute script and functions. The rest of generated classes contain
effectively 3 functions that looks like:

void constructor(Context cx, Scriptable scope, int id)
{
    store id
    static call to firestGeneratedClass._i<id>(this, cx, scope);
}

Object call(Context cx, Scriptable scope, Scriptable thisObj, Object[] args)
{
    static call to firestGeneratedClass._c<id>(
	signature-with-possible-direct-call-optimization);
}

Object getEncodedSource()
{
    static call to firestGeneratedClass.getEncodedSourceImpl(id);
}

So only the first class contains all script-specific strings and functions, the
rest of the generated classes looks almost identical. To make them identical,
it would be necessary to replace 
    static call to firestGeneratedClass._i<id>(this, cx, scope);
    static call to firestGeneratedClass._c<id>(this, cx, scope);
by a switch like

switch (id) {
  case 0: static call to firestGeneratedClass._i0(this, cx, scope);
  case 1: static call to firestGeneratedClass._i1(this, cx, scope);
  ...
}

and 
switch (id) {
  case 0: static call to firestGeneratedClass._c0(...);
  case 1: static call to firestGeneratedClass._c1(...);
  ...
}

The patch touches org/mozilla/classfile/ClassFileWriter to add a support for
switch generation which patch uses to generate switch in getEncodedSourceImpl
and adds public methods to NativeFunction to initialize protected fields which
are not accessible otherwise for code in static functions in
firestGeneratedClass.

Comment 4

[Igor Bukanov]

Attachment: An update for the previous patch to fix some ugliness

Comment 5

[Igor Bukanov]

Attachment: Working full fix: generating only 2 classes to represent script code

With the above patch the optimizer produces at most 2 classes for a script with
arbitrary number of possibly nested functions.

The patch passes the test suite with optimization set to 0 and 9 but since it
is very intrusive, I will try to test it before committing. 

In principle it is possible to make optimizer to generate exactly one class
since a subclass of omj.NativeScript is not necessary and can be replaced by a
omj.NativeFunction implementing some interface and hence the same class that
patch uses to generate omj.NativeFunction subclass can also implement that
interface. But such change would probably require non-trivial modifications in
omj.NativeScript.

Comment 6

[Igor Bukanov]

Attachment: Patch update after partial committ.

I committed the changes non-optimizer related changes that are necessary for
the patch like support for tableswitch in org/mozilla/classfile/ClassFileWriter
and making BaseFunction.createObject public instead of protected so it can be
called from after changes to the optimizer.

Comment 7

[Igor Bukanov]

Attachment: Patch update to use more compact bytecode for call switch and remove changes to OptNameHelper

I removed changes to OptNameHelper since they were too intrusive and changed
naming of generated files which I would prefer to keep as compatible with the
current naming as possible.

The patch passes the test suite and few my own stress tests. In addition the JS
compiler is working fine as well.

Comment 8

[Igor Bukanov]

I benchmarked the patch against BenchPress.js and from func_bench.js
mozilla/js/benchmarks. As far as I can tell an additional overhead switch/static
method call to implement Function.call does not change the running time in any
significant way. Such overhead is present only when direct call optimization is
not available since direct calls invoke the corresponding static method directly
and their timing should be the same as before the patch. 

The benchmarks confirmed this as I could not see a statistically meaningful
difference between running time when using -opt 9. 

With -opt 0 under JDK 1.1 there is not change in timing, under JDK 1.3 the patch
makes benchmarks slower by 1-2% while under JDK 1.4 they are faster by 1-2%.
This is under Linux.

Now regarding the generated class files size. Using JS compiler for
examples/NervousText.js as described at the bottom of
http://mozilla.org/rhino/jsc.html gives without the patch 8 class files with
total size 21321 and corresponding compressed jar gives 9842 bytes. 

After the patch the compiler produces only 3 class files with the total size
12851 and the jar size 5569 bytes.

Comment 9

[Igor Bukanov]

Attachment: Yet another patch update to generate smaller bytecode for switches.

Comment 10

[Igor Bukanov]

Attachment: Test case to check for class file limitations.

Due to limitations of JVM class format, the patch clearly adds restrictions to
complexity of script code that optimizer can handle since now all the constants
and strings goes into single file. But such additional restrictions are not
that bad since the patch does not affect the major restriction of restricting
byte code size for methods to 64K.

The test case generates a JS source of the form

function f1(n) { return n; }
function f2(n) { return f1(n); }
function f3(n) { return f2(n); }
...
function f<N>(n) { return f<N-1>(n); }

f<N>(<some-value>);

and then compile/execute it via "var code = new Script(); code()" since eval
can not be used as Rhino uses interpreter mode for it.

It turned out that before patch the maximum value for N with optimization level
0 was 2847 before JVM refused to load the file and after it actually increased
to 2853. The limit came from the code for script body that has to instantiate N
different functions and the patch made that slightly more compact that explains
the reason for the limit increase. Of cause a mixture of top-level functions
and nested ones would show the patch limitations since without the patch nested
functions will be initialized in a separated classes, but still a limit of 2500
functions per script seems reasonable.

Comment 11

[Igor Bukanov]

I tagged Rhino sources with before_less_classes_optimizer tag and committed the
patch. I do not mark the bug as fixed since I would prefer to try to change
optimizer to produce exactly one class for both script and all the functions it
contains. It will allow to make all internal fields and methods private which
would allow for better optimization of generated code by JVM.

Comment 12

[Igor Bukanov]

Attachment: Removal of the dual nature of NativeScript

The patch changes omj.NativeScript to represent only instances of Script object
in scripts and removes its second role to server as a superclass for compiled
forms of JS scripts. In is not only allow to make optimizer to generate only
single class but also would make instances of Script generated by optimizer not
to depend on the scope. The later is essential for Script object reuse to
execute it against different scopes.

Currently the optimizer sets the prototype of the compiled script to
Script.prototype from the scope but this wrong since the compiled script is
never exported to script. The interpreter never did it so compiled script
produced in this mode were almost scope independent (they currently hold a
scope reference through instantiated regular expressions while scripts
generated by the compiler instantiate the regexps during eval call).

Comment 13

[Igor Bukanov]

Attachment: One class for script and all its functions

Patch makes optimizer to generate exactly one class to represent a script and
all functions. That class implements Script and initializes in the default
constructor and Script.eval implementation script support while using a
separated constructor to initialize the function objects.

Comment 14

[Igor Bukanov]

I committed the last patch which finally allows to mark the bug as fixed.

Comment 15

[Phil Schwartau]

Rubber-stamp vrfy -

Comment 16

[Igor Bukanov]

Attachment: Fix for regression that prevented script to be executed twice

Without this fix which I committed Script instances can not be executed twice
since it would reinitialize NativeFunction each time the script is executed. 

The fix also moves initialization of regular expression for scripts (and only
for scripts) directly into the call method implementation where they are stored
into a local variable. Previously regexps would be stored in a class field
which the call method accessed thus making Script.exec non-reentrant and thread
unsafe.

The last part would probably should go as a fix for bug 218440 but it is too
complex to separate the patches.

Note that the test case from attachment 130962 [details] from that bug can be used to
check this regression since the test calls Script.exec twice.

Comment 17

[Igor Bukanov]

Trageting as resolved against 1.5R5