Bug 91933 – JSC should have property butterflies

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Filip Pizlo]

In a butterfly object model, you point into the middle of an object, and one set of properties is offset to the left (negative address direction) of the pointer while another distinct set is offset to the right (positive).  JSC should use this approach for property storage, so that named (and private) properties grow to the left while indexed properties grow to the right.  This will immediately yield two benefits: (1) all objects will have fast indexed storage and (2) indexed storage access will not have to perform the array type check.

[Filip Pizlo]

Created attachment 154570 [details]
it begins

[Filip Pizlo]

Created attachment 154739 [details]
more

And still a lot more left to do.

[Filip Pizlo]

Created attachment 154770 [details]
more

[Filip Pizlo]

Created attachment 154779 [details]
this isn't going to be a small change.

[Filip Pizlo]

Created attachment 155041 [details]
more

[Filip Pizlo]

Created attachment 155056 [details]
even more

Most of the JSArray functionality is now moved to JSObject.

This code does not compile, or work, or anything, for that matter.  Still a lot more to do.

[Filip Pizlo]

Created attachment 155083 [details]
it's getting there!

[Filip Pizlo]

Created attachment 155105 [details]
a little more

I think I'm getting close to having moved all of JSArray's indexed property handling into JSObject.

[Filip Pizlo]

Created attachment 155138 [details]
JSObject appears to be done

Except of course for all of the JIT and LLInt code that needs to be rewritten.  And the hacks for property name iteration are probably not yet complete.

[Filip Pizlo]

Created attachment 155139 [details]
rebased up to r123971

[Filip Pizlo]

Created attachment 155156 [details]
a bit more

[Filip Pizlo]

Created attachment 155176 [details]
almost done with JSArray methods

[Filip Pizlo]

Created attachment 155180 [details]
JSObject and JSArray are done

[Filip Pizlo]

Created attachment 160268 [details]
some rebasing

I'll have to rip out the type in IndexingHeader and replace it with an array mode in Structure.  Haven't done that yet.

[Filip Pizlo]

Created attachment 160281 [details]
more rebasing

Changed more of the code to use Structure::indexingType() rather than IndexingHeader::type().

[Filip Pizlo]

Created attachment 160305 [details]
rebasing done

The code should now be using Structure::indexingType(), and Structure now has the notion of cacheable indexing type transitions.

[Filip Pizlo]

Created attachment 160496 [details]
more

[Filip Pizlo]

Created attachment 160553 [details]
a little more

[Filip Pizlo]

Created attachment 160629 [details]
rebased again

[Filip Pizlo]

Created attachment 160894 [details]
it's starting to sort of compile

By which I mean I can compile the LLIntOffsetsExtractor.  Still a lot of work to do though.

[Filip Pizlo]

Created attachment 161014 [details]
more

[Filip Pizlo]

Created attachment 161059 [details]
more

[Filip Pizlo]

Created attachment 161103 [details]
it builds.

And probably crashes on launch, though I wouldn't know.

[Filip Pizlo]

Created attachment 161129 [details]
it runs things.

Most of the benchmarks run correctly.  I still smell bugs though.

[Filip Pizlo]

Created attachment 161142 [details]
zero regression on SunSpider

Still testing more things.

[Filip Pizlo]

(In reply to comment #25)
> Created an attachment (id=161142) [details]
> zero regression on SunSpider
> 
> Still testing more things.

Zero regression on SunSpider, V8, or Kraken.  Possible speed-up on V8, but it's slight.

[Filip Pizlo]

Created attachment 161416 [details]
getting close

Tests are starting to pass.

[Filip Pizlo]

Created attachment 161593 [details]
passes run-javascriptcore-tests

[Filip Pizlo]

Created attachment 161795 [details]
making progress with LayoutTests/fast/js

Still not passing though.

[Filip Pizlo]

Created attachment 161814 [details]
almost there in fast/js

[Filip Pizlo]

Created attachment 162135 [details]
more progress on fast/js

[Filip Pizlo]

Created attachment 162417 [details]
fast/js gets as far as it's going to get

We fail corner cases of numeric setters.  But we pass everything else.  That's as good as it's going to get, for now.

[Filip Pizlo]

Created attachment 162906 [details]
almost passing all tests

[Filip Pizlo]

Created attachment 162933 [details]
almost ready for review

Still need to write some 32-bit support code, and need to add files to the other build systems.

[Filip Pizlo]

Created attachment 163018 [details]
the patch

It works.

[WebKit Review Bot]

Attachment 163018 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1
Source/JavaScriptCore/runtime/JSArray.h:125:  The parameter name "globalData" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1088:  Missing space before {  [whitespace/braces] [5]
Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1165:  Missing space before {  [whitespace/braces] [5]
Source/JavaScriptCore/runtime/JSObject.cpp:51:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/runtime/ArrayPrototype.h:36:  The parameter name "exec" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/ArrayPrototype.h:36:  The parameter name "globalObject" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/ArrayPrototype.h:36:  The parameter name "structure" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/IndexingHeaderInlineMethods.h:29:  Alphabetical sorting problem.  [build/include_order] [4]
Source/JavaScriptCore/runtime/Butterfly.h:66:  The parameter name "structure" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/Butterfly.h:85:  The parameter name "structure" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/Butterfly.h:96:  The parameter name "structure" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/Butterfly.h:98:  The parameter name "structure" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/Butterfly.h:99:  The parameter name "structure" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/Butterfly.h:100:  The parameter name "structure" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/StringPrototype.cpp:26:  Alphabetical sorting problem.  [build/include_order] [4]
Source/JavaScriptCore/runtime/SparseArrayValueMap.h:42:  Missing space inside { }.  [whitespace/braces] [5]
Source/JavaScriptCore/runtime/SparseArrayValueMap.h:65:  The parameter name "globalData" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/SparseArrayValueMap.h:68:  The parameter name "globalData" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/SparseArrayValueMap.h:79:  The parameter name "globalData" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSArray.cpp:587:  More than one command on the same line  [whitespace/newline] [4]
Source/JavaScriptCore/runtime/ArrayConventions.h:45:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/runtime/JSObject.h:187:  The parameter name "exec" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSObject.h:613:  The parameter name "offset" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/ArrayStorage.h:39:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/runtime/ArrayStorage.h:40:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/runtime/ArrayStorage.h:41:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/runtime/ArrayStorage.h:42:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/runtime/SparseArrayValueMapInlineMethods.h:30:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 28 in 114 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Build Bot]

Comment on attachment 163018 [details]
the patch

Attachment 163018 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/13794693

[Early Warning System Bot]

Comment on attachment 163018 [details]
the patch

Attachment 163018 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/13793683

[Early Warning System Bot]

Comment on attachment 163018 [details]
the patch

Attachment 163018 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/13796660

[Filip Pizlo]

Created attachment 163019 [details]
the patch

Style fixes, and build fixes for Win and Qt.

[WebKit Review Bot]

Attachment 163019 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1
Source/JavaScriptCore/runtime/ArrayConventions.h:45:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Total errors found: 1 in 114 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Build Bot]

Comment on attachment 163019 [details]
the patch

Attachment 163019 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/13795652

[Filip Pizlo]

Created attachment 163020 [details]
the patch

Another style fix.  Also trying to fix Win.

[Build Bot]

Comment on attachment 163020 [details]
the patch

Attachment 163020 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/13799592

[Filip Pizlo]

Created attachment 163022 [details]
the patch

Fix Windows, for real this time!

[Geoffrey Garen]

Comment on attachment 163022 [details]
the patch

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

> Source/JavaScriptCore/llint/LowLevelInterpreter.asm:67
> +# Constant for reasoning about butterflies.
> +const IsArray = 1
> +const HasArrayStorage = 8
> +const AllArrayTypes = 15

The magical constants in the LLInt have been giving me fits lately. Would be nice to generate them through a .cpp file, so they auto-update.

> Source/JavaScriptCore/runtime/ArrayStorage.h:39
> +// This struct holds the actual data values of an array. A JSArray object points to it's contained ArrayStorage

Typo: "it's" => "its".

> Source/JavaScriptCore/runtime/JSObject.cpp:279
> +    // Try indexed put first.

Would be nice for this comment to explain that this is required for correctness, and not just optimization.

> Source/JavaScriptCore/runtime/JSObject.cpp:281
> +    if (i != PropertyName::NotAnIndex) {

Since we think the "not an index" case is probably common, it would be nice to refactor toUInt32FromCharacters() to have an inline fast path for the first character being non-digit, and move all the other code out-of-line.

> Source/JavaScriptCore/runtime/JSObject.h:542
> +        ArrayStorage* arrayStorageOrZero()

Let's call this "arrayStorageOrNull", since (ArrayStorage*)0 is better known as null.

> Source/JavaScriptCore/runtime/JSObject.h:773
> +inline void JSObject::setButterfly(JSGlobalData& globalData, Butterfly* butterfly, Structure* structure)

When 'butterfly' points to out-of-line storage, this function is a reference store between GC objects. Does it need to perform a write barrier?

> Source/JavaScriptCore/runtime/JSObject.h:781
> +inline void JSObject::setButterflyWithoutChangingStructure(Butterfly* butterfly)

Ditto.

> Source/JavaScriptCore/runtime/SparseArrayValueMapInlineMethods.h:104
> +        entry.set(exec->globalData(), array, value);

Since 'this' is a GC object now, it should be the owner in this set, not 'array'.

> Source/JavaScriptCore/runtime/SparseArrayValueMapInlineMethods.h:139
> +    entry.set(exec->globalData(), array, value);

Ditto.

> Source/JavaScriptCore/runtime/SparseArrayValueMapInlineMethods.h:190
> +inline void SparseArrayValueMap::visitChildren(JSCell* thisObject, SlotVisitor& visitor)

Since this is a GC object now, it needs to call through to Base::visitChildren().

[Geoffrey Garen]

Comment on attachment 163022 [details]
the patch

r=me

[Filip Pizlo]

(In reply to comment #46)
> (From update of attachment 163022 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=163022&action=review
> 
> > Source/JavaScriptCore/llint/LowLevelInterpreter.asm:67
> > +# Constant for reasoning about butterflies.
> > +const IsArray = 1
> > +const HasArrayStorage = 8
> > +const AllArrayTypes = 15
> 
> The magical constants in the LLInt have been giving me fits lately. Would be nice to generate them through a .cpp file, so they auto-update.

Yes!  I have been thinking about how to do that.  We should definitely do this.  https://bugs.webkit.org/show_bug.cgi?id=96587

> 
> > Source/JavaScriptCore/runtime/ArrayStorage.h:39
> > +// This struct holds the actual data values of an array. A JSArray object points to it's contained ArrayStorage
> 
> Typo: "it's" => "its".

Done.

> 
> > Source/JavaScriptCore/runtime/JSObject.cpp:279
> > +    // Try indexed put first.
> 
> Would be nice for this comment to explain that this is required for correctness, and not just optimization.

Done.

> 
> > Source/JavaScriptCore/runtime/JSObject.cpp:281
> > +    if (i != PropertyName::NotAnIndex) {
> 
> Since we think the "not an index" case is probably common, it would be nice to refactor toUInt32FromCharacters() to have an inline fast path for the first character being non-digit, and move all the other code out-of-line.

The whole method is ALWAYS_INLINE, and the second thing it checks is for the first character not being a digit.  (The first thing it checks is for the string being zero-length.)

> 
> > Source/JavaScriptCore/runtime/JSObject.h:542
> > +        ArrayStorage* arrayStorageOrZero()
> 
> Let's call this "arrayStorageOrNull", since (ArrayStorage*)0 is better known as null.

Done.

> 
> > Source/JavaScriptCore/runtime/JSObject.h:773
> > +inline void JSObject::setButterfly(JSGlobalData& globalData, Butterfly* butterfly, Structure* structure)
> 
> When 'butterfly' points to out-of-line storage, this function is a reference store between GC objects. Does it need to perform a write barrier?

As per our discussions, I'm leaving it as is.  None of the copying GC styles we can envision doing in the near future would require a barrier on accesses to m_butterfly.

> 
> > Source/JavaScriptCore/runtime/JSObject.h:781
> > +inline void JSObject::setButterflyWithoutChangingStructure(Butterfly* butterfly)
> 
> Ditto.
> 
> > Source/JavaScriptCore/runtime/SparseArrayValueMapInlineMethods.h:104
> > +        entry.set(exec->globalData(), array, value);
> 
> Since 'this' is a GC object now, it should be the owner in this set, not 'array'.

Ah!  Good catch.  Fixed.

> 
> > Source/JavaScriptCore/runtime/SparseArrayValueMapInlineMethods.h:139
> > +    entry.set(exec->globalData(), array, value);
> 
> Ditto.

Fixed.

> 
> > Source/JavaScriptCore/runtime/SparseArrayValueMapInlineMethods.h:190
> > +inline void SparseArrayValueMap::visitChildren(JSCell* thisObject, SlotVisitor& visitor)
> 
> Since this is a GC object now, it needs to call through to Base::visitChildren().

Fixed!

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/128400

[Ryosuke Niwa]

It appears that this patch caused some perf. regression: https://bugs.webkit.org/show_bug.cgi?id=93744