101964 - Performance: truncating arrays is slow in SpiderMonkey

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect, P3)

Description

[Phil Schwartau]

Try this in the JS shell:

var BIG = 10000000; 
var arr = Array(BIG);
arr.length = 10; 
for (var i=0; i<arr.length; i++) {print(i)}


The larger you make the variable BIG, the longer it takes this
program to execute. For the value I have put above, it takes 
several seconds. 

Simple debugging shows the time is taken on the last line of 
the program, not line 2 where the big array is created. I wouldn't
expect the execution of the last line to depend on what BIG is. 

Compare: in Rhino, it doesn't matter what the value of BIG is; 
the program always takes the same time to execute.

Comment 1

[Phil Schwartau]

Similar problem in SpiderMonkey if you access arr.toString() after truncation:

var BIG = 1000000000; 
var arr = Array(BIG);
arr.length = 10; 
print(arr.toString());

The time it takes to execute the last line depends on the value
of BIG in the first line -

Comment 2

[Phil Schwartau]

I'm assuming this issue is a separate issue from bug 101488, 
"Array(m).length = new Number(n) failing (silently)"

Comment 3

[Phil Schwartau]

Strange - when I have this testcase in a FILE, and load it in the JS shell,
all the time in SpiderMonkey seems to be taken at the BEGINNING: creating
and truncating the array, rather than in the last step.

Again, this differs from the behavior exhibited by Rhino, where the test
always executes quickly, whether it is interactive or loaded from a file -

Comment 4

[Phil Schwartau]

My mistake - however you try the testcase, all the time is taken up by the 
truncation step:

                     arr.length = 10;

It is this step which takes longer and longer as BIG is increased.
I don't know how but in my interactive test, my debugging code
must have been in the wrong spot.

Resummarizing and keeping bug open, since this performance compares
unfavorably with Rhino -

Comment 5

[Kenton Hanson (gone)]

the following code is where the time is being spent.  I'll examine it more 
closely.


static JSBool
array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
{
    jsuint newlen, oldlen, slot;
    jsid id2;
    jsval junk;

    if (!ValueIsLength(cx, *vp, &newlen))
	return JS_FALSE;
    if (!js_GetLengthProperty(cx, obj, &oldlen))
	return JS_FALSE;
    for (slot = newlen; slot < oldlen; slot++) {
	if (!IndexToId(cx, slot, &id2))
	    return JS_FALSE;
	if (!OBJ_DELETE_PROPERTY(cx, obj, id2, &junk))
	    return JS_FALSE;
    }
    return IndexToValue(cx, newlen, vp);
}

Comment 6

[Phil Schwartau]

Testcase added to JS testsuite:

        mozilla/js/tests/js1_5/Array/regress-101964.js

Currently it's hard-coded to expect its array truncation to take
no more than 50 ms. Anything longer and the test will fail.

Testcase is currently passing in the rhino and rhinoi shells,
failing in the smdebug and smopt shells -

Comment 7

[Kenton Hanson (gone)]

This performance bug while valid, will probably not be found in performance
critical programs. 

Comment 8

[Phil Schwartau]

Reopening bug for consideration in JS1.5 final release.

I agree with Kenton that this is not critical, yet I'm wondering
if there might be a not-too-hard fix for this that we could get in.

The testcase for this bug is failing. In the optimized JS shell:

Testcase js1_5/Array/regress-101964.js failed Bug Number 101964
STATUS: Performance: truncating very large arrays should be fast!
Failure messages were:
FAILED!: Expected value 'Truncation took less than 50 ms',
         Actual value 'Truncation took 5656 ms'


I will attach an HTML version of this testcase. Here are the
timings (in ms) I get on WinNT(SP6) 500MHz 128M:

IE6       0
NN4    6900 
Moz    6700
JS opt 5656
Rhino  < 50

Comment 9

[Phil Schwartau]

Attachment: HTML testcase

Comment 10

[Brendan Eich [:brendan]]

Taking for 1.5

/be

Comment 11

[Brendan Eich [:brendan]]

Blake, would you be willing to take this too?  It goes along with bug 322889.

/be

Comment 12

[Gabriel Sjoberg]

Attachment: Possible fix

Here's a patch that pulls the essential functionality out of the loop in array_length_setter().  Runtime for the testcase drops from 1600ms to 0ms on my 2.4GHz WinXP box.

I checked for memory leaks, and this change doesn't appear to leak anything.

This is my first patch ever, so please be nice if I'm waaaay off base here.

Comment 13

[Brendan Eich [:brendan]]

Comment on attachment 214407 [details] [diff] [review]
Possible fix

What is this patch doing?  It seems to be using a JSJMSG_* constant from liveconnect/*.msg, and it tests for ECMA version in order to throw an exception if non-ECMA, otherwise it doesn't truncate the array.  None of that is right.  Can you say why you wrote it like this?

/be

Comment 14

[Gabriel Sjoberg]

First, I searched for what I thought was the property deletion method that actually gets called from this method (JavaArray_deleteProperty() in jsj_JavaArray.c).  It didn't appear that that method actually deletes anything; it just does the same check that I pulled into array_length_setter().  When I test the size of the array after calling the modified array_length_setter, it does come back as the properly truncated size.  I figured that we just drop the reference to the memory and trust the garbage collector to clean it up.

This seemed a little simplistic to me and I figured it was wrong, but I wanted to try my hand at an easy bug first.  Can you give me a shove in the right direction?

Comment 15

[Gabriel Sjoberg]

Attachment: Patch v2

Upon further review, the earlier patch doesn't compile (I found that I actually compiled with an intermediate version).  Here's the patch I actually compiled with.

Comment 16

[Brendan Eich [:brendan]]

Sorry to say the patches show confusion about very basic stuff:

* JavaScript Array is implemented by js/src/jsarray.c and has nothing to do with java.lang.Array or any such thing.

* js/src/liveconnect is an optional module bridging JS and Java, js/src/js*.[ch] must not include its error message codes.

* The truncation that takes too long with this bug is really required by ECMA-262.  We just need to speed up our implementation, not remove the truncation code and violate ECMA. 

Please read http://www.mozilla.org/js/language/E262-3.pdf section 15.4.5.1, step 14 in particular.

/be

Comment 17

[Brendan Eich [:brendan]]

Igor, you have "dibs" on this bug.  I would be happy to review and advise.

/be

Comment 18

[Igor Bukanov]

(In reply to comment #17)
> Igor, you have "dibs" on this bug.  I would be happy to review and advise.

Ok, I will have a look after fishing in xml pond stops to bring a catch. 

Comment 19

[Brian Crowder]

Setting the lower bound in array_length_setter from (1<<24) to (1<<16) fixes this bug.  It seems like the algorithm in the "else" clause here would be superior for even much smaller arrays, and perfectly acceptable even for tiny arrays.  What is the justification for not using it all the time?

Comment 20

[Igor Bukanov]

I am not working on the bug right now.

Comment 21

[Bob Clary [:bc] (inactive)]

I show this passing on 1.9.0, 1.9.1