781439 - decrease running time of Environment-find-06.js

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

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.

Comment 1

[Luke Wagner [:luke]]

Any thoughts Jim or Jason?

Comment 2

[Jim Blandy :jimb]

I'd love to speed that one up a bit. I also run it frequently.

Comment 3

[Jim Blandy :jimb]

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.

Comment 4

[Jim Blandy :jimb]

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.

Comment 5

[Luke Wagner [:luke]]

Holy moly, I had no idea slotCount() wasn't O(1).  That assertion seems redundant since setSlot will assert (probably using slotSpan).

Comment 6

[Jim Blandy :jimb]

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.

Comment 7

[Jim Blandy :jimb]

Try: https://tbpl.mozilla.org/?tree=Try&rev=59f7071cbbdf
[will attach patch in a sec]

Comment 8

[Jim Blandy :jimb]

Attachment: Trim js/src/jit-test/tests/debug/Environment-find-06.js, and remove assertions.

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.

Comment 9

[Luke Wagner [:luke]]

Thanks!

Comment 10

[Jim Blandy :jimb]

https://hg.mozilla.org/integration/mozilla-inbound/rev/4030896316bd

Comment 11

[Graeme McCutcheon [:graememcc]]

https://hg.mozilla.org/mozilla-central/rev/4030896316bd