433336 - array iteration optimization

Status: RESOLVED INVALID

(Core :: JavaScript Engine, defect, P3)

Description

[Robert Sayre]

Avoid allocating bitmap during array enumeration for arrays without holes.

Comment 1

[Damon Sicore (:damons)]

Adding this to the 1.9.1 triage queue by marking this wanted1.9.1?.  

Comment 2

[Graydon Hoare :graydon]

As far as I can tell, the code in array_enumerate does not allocate a bitmap when there are no holes. It allocates only the prefix of the iteration structure before the bitmap. So I do not think there is a bug to fix here. Anyone care to confirm?

Comment 3

[Mike Shaver (:shaver emeritus)]

Sorry, I misspoke to sayrer when he kindly volunteered to file this bug.  I propose to skip the loop if COUNT == LENGTH, so that we don't iterate over large, dense arrays an extra time.

Comment 4

[Mike Shaver (:shaver emeritus)]

(This also requires auditing the code to make sure that we propagate COUNT correctly when slice and splicing and so forth!)

Comment 5

[Graydon Hoare :graydon]

Attachment: patch implementing count==length fast path

Possibly you mean a patch like this, then? It appears to work but only looks like it buys pebbles of speed in sunspider (~ 0.1%, if I am counting guest instructions on valgrind) 

Not sure this matters. Maybe I should test a pathological case?

Comment 6

[Mike Shaver (:shaver emeritus)]

Comment on attachment 330674 [details] [diff] [review]
patch implementing count==length fast path

You know that there are holes if you get into the else, so you can just allocate ii up front in that block.  Not surprised it's not much of a speed win on sunspider's smallish arrays (do they even enumerate arrays directly anywhere? that would be awfully JS-y!), and indeed it might not be worthwhile.

Comment 7

[Graydon Hoare :graydon]

Attachment: update to patch

Right. So ... patch updated as you suggest, and tested against a pathological case such as:

var k = 100000;
var arr = new Array();
for (i = 0; i < k; ++i) arr.push(i);
function f() { for (i in arr) { if (i > 10) break; } }
for (j = 0; j < 100; ++j) f();

we do, indeed, see guest instructions executed drop from 167 million to 77 million. Nice enough. What counts as "auditing" the mutator functions? I can just read every function in the file...

Comment 8

[Graydon Hoare :graydon]

Fwiw I have now read the file end to end looking for mutators that do not eventually funnel into a function that appropriately balances COUNT, and cannot find any. Most seem to delegate to InitArrayObject, SetArrayElement or DeleteArrayElement, and those that don't seem to do their own book-keeping. 

I can also try playing with dehydra to prove this, though :)

Comment 9

[Mike Shaver (:shaver emeritus)]

Comment on attachment 330806 [details] [diff] [review]
update to patch

I'm a shamefully bad reviewer; apologies for letting this work rot on the vine. :-(  Moving to njn for him to figure out if it's still meaningful.

Comment 10

[Nicholas Nethercote [inactive]]

(In reply to comment #9)
> (From update of attachment 330806 [details] [diff] [review])
> I'm a shamefully bad reviewer; apologies for letting this work rot on the vine.
> :-(  Moving to njn for him to figure out if it's still meaningful.

This patch is older than my daughter, and she can walk, feed herself, and -- as of last weekend -- use the slides at our local playground unassisted.

It's rotted so badly I had trouble finding identifiers mentioned in it that still exist in jsarray.cpp other than JS_TRUE and JS_FALSE.  All of the following are gone: array_enumerate(), JSIndexIterState, JS_BITMAP_SIZE, hasHoles.

So I'm closing it as INVALID.  But since it involves the words "array" and "iteration" I'll CC gal to give him a chance to resurrect the idea, if not the code, in case it is still relevant.

Comment 11

[Andreas Gal :gal]

I ripped out the code in question. This bug is dead indeed. RIP.