Bug 41920 – Avoid slow-path for put() in Array.splice()

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Andreas Kling]

The JSArray that Array.splice() ends up returning is currently created early on.

If we defer creation until we know the number of elements to accommodate, we avoid taking the put() slow-path when populating the array.

[Andreas Kling]

Created attachment 60986 [details]
Proposed patch

[Oliver Hunt]

Comment on attachment 60986 [details]
Proposed patch

I think this can be made much better.

We should add a function to create a new array that will actually allocate sufficient space for the result as we know we will be producing a compact array of this size, then resObj->put(...) should be replaced with setIndex(k, v).

--Oliver

[Caio Marcelo de Oliveira Filho]

(In reply to comment #2)
> We should add a function to create a new array that will actually allocate sufficient space for the result as we know we will be producing a compact array of this size (...)

Oliver, why isn't enough to use the constructEmptyArray() variant that takes the initial length (the one the patch uses)? It preallocates for cases with size up to MIN_SPARE_ARRAY_INDEX (which is 10k).

[Oliver Hunt]

(In reply to comment #3)
> (In reply to comment #2)
> > We should add a function to create a new array that will actually allocate sufficient space for the result as we know we will be producing a compact array of this size (...)
> 
> Oliver, why isn't enough to use the constructEmptyArray() variant that takes the initial length (the one the patch uses)? It preallocates for cases with size up to MIN_SPARE_ARRAY_INDEX (which is 10k).

new Array(100000).splice()

Won't allocate sufficient space, and setIndex does not do bounds checks

[Andreas Kling]

Created attachment 61272 [details]
Proposed patch v2

Updated patch addressing Oliver's comments.
* Made it possible to create a compact JSArray via the constructor that takes an initialLength.
* Changed splice() to use setIndex().

[Darin Adler]

Comment on attachment 61272 [details]
Proposed patch v2

Great that you're tackling this!

> -        JSArray(NonNullPassRefPtr<Structure>, unsigned initialLength);
> +        JSArray(NonNullPassRefPtr<Structure>, unsigned initialLength, bool compact = false);

In the WebKit project we strongly discourage using booleans for arguments like this one where callers pass constants. Instead, we normally use enums.

Since there is only one place where we call this, I think the default for the boolean argument isn't a good idea. No reason to have the default.

The patch otherwise looks pretty good. But setIndex is not fast enough. We want to just set m_numValuesInVector, m_length, and the values in m_storage->m_vector, without any branches and without looping. We should come up with a new code path specifically designed for creating a new array efficiently.

I’m going to say review- because of the boolean.

[Darin Adler]

(In reply to comment #6)
> Since there is only one place where we call this

The one place I am referring to is constructArrayWithSizeQuirk in ArrayConstructor.cpp. That's the only call site I found.

[Andreas Kling]

(In reply to comment #7)
> The one place I am referring to is constructArrayWithSizeQuirk in ArrayConstructor.cpp. That's the only call site I found.

Other call sites:
* RegExpMatchesArray::RegExpMatchesArray() in RegExpConstructor.cpp
* constructEmptyArray() in JSGlobalObject.h

Revised patch coming in a bit.

[Andreas Kling]

Created attachment 61290 [details]
Proposed patch v3

Updated to address Darin's comments.

* Replaced constructor bool parameter with enum ArrayCreationMode { CreateCompactUninitialized, CreateInitialized }
* Added JSArray::uncheckedSetIndex(unsigned i, JSValue v)

I don't understand how we should initialize this array without looping though.

[Andreas Kling]

(In reply to comment #9)
> I don't understand how we should initialize this array without looping though.

Oh duh, I guess you mean setting m_numValuesInVector and m_length outside the loop. (Done in latest patch.)

[Darin Adler]

Comment on attachment 61290 [details]
Proposed patch v3

> +    if (creationMode == CreateInitialized) {
> +        JSValue* vector = m_storage->m_vector;
> +        for (size_t i = 0; i < initialCapacity; ++i)
> +            vector[i] = JSValue();
> +        m_storage->m_numValuesInVector = 0;
> +    } else
> +        m_storage->m_numValuesInVector = initialCapacity;

It's not safe to leave the vector uninitialized. Garbage collection could happen if one of the calls to getProperty does any object allocation, which can definitely happen in many ways, including getters and DOM objects. And if garbage collection does happen, we will need to survive a call to the markChildren function.

> +        enum ArrayCreationMode { CreateCompactUninitialized, CreateInitialized };

While it is nice to scope the enum to the class, it makes the call sites too ugly. I think it's fine to define this at namespace scope instead.

> +        void uncheckedSetIndex(unsigned i, JSValue v)
> +        {
> +            m_storage->m_vector[i] = v;
> +        }

You could put assertions in here to make it clearer what those things are that are not checked.

[Oliver Hunt]

Comment on attachment 61290 [details]
Proposed patch v3

In our new construct path if we delay setting the length to the end of initialisation we can avoid clearing the vector...

[Andreas Kling]

Created attachment 61299 [details]
Proposed patch v4

Patch updated addressing Darin and Oliver's comments.

* ArrayCreationMode enum moved into JSC namespace. [Darin]
* Assertion added to uncheckedSetIndex(). [Darin]
* For CreateCompact, m_storage->m_length is left as 0 and finally set by setLength() after inserting the values. [Oliver]

[Darin Adler]

Comment on attachment 61299 [details]
Proposed patch v4

This is really great work. And so close, but still one thing not quite right that I spotted.

> +    if (creationMode == CreateCompact) {
> +        // NOTE: setLength() must be called after initializing this array.
> +        m_storage->m_length = 0;
> +        m_storage->m_numValuesInVector = initialCapacity;

The intent here is to now call uncheckedSetIndex on each element in the vector and then call setLength. The comment mentions setLength, but not uncheckedSetIndex; both are required. I think the comment should go in the header instead of here (see below).

Unfortunately, the call to setLength when the values are set but the length is still zero is incompatible with CHECK_ARRAY_CONSISTENCY. The checkConsistency call at the start of setLength will assert because there are values in the vector in slots that are greater than m_length.

So somehow we need to turn off that consistency check. I'm sure there are multiple ways to do this. The simplest would be to remove the consistency check at the start of setLength, but I'd prefer not to do that. The second simplest I can think of is to add a debug-only boolean flag to ArrayStorage that is true if we have created an array with CreateCompact but have not yet set the length. If that flag is set we can skip the checkConsistency call at the start of setLength. We can also assert that flag is not set in the checkConsistency function. We could probably do other checks with that flag as well, to catch other unsafe actions during the process of creating the array.

> +    enum ArrayCreationMode { CreateCompact, CreateInitialized };

I think a comment about how CreateCompact works should be somewhere in the header. If we use CreateCompact to create an array, we are obligated to then use uncheckedSetIndex for all the elements of the array and the setLength; in fact the debugging checks may obligate us to do this even if the length is zero! The header should mentions this somewhere. Not that I want to be wordy and untidy, but that would be non-obvious if not mentioned, and so is the type of thing we do want to put in a comment.

> +        void uncheckedSetIndex(unsigned i, JSValue v)
> +        {
> +            ASSERT(canSetIndex(i));
> +            m_storage->m_vector[i] = v;
> +        }

We could also assert that we are in the "create new elements of a compact array" mode if we add that flag, or if not in that special mode we'd want to assert that the previous value in the vector is non-zero and that i < m_storage->m_length.

I'd say review- but I don't want to land something that breaks the CHECK_ARRAY_CONSISTENCY mode. I also suggest you run the regression tests with CHECK_ARRAY_CONSISTENCY turned on after making your change, although you don't want to land with it on!

[Darin Adler]

(In reply to comment #14)
> we are obligated to then use uncheckedSetIndex for all the elements of the array and the setLength; in fact the debugging checks may obligate us to do this even if the length is zero!

On second though, we can write the debugging checks so they do not obligate us to call setLength. We can set the "did a CreateCompact and needs a setLength" flag only if the initial capacity is non-zero.

[Andreas Kling]

(In reply to comment #14)
> I'd say review- but I don't want to land something that breaks the CHECK_ARRAY_CONSISTENCY mode.

It's already broken - it uses JSValue::type() which was eliminated(!) in http://trac.webkit.org/changeset/35830 :-)

[Darin Adler]

(In reply to comment #16)
> It's already broken - it uses JSValue::type() which was eliminated(!) in http://trac.webkit.org/changeset/35830 :-)

I'm sad to hear that. Should be quick to fix, though.

[Andreas Kling]

Created attachment 61424 [details]
Proposed patch v5

Updated patch, sorry about the delay!

* Brief explanation about CreateCompact mode added to JSArray.h
* m_inCompactInitialization flag added to ArrayStorage (only with CHECK_ARRAY_CONSISTENCY)
* ASSERT(m_inCompactInitialization) added to uncheckedSetIndex()
* setLength() won't call checkConsistency() on entry at the first call after CreateCompact initialization.

[WebKit Review Bot]

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

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
JavaScriptCore/runtime/JSArray.cpp:159:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 1 in 7 files


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

[Andreas Kling]

Comment on attachment 61424 [details]
Proposed patch v5

Unsetting cq? because I love you, Stylebot.

[Darin Adler]

Comment on attachment 61424 [details]
Proposed patch v5

> -#define CHECK_ARRAY_CONSISTENCY 0

One of the goals for CHECK_ARRAY_CONSISTENCY is to be able to turn it on without recompiling anything except JSArray.cpp. By making m_inCompactInitialization be included in any non-NDEBUG builds, we could achieve that.

The code to set up m_inCompactInitialization and the data member itself would be inside #ifndef NDEBUG rather than #if CHECK_ARRAY_CONSISTENCY.

> +#if CHECK_ARRAY_CONSISTENCY
> +            ASSERT(m_storage->m_inCompactInitialization);
> +#endif

If we used #ifndef NDEBUG we could just unconditionally include this assertion. This gives a good reason to have the boolean there even if CHECK_ARRAY_CONSISTENCY is 0.

r=me as is

Even better if you move CHECK_ARRAY_CONSISTENCY back inside the .cpp file.

[Andreas Kling]

Committed r63268: <http://trac.webkit.org/changeset/63268>