Optimize Object.values() and Object.entries() and let them ride the trains

RESOLVED FIXED in Firefox 47

Status

()

RESOLVED FIXED
3 years ago
a year ago

People

(Reporter: till, Assigned: till)

Tracking

(Depends on: 1 bug, Blocks: 1 bug, {dev-doc-complete})

Trunk
mozilla47
dev-doc-complete
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox46 affected, firefox47 fixed)

Details

Attachments

(1 attachment, 1 obsolete attachment)

(Assignee)

Description

3 years ago
These functions are currently not enabled for release builds because they're atrociously slow. We should change that somewhat soon.

One way to go about this is to fix the remaining bugs blocking this one and keeping the self-hosted implementation. Another is to change the implementation of Object.keys() to use the same underlying algorithm the spec uses, which would allow sharing it among keys, values, and entries. Then we'd just get rid of the self-hosted implementations and use native ones (or one templated native one) for all three.
Keywords: dev-doc-needed
(Assignee)

Comment 1

3 years ago
Turns out the second of comment 0's proposed ways to speed these up is way easier than the first. Object.values is faster than Object.keys now (by about 25%) because it doesn't need to stringify the keys. Object.entries is still a lot (8x) slower, but I'm not sure much can be done about that: it has to create lots of arrays. Perhaps a template object would speed this up, not sure.

This patch also removes the non-release-build restriction because the performance was the only thing keeping this from riding the trains.
Attachment #8708993 - Flags: review?(jorendorff)
(Assignee)

Updated

3 years ago
Assignee: nobody → till
Status: NEW → ASSIGNED
Comment on attachment 8708993 [details] [diff] [review]
Implement Object.{values,entries} in C++ to avoid native call overhead in tight loop

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

r=me. Thanks!

::: js/src/builtin/Object.cpp
@@ +733,5 @@
> +        }
> +
> +        // Step 4.a.ii.1.
> +        if (kind == Keys) {
> +            properties[i - skipped].set(key);

It seems clearer to me to have

    size_t out = 0;
    for (size_t i = 0; i < len; i++) {
        ...
        properties[out++].set(key);
    }

instead of decrementing something called `skipped` and doing extra subtractions. Only change it if you agree.

@@ +766,5 @@
>  static bool
>  obj_keys(JSContext* cx, unsigned argc, Value* vp)
>  {
>      CallArgs args = CallArgsFromVp(argc, vp);
> +    return EnumerableOwnProperties(cx, args, Keys);

As discussed on IRC, it's surprising that the new code is not a whole lot slower than the old code, so a little more perf-testing is in order.

r=me if my hunch turns out to be right and you want to revert to the old code.

The GetProperty can be avoided too, for data properties on native objects, if we need to make Object.values() faster... but that's a separate patch.
Attachment #8708993 - Flags: review?(jorendorff) → review+
(Assignee)

Comment 3

3 years ago
You were so very right about the performance issues :(

I changed Object.keys() back to the old implementation, and rewrote the loop in EnumerableOwnProperties to re-gain as much performance as was reasonably easy to do. For large dict-mode objects, Object.values() is about 4x slower than Object.keys(). For dense indexed objects, it's still about 2.5x as fast. Object.entries() has all the overhead of .values plus the creation of the entry arrays, so it sucks.

To make Object.values() really fast, I guess we'd have to duplicate pretty much all of Snapshot and EnumerateNativeProperties, or change both of them to optionally also get values. Both options are somewhat annoying, so perhaps let's wait until anything warrants doing this?
Attachment #8711500 - Flags: review?(jorendorff)
(Assignee)

Updated

3 years ago
Attachment #8708993 - Attachment is obsolete: true
(In reply to Till Schneidereit [:till] from comment #3)
> perhaps let's wait until anything warrants doing this?

Indeed. Reviewing now.
Comment on attachment 8711500 [details] [diff] [review]
Implement Object.{values,entries} in C++ to avoid native call overhead in tight loop. v2

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

How good are our existing tests? If we don't have tests confirming that the order of operations is correct on Proxies, please add a few.

::: js/src/builtin/Object.cpp
@@ +684,5 @@
> +    KeysAndValues
> +};
> +
> +// ES7 proposal 2015-12-14
> +// http://tc39.github.io/proposal-object-values-entries/#EnumerableOwnProperties

Now that there are no longer periodic drops, we should rethink how we do this. A single URL that points to a specific revision (assuming github offers that) would be better than the combination of date and URL you have here.

@@ +717,5 @@
> +    // Step 4.
> +    size_t out = 0;
> +    for (size_t i = 0; i < len; i++) {
> +        id = ids[i];
> +        // Step 4.a. (Symbols were filtered out in step 2.)

Style nit: blank line before comment, please
Attachment #8711500 - Flags: review?(jorendorff) → review+
(Assignee)

Comment 6

3 years ago
https://hg.mozilla.org/integration/mozilla-inbound/rev/6eaaef0677d4000359a26445aec25016273a2d46
Bug 1232639 - Implement Object.{values,entries} in C++ to avoid native call overhead in tight loop. r=jorendorff
(Assignee)

Comment 7

3 years ago
This took ridiculously long :(

(In reply to Jason Orendorff [:jorendorff] from comment #5)
> How good are our existing tests? If we don't have tests confirming that the
> order of operations is correct on Proxies, please add a few.

I'd say they're decent. They definitely cover the order of operations, for one.

> > +// ES7 proposal 2015-12-14
> > +// http://tc39.github.io/proposal-object-values-entries/#EnumerableOwnProperties
> 
> Now that there are no longer periodic drops, we should rethink how we do
> this. A single URL that points to a specific revision (assuming github
> offers that) would be better than the combination of date and URL you have
> here.

I asked bterlson and talked about this in #jslang: everyone agrees that permanent links to specific revisions would be nice, but they don't exist, and the way the spec drafts are published (with a script that wipes out the gh-pages history) makes it nontrivial to add them. I left the comment as-is for now, but we should go through and replace all draft spec links once something better is available.

Comment 8

3 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/6eaaef0677d4
Status: ASSIGNED → RESOLVED
Last Resolved: 3 years ago
status-firefox47: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla47
Depends on: 1406398
You need to log in before you can comment on or make changes to this bug.