Closed Bug 433336 Opened 13 years ago Closed 11 years ago

array iteration optimization


(Core :: JavaScript Engine, defect, P3)






(Reporter: sayrer, Assigned: graydon)


(Keywords: perf)


(2 obsolete files)

Avoid allocating bitmap during array enumeration for arrays without holes.
Keywords: perf
Version: unspecified → Trunk
Adding this to the 1.9.1 triage queue by marking this wanted1.9.1?.  
Flags: wanted1.9.1?
Priority: -- → P3
Flags: wanted1.9.1? → wanted1.9.1+
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?
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.
Assignee: shaver → graydon
(This also requires auditing the code to make sure that we propagate COUNT correctly when slice and splicing and so forth!)
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?
Attachment #330674 - Flags: review?(shaver)
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.
Attached patch update to patch (obsolete) — Splinter Review
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...
Attachment #330674 - Attachment is obsolete: true
Attachment #330806 - Flags: review?(shaver)
Attachment #330674 - Flags: review?(shaver)
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 :)
Flags: blocking1.9.2?
OS: Linux → All
Flags: blocking1.9.2? → blocking1.9.2+
Flags: wanted1.9.2+
Flags: blocking1.9.2-
Flags: blocking1.9.2+
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.
Attachment #330806 - Flags: review?(shaver) → review?(nnethercote)
(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.
Closed: 11 years ago
Resolution: --- → INVALID
I ripped out the code in question. This bug is dead indeed. RIP.
Attachment #330806 - Attachment is obsolete: true
Attachment #330806 - Flags: review?(nnethercote)
You need to log in before you can comment on or make changes to this bug.