399348 - Improve performance of NativeArray methods using dense representation

Status: RESOLVED FIXED

(Rhino Graveyard :: Core, defect)

Description

[Norris Boyd]

I've been looking a little at John Resig's JavaScript speed tests (http://ejohn.org/apps/speed/). Rhino could do better on a number of those tests. Yesterday I checked in a change to Rhino that improves the performance of Array.prototype.shift on those tests by a factor of 755! 

The change I made is relatively simple. Previously all array operations were implemented in terms of abstract getters and setters that looked up each element in either a dense Object[] array or in the normal JavaScript hashtables. I changed the previous dense array storage to grow for dense allocation patterns and then I added specialized implementations of some of the Array built-in functions, including shift. Here's the new shift code:

    private static Object js_shift(Context cx, Scriptable thisObj,
                                   Object[] args)
    {
        if (thisObj instanceof NativeArray) {
            NativeArray na = (NativeArray) thisObj;
            if (na.denseOnly && na.length > 0) {
                synchronized (na) {
                    na.length--;
                    Object result = na.dense[0];
                    System.arraycopy(na.dense, 1, na.dense, 0, (int)na.length);
                    na.dense[(int)na.length] = NOT_FOUND;
                    return result;
                }
            }
        }
        // pre-existing code that handles elements in either dense or hashtable...

So now for most array usages the shift is performed using System.arraycopy as it should be rather than a loop over a set of gets and puts. 

That's great, you say, but why are you posting? I'm looking for volunteers to convert these remaining methods of NativeArray:

     *      toStringHelper
     *      js_join
     *      js_reverse
     *      js_sort
     *      js_splice
     *      js_concat
     *      indexOfHelper
     *      iterativeMethod

Comment 1

[Christophe Grand]

(In reply to comment #0)
>      *      js_join

Here goes js_join and js_sort is coming.

Comment 2

[Christophe Grand]

Attachment: js_join

Comment 3

[Norris Boyd]

Attachment: Test case results from running with first patch

Regression tests had a few failures (see attached). I don't know if it's related, but you should check the "denseOnly" boolean variable before doing the specialized dense code. Then you can just use NativeArray's length property and avoid calling getLengthProperty. 

In addition to undefined, you should also compare against NOT_FOUND, which is a special value meaning the key is not defined.

Then you should be able to accumulate your results in a StringBuilder, which will avoid all the object creation overhead of having partial results in String objects.

Thanks!

Comment 4

[Christophe Grand]

Attachment: 2nd attempt

Figured how to run the tests ;-)

denseOnly wasn't involved: dense being null on large array creation was the cause.

I didn't change the string building yet. StringBuilder is Java 5, is it ok to use it?

Comment 5

[Norris Boyd]

(In reply to comment #4)
> I didn't change the string building yet. StringBuilder is Java 5, is it ok to
> use it?

Good catch, thank you. We're continuing to support JDK 1.4 for a while longer, so you're right not to use StringBuilder.

Comment 6

[Norris Boyd]

I did change to use StringBuffer. Change committed:

Checking in src/org/mozilla/javascript/NativeArray.java;
/cvsroot/mozilla/js/rhino/src/org/mozilla/javascript/NativeArray.java,v  <--  NativeArray.java
new revision: 1.71; previous revision: 1.70
done

Comment 7

[Attila Szegedi]

Alternatively, we can use retrotranslator. 

I can set up our build.xml so that we create both a js.jar for use with JDK 1.5 and above, and an alternative js-14.jar that is js.jar treated with retrotranslator. Retrotranslator operates on a bytecode level, provides a JDK 1.4 replacement for 1.5 core JDK classes and methods, and replaces references to them to references to its private replacements of them.

We're following this practice with FreeMarker 2.4 as well, and for now it seems to work like charm, see <http://retrotranslator.sourceforge.net/>

What do you think? 

Comment 8

[Norris Boyd]

I'd love to be able to use 1.5! Go for it.

Comment 9

[Christophe Grand]

Attachment: js_sort

A minimal js_sort for denseOnly NativeArrays. (I'd like to investigate whether using Arrays.sort would be faster.)

js_splice is near ready (I'm benchmarking it).

Comment 10

[Christophe Grand]

Attachment: js_splice

splice is now 55x faster (according to js-speed tests "Array (de)construction, splice") bringing it on par with shift/unshift.

Array Construction, []:16384:0:4.85:0:156:17.442184438303535
Array Construction, new Array():16384:0:1.41:0:32:5.049442413461974
Array Construction, push:16384:203:213.2659574468085:187:329:29.35513932835981
Array Deconstruction, pop:128:219:219.42391304347825:187:312:20.135384466077408
Array Construction, unshift:128::63375:63375:63375:NaN
Array Deconstruction, shift:128::61829:61829:61829:NaN
Array Construction, splice:128::63000:63000:63000:NaN
Array Deconstruction, splice:128::62375:62375:62375:NaN
Array Construction, []:32768:0:0.62:0:16:3.0543229837214154
Array Construction, new Array():32768:0:0.47:0:16:2.687250105835542
Array Construction, push:32768:203:205.6734693877551:187:250:20.124240658123316
Array Deconstruction, pop:256:203.5:209.46875:156:234:9.781780189935292
Array Construction, unshift:256::62641:62641:62641:NaN
Array Deconstruction, shift:256::63344:63344:63344:NaN
Array Construction, splice:256::62890:62890:62890:NaN
Array Deconstruction, splice:256::65640:65640:65640:NaN
Array Construction, []:65536:0:0.63:0:16:3.1031264781497288
Array Construction, new Array():65536:0:0.31:0:16:2.1820896295787557
Array Construction, push:65536::207.95876288659792:187:250:20.186586679945226
Array Deconstruction, pop:512::211.02105263157895:141:235:10.880373651445652
Array Construction, unshift:512::63219:63219:63219:NaN
Array Deconstruction, shift:512::62781:62781:62781:NaN
Array Construction, splice:512::63297:63297:63297:NaN
Array Deconstruction, splice:512::64734:64734:64734:NaN
Array Construction, []:131072:0:0.47:0:16:2.687250105835542
Array Construction, new Array():131072:0:0.47:0:16:2.687250105835542
Array Construction, push:131072::215.89247311827958:187:313:27.59665321768573
Array Deconstruction, pop:1024::217.23655913978496:156:422:27.035563474424137
Array Construction, unshift:1024::64438:64438:64438:NaN
Array Deconstruction, shift:1024::66796:66796:66796:NaN
Array Construction, splice:1024::63360:63360:63360:NaN
Array Deconstruction, splice:1024::62875:62875:62875:NaN

Comment 11

[Norris Boyd]

Committed with some modifications; it appeared that "Array Deconstruction, splice" wasn't going through the dense path. Christophe, if you could review my changes it'd be appreciated...

Checking in src/org/mozilla/javascript/NativeArray.java;
/cvsroot/mozilla/js/rhino/src/org/mozilla/javascript/NativeArray.java,v  <--  NativeArray.java
new revision: 1.72; previous revision: 1.71
done

On my machine I got 754X speedup on splice with these changes.

"sort" was only improved by 9%, but that's probably because the bulk of the work was already done on a dense array even before the change. It would be interesting to see if Arrays.sort were faster.

Comment 12

[Norris Boyd]

Attachment: Perf test for sort

Comment 13

[Christophe Grand]

Attachment: Misc changes on js_join and js_splice

About js_sort: running your test I get a 2x-3x speed-up (running it directly into shell).

Comment 14

[Christophe Grand]

Attachment: sort now uses Arrays.sort instead of heapsort, 46% speed-up (compared to my previous js_sort patch)

So, using Arrays.sort and a Comparator leads to better performance.
Norris, I measured at last the 9% improvement you previously mentioned (I figure another process skewed my previous runs).
But something is worrying me: 1.6R7 seems way faster (regarding Array.sort) than HEAD. Is it a build problem on my side?

Comment 15

[Christophe Grand]

Attachment: js_reverse for dense arrays

js_reverse, 16x faster

Comment 16

[Christophe Grand]

Attachment: test for js_reverse

Comment 17

[Christophe Grand]

I had spare time to check-out 1.6R7 from the CVS and run Norris' perf test for sort and now I'm sure: there is a 2x slowdown between 1.6R7 and HEAD. I profiled several runs but to no avail (I think it's not specific to js_sort).

If you apply my second patch for js_sort you'll get an overall 2x faster sort which will only bring back HEAD on par with 1.6R7.

I'm still ready to work on the remaining methods. I'll take indexOfHelper (and iterativeMethod next) if nobody already took it.

Comment 18

[Christophe Grand]

The 2x slowdown appears with rev 1.321 of Interpreter.java (when adding support for generators). Is the interpretLoop method now too large for some HotSpot optimisations to happen ?

Comment 19

[Norris Boyd]

Thanks for tracking this down. What's the benchmark you're running to see the slowdown?

Comment 20

[Christophe Grand]

Attachment: Benchmark with which I got the slowdown

It's the benchmark you provided to me (I only reduced the number of iterations to make hunting the slowdown practical). On my machine it takes 5s with r1.320 and 10s with r1.321.

Comment 21

[Attila Szegedi]

(In reply to comment #18)
> The 2x slowdown appears with rev 1.321 of Interpreter.java (when adding support
> for generators). Is the interpretLoop method now too large for some HotSpot
> optimisations to happen ?
> 

This is really weird. There's nothing apparent here that'd trigger this sort of a slowdown. I don't think it's a HotSpot deficiency. It rather sounds like a CPU cache overflow. What CPU and OS are you testing on? Also, are you just switching Interpreter.java between runs, or moving the date timestamp of your whole local CVS copy to match those revisions?

Comment 22

[Christophe Grand]

Pentium M 1.73GHz / XP SP 2 / Sun JDK 1.6
I also thought about bad cache misses.

With the CVS HEAD I've got the slowdown. Bringing back my whole working CVS copy down to 2007-06-06 I've got the slowdown. One day earlier, hallelujah, "full" speed. So I diff'd the two versions til I noticed that commenting out the three new cases in interpretLoop does the trick (or replacing Interpreter.java as a whole).

FYI Intepreter.class is (1.320) 64372 bytes long and 66682 bytes long in 1.321... there's 64K in between...

Comment 23

[Attila Szegedi]

(In reply to comment #22)
> Pentium M 1.73GHz / XP SP 2 / Sun JDK 1.6
> I also thought about bad cache misses.

Any idea what's your CPU L1 and L2 cache size?

> With the CVS HEAD I've got the slowdown. Bringing back my whole working CVS
> copy down to 2007-06-06 I've got the slowdown. One day earlier, hallelujah,
> "full" speed. So I diff'd the two versions til I noticed that commenting out
> the three new cases in interpretLoop does the trick (or replacing
> Interpreter.java as a whole).
> 
> FYI Intepreter.class is (1.320) 64372 bytes long and 66682 bytes long in
> 1.321... there's 64K in between...

Yep, although that shouldn't matter, really. There's a limitation that a single method can't exceed 64K in bytecode, but that's all... Okay, I'll try to run the tests on hardware available to me: a MacBook Pro with Intel Core Duo and an iMac G5 -- two radically different architectures. Will be curious what'll happen.

Comment 24

[Christophe Grand]

L1: 32kB/32kB (instruction/data)
L2: 2MB

I just tried to take Interpreter.java 1.321 and to extract some methods from somes cases of the big switch in interpretLoop... And I get the good perfs.

Comment 25

[Christophe Grand]

I just ran the test on AMD Turion X2 TL-56 (L1 : 2x128k; L2 : 2x512k) / Vista + JRE 1.6:
with 1.7pre1 and 1.6R7 from ftp.mozilla.org: 1.7 is 4x slower (14s vs 3.5s) than 1.6r7!

Comment 26

[Christophe Grand]

Running the jvm in interpreter mode (java -Xint) results in 1.7pre1 being faster than 1.6R7. It may be a CPU instruction cache problem: is the jitted code inside the loop too large? ("keep your loops tight" :-))

Comment 27

[Norris Boyd]

I just checked in code for concat. 54X speed improvement.

As far as the interpreter speed issue, sounds like it would be worth factoring some code out of the interpreter loop, perhaps into ScriptRuntime. Christophe, did you have some suggested code to move elsewhere?

Comment 28

[Christophe Grand]

Attachment: Dense array optimization for indexOfHelper. 4x improvement.

I got a 4x improvement with this perf test:

var a = [];
for (var i=0; i < 10000; i++) {
  a[i] = i;
}
var d = new Date();
for (var i=0; i < 1000; i++) {
  a.indexOf(9999);
  a.lastIndexOf(0);
}
print((new Date()) - d);

Comment 29

[Christophe Grand]

Optimizing iterativeMethod for dense arrays seems to lead no gain: the iteration cost is negligible compared to the function invocations cost.
Furthermore iterativeMethod suffers from the interpretLoop slowdown. It may be interesting to give another try at iterativeMethod once interpretLoop fixed.

FYI I used this test:

var a = [];
for (var i=0; i < 10000; i++) {
  a[i] = i;
}
function allTrue() {
  return true;
}
function allFalse() {
  return false;
}

var d = new Date();
for (var i=0; i < 100; i++) {
  a.every(allTrue);
  a.some(allFalse);
  a.map(allTrue);
  a.filter(allTrue);
  a.filter(allFalse);
}
print((new Date()) - d);

Comment 30

[Christophe Grand]

Concerning the interpreter speed issue, I'll give it a look to see what makes much sense to me to factor out -- during my experiments I extracted code rather randomly.

Comment 31

[Attila Szegedi]

(In reply to comment #29)
> Optimizing iterativeMethod for dense arrays seems to lead no gain: the
> iteration cost is negligible compared to the function invocations cost.
> Furthermore iterativeMethod suffers from the interpretLoop slowdown. It may be
> interesting to give another try at iterativeMethod once interpretLoop fixed.

One thing that struck me with iterativeMethod is that we might want to replace the switch/case in it with a strategy pattern: declare an interface for bodies of respective case statements, and create a new object of an anonymous inner class implementing that interface, then pass it to the iterator loop. That way, we allow the HotSpot to perform optimizations -- it might detect the call site is mostly monomorphic (i.e. code mostly runs foreach) and inline it -- even for a single iteration over a fairly big array. It can do none of these with a switch statement. 

Comment 32

[Christophe Grand]

Attachment: staged interpretLoop

Okay: here is a quick and dirty hack of interpretLoop. It leads to 4x speed improvement on the sort perf test and a 2x on iterativeMethod test.

(So, with my patch for using Arrays.sort and Comparator, we get an overall 8x on sort (4x compared to 1.6r7).)

I have extracted in interpretLoopCore the handling of all the simple opcodes (ie: no control flow opcodes, no register loading opcodes).

BTW what I mean by "dirty":
	private static int interpretLoopCore(Context cx, final CallFrame frame, final Object DBL_MRK, final Object undefined, final boolean instructionCounting, final int INVOCATION_COST, String stringReg, int indexReg, Object[] stack, double[] sDbl, Object[] vars, double[] varDbls, byte[] iCode, int stackTop, int op)

There's some obvious clean up to do :-)

Is it okay with you to continue in this way?

Comment 33

[Christophe Grand]

(In reply to comment #31)
> One thing that struck me with iterativeMethod is that we might want to replace
> the switch/case in it with a strategy pattern: declare an interface for bodies
> of respective case statements, and create a new object of an anonymous inner
> class implementing that interface, then pass it to the iterator loop. That way,
> we allow the HotSpot to perform optimizations -- it might detect the call site
> is mostly monomorphic (i.e. code mostly runs foreach) and inline it -- even for
> a single iteration over a fairly big array. It can do none of these with a
> switch statement. 

I thought of it but didn't give it a try because I benchmarked a (faulty) iterativeMethod without anything inside the loop except the method call and there was no difference. It was before I modified Interpreter.java. Must retry...

Comment 34

[Norris Boyd]

Thanks...

Here are my quick numbers on the iterativeMethod timing test (see comment #29):
1.6R7: 5831
1.7R1pre: 15668
1.7R1pre with patch from comment #32: 6713

I'm concerned about the call overhead for invoking interpretLoopCore in the inner loop. I tried adding looping in interpretLoopCore, and that got the numbers down into the 6500's, but still well above the 5800's from 1.6R7. 

I'll look at it some more.

Comment 35

[Norris Boyd]

As an additional datapoint, I ran a comparison between the current sources and 1.6R7, but with -Xint option that disables any compilation/jitting in the JVM. The two timings are very close, so Christophe is right that it has to do with something not working for us in compilation with the JVM.

[rhino] java -Xint -jar build/rhino1_7R1pre/js.jar -opt -1 iterativeMethod.js 79574
[rhino] java -Xint -jar /home/norris/rhino/mozilla/js/rhino/build/rhino1_6R7/js.jar -opt -1 iterativeMethod.js
78910

Comment 36

[Christophe Grand]

Attachment: Rhino 1.7 -XX:+PrintCompilation trace

Comment 37

[Christophe Grand]

Attachment: Rhino 1.6R7 -XX:+PrintCompilation trace

Comment 38

[Christophe Grand]

I ran the tests on the sun server jvm with -XX:+PrintCompilation to trace the jitting.

Now it's clear that it's not a cache problem: interpretLoop don't get jitted anymore.

Comment 39

[Norris Boyd]

Thanks--using -XX:+PrintCompilation is an easy way to see the problem. Using that approach, I played around with pulling pieces out of interpretLoop until it was jitted again. I've committed those changes:

Checking in Interpreter.java;
/cvsroot/mozilla/js/rhino/src/org/mozilla/javascript/Interpreter.java,v  <--  Interpreter.java
new revision: 1.340; previous revision: 1.339
done

I'm marking this bug FIXED now, as all the original array methods have been
optimized or at least examined and determined that a dense array specialization
likely wouldn't make much difference.