Closed Bug 912079 Opened 6 years ago Closed 2 years ago

SuppressDeletedPropertyHelper is very slow for objects with many properties

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla61
Tracking Status
firefox61 --- fixed

People

(Reporter: jandem, Assigned: jandem)

References

(Blocks 1 open bug)

Details

Attachments

(4 files)

The benchmark in bug 856128 creates an object with a ton of properties and uses it as a hashmap. It has a delete expression (DELELEM) inside a for-in loop. This delete is executed about 45000 times but the problem is that we have > 90 million (!) calls to EqualStrings from SuppressDeletedPropertyHelper.

For the micro-benchmark below I get:

d8 :   17 ms
js : 3621 ms

function f(o) {
    for (var p in o)
	delete o[p];
}
var o = {};
for (var i = 0; i < 40000; i++)
    o[i + " " + i] = i;
var t0 = new Date;
f(o);
print(new Date - t0);
The problem is that if we have:

    for (var p in o)
	delete o[p];

SuppressDeletedPropertyHelper starts looking for p after the current property. I think we should fast-path this case since it's probably pretty common.
When dvander was fixing the enumerator stack crashes he pointed out that v8 implemented property iteration by just iterating over the shapes (maps/hidden-classes) which would be faster (esp. in the case where we didn't hit the native iterator cache), didn't require this 'enumerator' stack and all the sadness it entails, and was able to avoid SupressDeletedProperty.
Thanks, I found bug 839726. Fixing that may be a good idea; for-in is pretty common and iteration perf even matters a bit for SS (looking at you, string-fasta). What do you think, is fixing bug 839726 worth it?
Fixing a perf cliff, improving SS, and removing a footgun seems like a nice reason.  I just did a quick test and for the simple loop:

  for (var p in o)
    s += o[p];

Ion is almost 2x slower than V8.  Do you think bug 839726 would close the gap?
(In reply to Luke Wagner [:luke] from comment #4)
> Ion is almost 2x slower than V8.  Do you think bug 839726 would close the
> gap?

It depends. The first part is removing compartment->enumerators and SuppressDeletedProperty, but this will require an extra shape guard for for-in. When this shape guard fails, we will have to call into the VM. 

What V8 does in this case is that the baseline compiler calls FILTER_KEY, which calls %HasProperty. Crankshaft just bails out when this check fails. I'm not entirely sure, but I think they don't update their "expected map": once the map changes, all other iterations will do an explicit HasProperty. This may still be faster and simpler than what SuppressDeletedPropertyHelper does though.

This part would make for-in slightly slower (though I doubt the extra shape check matters much), but it would fix this bug I think and remove a lot of complexity.

The second part of bug 839726 is removing the snapshot mechanism entirely and using the shapes directly. That should speed up your for-in micro-benchmark and SS string-fasta if we can make it work..
Assignee: general → nobody
Bah, I forgot about this bug, but there's some really dumb stuff here that we can easily optimize without rewriting the iterator code.
Assignee: nobody → jdemooij
Status: NEW → ASSIGNED
SuppressDeletedPropertyHelper is only called with SingleStringPredicate nowadays so we can just inline that.
Attachment #8970870 - Flags: review?(andrebargull)
Attachment #8970870 - Flags: review?(andrebargull) → review+
This adds a helper function so we can more easily get rid of the goto and simplify the control flow. I also did some minor clean up: converting comments to //, dedenting the code inside the loop.
Attachment #8970873 - Flags: review?(andrebargull)
Instead of calling EqualStrings, take advantage of the fact that usually both strings are atoms.
Attachment #8970874 - Flags: review?(andrebargull)
Optimization for this case:

  for (var p in o)
      delete o[p];

For the micro-benchmark in comment 0:

before:       2914 ms
after part 3:  933 ms
after part 4:   11 ms
d8:             11 ms
Attachment #8970876 - Flags: review?(andrebargull)
Comment on attachment 8970873 [details] [diff] [review]
Part 2 - Simplify SuppressDeletedPropertyHelper

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

::: js/src/vm/Iteration.cpp
@@ +1198,5 @@
>      }
>  }
>  
> +static bool
> +SuppressDeletedProperty(JSContext* cx, NativeIterator* ni, HandleObject obj,

I had hoped for SuppressDeletedPropertyHelperHelper. ;-)

@@ +1233,5 @@
> +                if (desc.object() && desc.enumerable())
> +                    continue;
> +            }
> +
> +            // If GetPropertyDescriptorById above removed a property from

Nit, pre-existing: "GetPropertyDescriptorById" -> "GetPropertyDescriptor".
Attachment #8970873 - Flags: review?(andrebargull) → review+
Attachment #8970874 - Flags: review?(andrebargull) → review+
Comment on attachment 8970876 [details] [diff] [review]
Part 4 - Optimize common case

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

Nice speed-up!
Attachment #8970876 - Flags: review?(andrebargull) → review+
Thanks for the reviews!

(In reply to André Bargull [:anba] from comment #11)
> > +SuppressDeletedProperty(JSContext* cx, NativeIterator* ni, HandleObject obj,
> 
> I had hoped for SuppressDeletedPropertyHelperHelper. ;-)

Heh, I did consider it :)
Pushed by jandemooij@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/083e48663622
part 1 - Remove SuppressDeletedPropertyHelper predicate argument. r=anba
https://hg.mozilla.org/integration/mozilla-inbound/rev/826aeeda8a92
part 2 - Clean up SuppressDeletedPropertyHelper. r=anba
https://hg.mozilla.org/integration/mozilla-inbound/rev/acf9cda9b84d
part 3 - Don't call EqualStrings if both strings are atoms. r=anba
https://hg.mozilla.org/integration/mozilla-inbound/rev/ac68dde79189
part 4 - Optimize SuppressDeletedPropertyHelper when the property matches the iterator's previous one. r=anba
You need to log in before you can comment on or make changes to this bug.