Closed Bug 781439 Opened 7 years ago Closed 7 years ago

decrease running time of Environment-find-06.js

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla18

People

(Reporter: luke, Assigned: jimb)

Details

(Whiteboard: [js:t])

Attachments

(1 file)

Environment-find-06.js takes 36s in a debug build.  Could we decrease the runtime of tests/debug/Environment-find-06.js (perhaps shortening manyNames) while maintaining the value of this test?  I run the whole suite several times a day, so this would be very helpful.
Any thoughts Jim or Jason?
Whiteboard: [js:t]
I'd love to speed that one up a bit. I also run it frequently.
This patch cuts the test's run time in half:

--- a/js/src/vm/ScopeObject-inl.h
+++ b/js/src/vm/ScopeObject-inl.h
@@ -129,14 +129,14 @@ BlockObject::localIndexToSlot(const Bind
 inline const Value &
 BlockObject::slotValue(unsigned i)
 {
-    JS_ASSERT(i < slotCount());
+    // JS_ASSERT(i < slotCount());
     return getSlotRef(RESERVED_SLOTS + i);
 }
 
 inline void
 BlockObject::setSlotValue(unsigned i, const Value &v)
 {
-    JS_ASSERT(i < slotCount());
+    // JS_ASSERT(i < slotCount());
     setSlot(RESERVED_SLOTS + i, v);
 }

Valgrind says that slotCount is calling JSObject::propertyCount, which calls js::Shape::entryCount, which is iterating over the properties to find the count.
What's going on here is that we have StaticBlockObjects and BlockObjects with 4000 properties, but that are not in dictionary mode. The calls to slotCount in the assertions probably produce quadratic behavior when one calls slotValue in a loop, checking the value of each property.
Holy moly, I had no idea slotCount() wasn't O(1).  That assertion seems redundant since setSlot will assert (probably using slotSpan).
Yes, setSlot and getSlotRef do use slotSpan.

I tried replacing slotCount() with slotSpan (with an appropriate check for the empty shape), but it still wasn't happy: it seems to be used at compile time when the StaticBlockObjects are in some weird half-constructed state that I don't understand. It seems like usage patterns like this should cause the static block's shape to get a hash (this can be done without placing it in dictionary mode, so that BlockObjects and their StaticBlockObjects can still share shapes), but I wasn't able to see how to fit hashify in with the code I saw.

I suspect that we will find many more examples of quadratic behavior in the debug code as time goes by. It would be nice to address them; a good tool should be robust in situations like this.
Try: https://tbpl.mozilla.org/?tree=Try&rev=59f7071cbbdf
[will attach patch in a sec]
slotCount() is O(n) on BlockObjects, so that, when used from a loop, those
assertions brought about quadratic behavior. The test creates 'let' blocks
with thousands of bindings, making the quadratic behavior show.

The assertions are unnecessary, as getSlotRef and setSlot do their own
bounds checking. I believe the test can be just as effective with smaller
'let' blocks.
Assignee: general → jimb
Status: NEW → ASSIGNED
Attachment #661936 - Flags: review?(luke)
Attachment #661936 - Flags: review?(luke) → review+
Thanks!
https://hg.mozilla.org/integration/mozilla-inbound/rev/4030896316bd
Flags: in-testsuite-
Target Milestone: --- → mozilla18
https://hg.mozilla.org/mozilla-central/rev/4030896316bd
Status: ASSIGNED → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.