1405284 - Avoid extra copying of property keys when calling js::GetOwnPropertyKeys

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P3)

Description

[André Bargull [:anba]]

Avoiding the extra copying into AutoValueVector should make GetOwnPropertyKeys a bit faster.

Comment 1

[André Bargull [:anba]]

Attachment: bug1405284.patch

Directly copying the ids into the result array seems to be faster. I've tested this in µ-benchmarks with objects with an increasing number of properties and avoiding AutoValueVector seems to be faster in all cases. 

Drive-by change: NewValuePair is only used in builtin/Object.cpp, so I moved it into that file and also changed it to use NewDenseFullyAllocatedArray instead of NewDenseCopiedArray. This improved Object.entries() µ-benchmarks a little bit (<5%).

Comment 2

[André Bargull [:anba]]

Comment on attachment 8914716 [details] [diff] [review]
bug1405284.patch

I see cgc crashes with this patch, clearing review for now:


Thread 1 "js" received signal SIGSEGV, Segmentation fault.
0x0000000000470ef3 in js::gc::detail::GetCellLocation (cell=<optimized out>) at /home/andre/hg/mozilla-inbound/js/src/build-cgc-debug-obj/dist/include/js/HeapAPI.h:382
382         return *reinterpret_cast<ChunkLocation*>(addr);

(gdb) bt 
#0  0x0000000000470ef3 in js::gc::detail::GetCellLocation (cell=<optimized out>) at /home/andre/hg/mozilla-inbound/js/src/build-cgc-debug-obj/dist/include/js/HeapAPI.h:382
#1  js::gc::IsInsideNursery (cell=<optimized out>) at /home/andre/hg/mozilla-inbound/js/src/build-cgc-debug-obj/dist/include/js/HeapAPI.h:401
#2  0x0000000000e4d4e2 in js::TenuringTracer::traverse<JSObject> (this=0x7fffffffbc30, objp=0x7fffffffbac0) at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:2671
#3  0x0000000000e6953c in js::TenuringTraversalFunctor<JS::Value>::operator()<JSObject> (this=<synthetic pointer>, trc=0x7fffffffbc30, t=0x48) at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:2678
#4  js::DispatchTyped<js::TenuringTraversalFunctor<JS::Value>, js::TenuringTracer*>(js::TenuringTraversalFunctor<JS::Value>, JS::Value const&, js::TenuringTracer*&&) (f=..., val=...)
    at /home/andre/hg/mozilla-inbound/js/src/build-cgc-debug-obj/dist/include/js/Value.h:1434
#5  0x0000000000e4e639 in js::TenuringTracer::traverse<JS::Value> (thingp=0x7ffff41b4a28, this=0x7fffffffbc30) at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:2687
#6  js::TenuringTracer::traceSlots (end=0x7ffff41b8018, vp=0x7ffff41b4a28, this=0x7fffffffbc30) at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:2931
#7  js::TenuringTracer::traceObject (this=this@entry=0x7fffffffbc30, obj=obj@entry=0x7ffff44c1060) at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:2907
#8  0x0000000000e4ea11 in js::Nursery::collectToFixedPoint (this=this@entry=0x7ffff696cd40, mover=..., tenureCounts=...) at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:2871
#9  0x0000000000e4eeae in js::Nursery::doCollection (this=this@entry=0x7ffff696cd40, reason=reason@entry=JS::gcreason::DEBUG_GC, tenureCounts=...)
    at /home/andre/hg/mozilla-inbound/js/src/gc/Nursery.cpp:792
#10 0x0000000000e51e38 in js::Nursery::collect (this=0x7ffff696cd40, reason=reason@entry=JS::gcreason::DEBUG_GC) at /home/andre/hg/mozilla-inbound/js/src/gc/Nursery.cpp:642
#11 0x00000000009e0a60 in js::gc::GCRuntime::minorGC (this=0x7ffff696a738, reason=JS::gcreason::DEBUG_GC, phase=<optimized out>) at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:7514
#12 0x0000000000a127fc in js::gc::GCRuntime::gcCycle (this=this@entry=0x7ffff696a738, nonincrementalByAPI=nonincrementalByAPI@entry=false, budget=..., reason=reason@entry=JS::gcreason::DEBUG_GC)
    at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:7090
#13 0x0000000000a130b2 in js::gc::GCRuntime::collect (this=this@entry=0x7ffff696a738, nonincrementalByAPI=nonincrementalByAPI@entry=false, budget=..., reason=reason@entry=JS::gcreason::DEBUG_GC)
    at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:7288
#14 0x0000000000a15405 in js::gc::GCRuntime::runDebugGC (this=this@entry=0x7ffff696a738) at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:7908
#15 0x0000000000d6e9b5 in js::gc::GCRuntime::gcIfNeededAtAllocation (this=0x7ffff696a738, cx=cx@entry=0x7ffff697a000) at /home/andre/hg/mozilla-inbound/js/src/gc/Allocator.cpp:230
#16 0x0000000000d7c548 in js::gc::GCRuntime::checkAllocatorState<(js::AllowGC)1> (this=<optimized out>, cx=0x7ffff697a000, kind=js::gc::AllocKind::STRING)
    at /home/andre/hg/mozilla-inbound/js/src/gc/Allocator.cpp:191
#17 0x0000000000d7e8ba in js::Allocate<JSString, (js::AllowGC)1> (cx=0x7ffff697a000, cx@entry=0x7fffffffc377) at /home/andre/hg/mozilla-inbound/js/src/gc/Allocator.cpp:142
#18 0x00000000009c708b in JSThinInlineString::new_<(js::AllowGC)1> (cx=0x7fffffffc377) at /home/andre/hg/mozilla-inbound/js/src/vm/String-inl.h:263
#19 js::AllocateInlineString<(js::AllowGC)1, unsigned char> (chars=<synthetic pointer>, len=<optimized out>, cx=0x7fffffffc377) at /home/andre/hg/mozilla-inbound/js/src/vm/String-inl.h:31
#20 js::NewInlineString<(js::AllowGC)1, unsigned char> (cx=cx@entry=0x7ffff697a000, chars=...) at /home/andre/hg/mozilla-inbound/js/src/vm/String-inl.h:57
#21 0x0000000000a1c609 in js::Int32ToString<(js::AllowGC)1> (cx=0x7ffff697a000, si=323) at /home/andre/hg/mozilla-inbound/js/src/jsnum.cpp:639
#22 0x00000000005b6c7a in js::IdToStringOrSymbol (cx=<optimized out>, id=..., result=..., result@entry=...) at /home/andre/hg/mozilla-inbound/js/src/builtin/Object.cpp:1376
#23 0x00000000005dc64f in js::GetOwnPropertyKeys (cx=cx@entry=0x7ffff697a000, args=..., flags=flags@entry=24) at /home/andre/hg/mozilla-inbound/js/src/builtin/Object.cpp:1414
#24 0x00000000005dc74e in js::obj_getOwnPropertyNames (cx=0x7ffff697a000, argc=<optimized out>, vp=<optimized out>) at /home/andre/hg/mozilla-inbound/js/src/builtin/Object.cpp:1427
...

Comment 3

[André Bargull [:anba]]

(In reply to André Bargull [:anba] from comment #2)
> Comment on attachment 8914716 [details] [diff] [review]
> bug1405284.patch
> 
> I see cgc crashes with this patch, clearing review for now:

Duh, having uninitialized elements reachable during GC is probably not great! :)

Comment 4

[André Bargull [:anba]]

Attachment: bug1405284.patch

I've replaced setDenseInitializedLength+initDenseElement with ensureDenseInitializedLength/setDenseElement to make sure all heap elements are initialised, so a possible GC during IdToStringOrSymbol won't see uninitialised elements. But I'm still a bit confused about the differences between setDenseInitializedLength and ensureDenseElements when used after NewDenseFullyAllocatedArray to create dense elements, because we seem to use both methods interchangeably: 

NewDenseFullyAllocatedArray + setDenseInitializedLength:
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/builtin/TestingFunctions.cpp#3455-3458
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/builtin/TestingFunctions.cpp#3610-3613
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/builtin/TestingFunctions.cpp#3619-3622
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/builtin/TestingFunctions.cpp#3628-3631
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/vm/Debugger.cpp#3858-3861
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/vm/Debugger.cpp#4748-4752
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/vm/Debugger.cpp#4948-4952
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/vm/Debugger.cpp#8978-8982
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/vm/DebuggerMemory.cpp#189-192

NewDenseFullyAllocatedArray + ensureDenseElements:
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/builtin/Promise.cpp#1356-1361
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/builtin/Promise.cpp#3222-3226
http://searchfox.org/mozilla-central/rev/7ba03cebf1dcf3b4c40c85a4efad42a5022cf1ec/js/src/builtin/Promise.cpp#1792-1796


Performance improvements in the following µ-benchmark:

// 0 properties:    170ms -> 150ms   @ 1000000 iterations
// 2 properties:    220ms -> 170ms   @ 1000000 iterations
// 10 properties:   560ms -> 430ms   @ 1000000 iterations
// 100 properties:  245ms -> 235ms   @  100000 iterations
// > 100 properties: negligible differences.

    var properties = 0;
    var iterations = 1000000;
    var a = Array(properties).fill("");
    var o = a.reduce((acc, v, k) => (acc["_" + k] = v, acc), {});
    var q = 0;
    var t = dateNow();
    for (var i = 0; i < iterations; ++i) {
        q += Object.keys(o).length;
    }
    print(dateNow() - t);



I've replaced the drive-by change in NewValuePair with a different drive-by change (because I have another patch which modifies NewValuePair). In fun_enumerate, we can avoid the HasOwnProperty calls to resolve the "name" and "length" properties if we check hasResolvedLength/hasResolvedName. Rational for this change: I'm not sure if fun_enumerate is often called for normal functions, but I can see possible callers of fun_enumerate for ES6 classes, so it shouldn't hurt to make this a bit faster.

Comment 5

[Jan de Mooij [:jandem]]

Comment on attachment 8915616 [details] [diff] [review]
bug1405284.patch

Review of attachment 8915616 [details] [diff] [review]:
-----------------------------------------------------------------

Superb.

::: js/src/builtin/Object.cpp
@@ +1400,2 @@
>              return false;
> +        array->setDenseElement(i, val);

Nit: initDenseElement might be a bit faster (no pre-barrier) and should be okay since the current value is the magic hole value (not a GC thing). r=me either way.

Comment 6

[André Bargull [:anba]]

Attachment: bug1405284.patch

Updated to use initDenseElement per review comment, carrying r+.

Comment 7

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=663007ce1fbf02d4f5a9ed8714917d77aaf97ed0

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b355375f2ab3
Avoid extra copying of property keys when calling js::GetOwnPropertyKeys. r=jandem

Comment 9

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/b355375f2ab3