Object.getOwnPropertySymbols on large list takes very long

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Joseph Pecoraro]

* SUMMARY
Object.getOwnPropertySymbols can take a very long time on an object without Symbols but lots of properties. Other browsers take 0ms.

* TEST
<script>
// Likewise with just a large Array...
var buffer = new ArrayBuffer(10000000);
var int8View = new Int8Array(buffer);
var start = Date.now();
var list = Object.getOwnPropertySymbols(int8View);
var end = Date.now();
console.log("Symbols", list, "Time", end-start);
</script>

* NOTES
- Firefox - 0ms
- Chrome - 0ms
- WebKit - 10703ms

[Yusuke Suzuki]

This is because,

1. Object.getOwnPropertySymbols once create the array contains all symbols / non-symbol names.
2. And filter it in the getOwnPropertySymbols function.

So if there's a lot of names (not-symbol), it produces a large array once.

[Yusuke Suzuki]

Linux `perf report` result.

Samples: 38K of event 'cycles', Event count (approx.): 34269853476
 25.82%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] WTF::HashTable<WTF::StringImpl*, WTF::StringImpl*, WTF::IdentityExtractor, WTF::StringHash, WTF::HashTraits<WTF::StringImpl*>, WTF::HashTraits<WTF::StringImpl*> >::rehash(unsigned int, WTF:
 20.38%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] WTF::equal(WTF::StringImpl const&, WTF::StringImpl const&)
 12.60%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] WTF::HashTableConstIterator<WTF::StringImpl*, WTF::StringImpl*, WTF::IdentityExtractor, WTF::StringHash, WTF::HashTraits<WTF::StringImpl*>, WTF::HashTraits<WTF::StringImpl*> > WTF::HashTabl
 10.98%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] WTF::AtomicStringImpl::addSlowCase(WTF::StringImpl&)
  8.59%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] JSC::JSGenericTypedArrayView<JSC::Int8Adaptor>::getOwnPropertyNames(JSC::JSObject*, JSC::ExecState*, JSC::PropertyNameArray&, JSC::EnumerationMode)
  7.04%  jsc  [kernel.kallsyms]                   [k] 0xffffffff8104f45a
  5.45%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] WTF::HashTable<WTF::UniquedStringImpl*, WTF::UniquedStringImpl*, WTF::IdentityExtractor, WTF::PtrHash<WTF::UniquedStringImpl*>, WTF::HashTraits<WTF::UniquedStringImpl*>, WTF::HashTraits<WTF
  1.24%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] WTF::String::number(unsigned int)
  1.13%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] JSC::Identifier::from(JSC::ExecState*, unsigned int)
  1.03%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] WTF::StringImpl::hashSlowCase() const
  0.81%  jsc  libpthread-2.19.so                  [.] pthread_getspecific
  0.67%  jsc  libc-2.19.so                        [.] __memcpy_sse2_unaligned
  0.59%  jsc  libc-2.19.so                        [.] memset
  0.44%  jsc  libjavascriptcoregtk-4.0.so.18.2.1  [.] JSC::objectConstructorGetOwnPropertySymbols(JSC::ExecState*)


Generating AtomicStringImpl that is used for representing names takes a lot of cost.
Avoiding this when symbols are required makes the performance better.

[Yusuke Suzuki]

Created attachment 257334 [details]
Patch

[Yusuke Suzuki]

OK, the proposed patch makes the JoePeck's example 0ms!

[Yusuke Suzuki]

Created attachment 257337 [details]
Patch

[Yusuke Suzuki]

Created attachment 257338 [details]
Patch

[Yusuke Suzuki]

Created attachment 257339 [details]
Patch

[Yusuke Suzuki]

OK, patch is ready for review.
build-webkit, run-webkit-tests onto js/regress & run-javascriptcore-tests are passed.

[Mark Lam]

Comment on attachment 257339 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=257339&action=review

Looks like you have removed all uses of SymbolPropertiesMode.  You should also remove its definition from EnumerationMode.h.

> Source/JavaScriptCore/ChangeLog:8
> +        Before this patch, Object.getOwnPropertySymbols once collects the all names including strings.

Replace "once collects the all names" with "collects all the names".

> Source/JavaScriptCore/ChangeLog:10
> +        But it's so much time consuming if the given object is a large non-holed array since it has

Replace "it's so much time consuming" with "it's so time consuming".

> Source/JavaScriptCore/ChangeLog:11
> +        many indexed properties and all the properties are once converted to uniqued strings and collected.

Replace "all the properties are once converted to uniqued strings and collected" with "all the indexes have to be converted to uniqued_strings for this one purpose, and then GC'ed thereafter".  I think that's what you meant.  If not, please correct me.

> Source/JavaScriptCore/ChangeLog:35
> +

In this patch, there's a concept in use that is not clear just from reading the code, and hence should be documented here.  That is: when selecting the PropertiesTypeMode for the PropertyNameArray to be instantiated, you applied the following logic:
1. Only JavaScriptCore code is aware of ES6 Symbols.  We can assume that pre-existing external code that interfaces JSC are only looking for string named properties.  This includes:
    a. WebCore bindings
    b. Serializer bindings
    c. NPAPI bindings
    d. Objective C bindings

2. In JSC, code that compute object storage space needs to iterate both Symbol and String named properties.  Hence, use PropertiesTypeMode::Both.
3. In JSC, ES6 APIs that work with Symbols should use PropertiesTypeMode::Symbols.
4. In JSC, ES6 APIs that work with String named properties should use PropertiesTypeMode::Strings.

Please add a comment here to document this reasoning.

> LayoutTests/js/regress/script-tests/object-get-own-property-symbols-on-large-array.js:1
> +function trial()

I think you're expecting this test to not time out.  If so, can you put a comment above to indicate that "This test should not time out"?  Alternatively, you can measure the time it takes to run trial() (using Date.now() before and after) and verify that the delta is less than some generous amount of time ... maybe 1 second?

[Mark Lam]

Comment on attachment 257339 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=257339&action=review

>> Source/JavaScriptCore/ChangeLog:11
>> +        many indexed properties and all the properties are once converted to uniqued strings and collected.
> 
> Replace "all the properties are once converted to uniqued strings and collected" with "all the indexes have to be converted to uniqued_strings for this one purpose, and then GC'ed thereafter".  I think that's what you meant.  If not, please correct me.

Per our offline discussion, let me revise my suggestion here.

Please replace "all the properties are once converted to uniqued strings and collected" with "all the indexes have to be converted to uniqued_strings and added to the collection of property names (though they may not be of the requested type and will be filtered out later)".

> Source/JavaScriptCore/ChangeLog:18
> +        It makes that PropertyNameArray doesn't become so large.

I suggest replacing "It makes that ... so large" with "It ensures that ... so large in the pathological case".

> Source/JavaScriptCore/ChangeLog:34
> +        But we don't heavily rely on this system; it means that getOwnPropertyNames may add wrong typed
> +        keys (adding the string keys in the context requiring the symbol keys) because relying on the
> +        careful coding in the getOwnPropertyNames side is much error prone. Users may add the string key
> +        in the context only requiring the symbol keys.
> +        So the guarantee such as "only symbols are included if the PropertiesTypeMode is Symbols" is
> +        ensured in the PropertyNameArray side.

How about rephrasing this as:
"But we cannot exclusively rely on these caller side checks because it would require that we exhaustively add the checks to all custom implementations of getOwnPropertyNames as well.  This process requires manual inspection of many pieces of code, and is error prone.  Instead, we only apply the caller side check in a few strategic places where it is known to yield performance benefits; and we rely on the filter in PropertyNameArray::add() to reject the wrong types of properties for all other calls to PropertyNameArray::add()."

[Geoffrey Garen]

Comment on attachment 257339 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=257339&action=review

> Source/JavaScriptCore/runtime/EnumerationMode.h:31
> +enum class PropertiesTypeMode {

Since this is just a hint, let's call it PropertyTypeHint. Otherwise, it seems like it's an error to disobey the mode.

[Yusuke Suzuki]

Comment on attachment 257339 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=257339&action=review

Thank you for your review, Mark & Geoff!

>> Source/JavaScriptCore/ChangeLog:8
>> +        Before this patch, Object.getOwnPropertySymbols once collects the all names including strings.
> 
> Replace "once collects the all names" with "collects all the names".

Fixed.

>> Source/JavaScriptCore/ChangeLog:10
>> +        But it's so much time consuming if the given object is a large non-holed array since it has
> 
> Replace "it's so much time consuming" with "it's so time consuming".

Fixed.

>>> Source/JavaScriptCore/ChangeLog:11
>>> +        many indexed properties and all the properties are once converted to uniqued strings and collected.
>> 
>> Replace "all the properties are once converted to uniqued strings and collected" with "all the indexes have to be converted to uniqued_strings for this one purpose, and then GC'ed thereafter".  I think that's what you meant.  If not, please correct me.
> 
> Per our offline discussion, let me revise my suggestion here.
> 
> Please replace "all the properties are once converted to uniqued strings and collected" with "all the indexes have to be converted to uniqued_strings and added to the collection of property names (though they may not be of the requested type and will be filtered out later)".

Sounds nice. I'll change it.

>> Source/JavaScriptCore/ChangeLog:18
>> +        It makes that PropertyNameArray doesn't become so large.
> 
> I suggest replacing "It makes that ... so large" with "It ensures that ... so large in the pathological case".

Sounds nice! Fixed.

>> Source/JavaScriptCore/ChangeLog:34
>> +        ensured in the PropertyNameArray side.
> 
> How about rephrasing this as:
> "But we cannot exclusively rely on these caller side checks because it would require that we exhaustively add the checks to all custom implementations of getOwnPropertyNames as well.  This process requires manual inspection of many pieces of code, and is error prone.  Instead, we only apply the caller side check in a few strategic places where it is known to yield performance benefits; and we rely on the filter in PropertyNameArray::add() to reject the wrong types of properties for all other calls to PropertyNameArray::add()."

Looks great! Fixed.

>> Source/JavaScriptCore/ChangeLog:35
>> +
> 
> In this patch, there's a concept in use that is not clear just from reading the code, and hence should be documented here.  That is: when selecting the PropertiesTypeMode for the PropertyNameArray to be instantiated, you applied the following logic:
> 1. Only JavaScriptCore code is aware of ES6 Symbols.  We can assume that pre-existing external code that interfaces JSC are only looking for string named properties.  This includes:
>     a. WebCore bindings
>     b. Serializer bindings
>     c. NPAPI bindings
>     d. Objective C bindings
> 
> 2. In JSC, code that compute object storage space needs to iterate both Symbol and String named properties.  Hence, use PropertiesTypeMode::Both.
> 3. In JSC, ES6 APIs that work with Symbols should use PropertiesTypeMode::Symbols.
> 4. In JSC, ES6 APIs that work with String named properties should use PropertiesTypeMode::Strings.
> 
> Please add a comment here to document this reasoning.

Your reasoning is looks perfect. I've added this here.

>> Source/JavaScriptCore/runtime/EnumerationMode.h:31
>> +enum class PropertiesTypeMode {
> 
> Since this is just a hint, let's call it PropertyTypeHint. Otherwise, it seems like it's an error to disobey the mode.

This mode is used as a hint in the caller side (getOwnPropertyNames), but it's used as an invariant in the callee side (PropertyNameArray).
Typical users use it as the `PropertyNameArray array(exec, PropertiesTypeMode::Strings)`. So I think keeping this name is preferable.
What do you think of it? I'd like to hear your opinion :)

>> LayoutTests/js/regress/script-tests/object-get-own-property-symbols-on-large-array.js:1
>> +function trial()
> 
> I think you're expecting this test to not time out.  If so, can you put a comment above to indicate that "This test should not time out"?  Alternatively, you can measure the time it takes to run trial() (using Date.now() before and after) and verify that the delta is less than some generous amount of time ... maybe 1 second?

Measuring the delta is nice to me. Time out in LayoutTests needs longer time and adjusting the test to it may lead the test flaky.

[Yusuke Suzuki]

Created attachment 257414 [details]
Patch

[Mark Lam]

Comment on attachment 257414 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=257414&action=review

> Source/JavaScriptCore/ChangeLog:8
> +        Before this patch, Object.getOwnPropertySymbols collects the all names including strings.

typo: "collects the all" ==> "collect all the".

> Source/JavaScriptCore/ChangeLog:40
> +        In this patch, there's a concept in use that is not clear just from reading the code, and hence
> +        should be documented here. That is: when selecting the PropertiesTypeMode for the PropertyNameArray
> +        to be instantiated, you applied the following logic:

Please replace this with:
"When selecting the PropertiesTypeMode for the PropertyNameArray to be instantiated, we apply the following logic:"

> Source/JavaScriptCore/ChangeLog:50
> +        1. Only JavaScriptCore code is aware of ES6 Symbols.
> +        We can assume that pre-existing external code that interfaces JSC are only looking for string named properties. This includes:
> +            a. WebCore bindings
> +            b. Serializer bindings
> +            c. NPAPI bindings
> +            d. Objective C bindings
> +        2. In JSC, code that compute object storage space needs to iterate both Symbol and String named properties. Hence, use PropertiesTypeMode::Both.
> +        3. In JSC, ES6 APIs that work with Symbols should use PropertiesTypeMode::Symbols.
> +        4. In JSC, ES6 APIs that work with String named properties should use PropertiesTypeMode::Strings.

After thinking about this some more, I'm wondering if this is the right approach.  Will talk with you offline to discuss the issues.

[Geoffrey Garen]

> >> Source/JavaScriptCore/runtime/EnumerationMode.h:31
> >> +enum class PropertiesTypeMode {
> > 
> > Since this is just a hint, let's call it PropertyTypeHint. Otherwise, it seems like it's an error to disobey the mode.
> 
> This mode is used as a hint in the caller side (getOwnPropertyNames), but
> it's used as an invariant in the callee side (PropertyNameArray).
> Typical users use it as the `PropertyNameArray array(exec,
> PropertiesTypeMode::Strings)`. So I think keeping this name is preferable.
> What do you think of it? I'd like to hear your opinion :)

I see.

OK, Mode sounds good to me.

Maybe PropertyNameMode, to match PropertyNameArray?

[Mark Lam]

Comment on attachment 257414 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=257414&action=review

>> Source/JavaScriptCore/ChangeLog:50
>> +        4. In JSC, ES6 APIs that work with String named properties should use PropertiesTypeMode::Strings.
> 
> After thinking about this some more, I'm wondering if this is the right approach.  Will talk with you offline to discuss the issues.

I changed my mind.  This logic works.

> Source/JavaScriptCore/runtime/EnumerationMode.h:35
> +enum class PropertiesTypeMode {
> +    Symbols = 1,
> +    Strings = 2,
> +    Both = 3,
> +};

I agree with Geoff: PropertyNameMode is a better name.

On another detail, according to includeSymbolProperties() and includeStringProperties(), PropertyNameMode is supposed to be bit maskable.  Would it be clearer about this intent is we express the enum as follows?

enum class PropertyNameMode {
    Symbols = 1 << 0,
    Strings = 1 << 1,
    Both = Symbols | Strings
};

[Yusuke Suzuki]

Comment on attachment 257414 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=257414&action=review

>> Source/JavaScriptCore/ChangeLog:8
>> +        Before this patch, Object.getOwnPropertySymbols collects the all names including strings.
> 
> typo: "collects the all" ==> "collect all the".

Fixed.

>> Source/JavaScriptCore/ChangeLog:40
>> +        to be instantiated, you applied the following logic:
> 
> Please replace this with:
> "When selecting the PropertiesTypeMode for the PropertyNameArray to be instantiated, we apply the following logic:"

Fixed.

>> Source/JavaScriptCore/runtime/EnumerationMode.h:35
>> +};
> 
> I agree with Geoff: PropertyNameMode is a better name.
> 
> On another detail, according to includeSymbolProperties() and includeStringProperties(), PropertyNameMode is supposed to be bit maskable.  Would it be clearer about this intent is we express the enum as follows?
> 
> enum class PropertyNameMode {
>     Symbols = 1 << 0,
>     Strings = 1 << 1,
>     Both = Symbols | Strings
> };

Completely agreed. It looks more readable.

[Yusuke Suzuki]

Created attachment 257462 [details]
Patch

[Mark Lam]

Comment on attachment 257462 [details]
Patch

r=me

[Yusuke Suzuki]

Comment on attachment 257462 [details]
Patch

Thanks for your reviews! I've checked cq+.

[WebKit Commit Bot]

Comment on attachment 257462 [details]
Patch

Clearing flags on attachment: 257462

Committed r187355: <http://trac.webkit.org/changeset/187355>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Yusuke Suzuki]

It may occur windows build failing.
I'm now investigating...
(Maybe, JSC:: namespace specifying is missing)

[Yusuke Suzuki]

Ah, I thought since I saw the failing in win EWS.
But seeing the buildbot, it seems that the patch passed the build.

If you found some build issues after this patch, please ping me.