912079 - SuppressDeletedPropertyHelper is very slow for objects with many properties

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

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);

Comment 1

[Jan de Mooij [:jandem]]

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.

Comment 2

[Luke Wagner [:luke]]

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.

Comment 3

[Jan de Mooij [:jandem]]

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?

Comment 4

[Luke Wagner [:luke]]

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?

Comment 5

[Jan de Mooij [:jandem]]

(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..

Comment 6

[Jan de Mooij [:jandem]]

Bah, I forgot about this bug, but there's some really dumb stuff here that we can easily optimize without rewriting the iterator code.

Comment 7

[Jan de Mooij [:jandem]]

Attachment: Part 1 - Remove SuppressDeletedPropertyHelper predicate

SuppressDeletedPropertyHelper is only called with SingleStringPredicate nowadays so we can just inline that.

Comment 8

[Jan de Mooij [:jandem]]

Attachment: Part 2 - Simplify SuppressDeletedPropertyHelper

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.

Comment 9

[Jan de Mooij [:jandem]]

Attachment: Part 3 - Add fast path for atoms

Instead of calling EqualStrings, take advantage of the fact that usually both strings are atoms.

Comment 10

[Jan de Mooij [:jandem]]

Attachment: Part 4 - Optimize common case

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

Comment 11

[André Bargull [:anba]]

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".

Comment 12

[André Bargull [:anba]]

Comment on attachment 8970876 [details] [diff] [review]
Part 4 - Optimize common case

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

Nice speed-up!

Comment 13

[Jan de Mooij [:jandem]]

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 :)

Comment 14

[Pulsebot]

Pushed by [e-mail]:
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

Comment 15

[Stefan Hindli [:stefan_hindli]]

https://hg.mozilla.org/mozilla-central/rev/083e48663622
https://hg.mozilla.org/mozilla-central/rev/826aeeda8a92
https://hg.mozilla.org/mozilla-central/rev/acf9cda9b84d
https://hg.mozilla.org/mozilla-central/rev/ac68dde79189