Bug 41920 - Avoid slow-path for put() in Array.splice()
Summary: Avoid slow-path for put() in Array.splice()
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-07-08 17:25 PDT by Andreas Kling
Modified: 2010-07-13 17:30 PDT (History)
6 users (show)

See Also:


Attachments
Proposed patch (1.73 KB, patch)
2010-07-08 17:26 PDT, Andreas Kling
oliver: review-
oliver: commit-queue-
Details | Formatted Diff | Diff
Proposed patch v2 (3.27 KB, patch)
2010-07-12 14:55 PDT, Andreas Kling
darin: review-
darin: commit-queue-
Details | Formatted Diff | Diff
Proposed patch v3 (7.34 KB, patch)
2010-07-12 16:42 PDT, Andreas Kling
darin: review-
darin: commit-queue-
Details | Formatted Diff | Diff
Proposed patch v4 (7.60 KB, patch)
2010-07-12 17:28 PDT, Andreas Kling
darin: review-
darin: commit-queue-
Details | Formatted Diff | Diff
Proposed patch v5 (10.62 KB, patch)
2010-07-13 15:37 PDT, Andreas Kling
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andreas Kling 2010-07-08 17:25:18 PDT
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.
Comment 1 Andreas Kling 2010-07-08 17:26:09 PDT
Created attachment 60986 [details]
Proposed patch
Comment 2 Oliver Hunt 2010-07-08 23:14:00 PDT
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
Comment 3 Caio Marcelo de Oliveira Filho 2010-07-09 07:58:59 PDT
(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).
Comment 4 Oliver Hunt 2010-07-09 10:08:22 PDT
(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
Comment 5 Andreas Kling 2010-07-12 14:55:54 PDT
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().
Comment 6 Darin Adler 2010-07-12 15:36:55 PDT
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.
Comment 7 Darin Adler 2010-07-12 15:45:27 PDT
(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.
Comment 8 Andreas Kling 2010-07-12 16:18:10 PDT
(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.
Comment 9 Andreas Kling 2010-07-12 16:42:21 PDT
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.
Comment 10 Andreas Kling 2010-07-12 16:52:59 PDT
(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.)
Comment 11 Darin Adler 2010-07-12 16:55:12 PDT
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.
Comment 12 Oliver Hunt 2010-07-12 17:05:27 PDT
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...
Comment 13 Andreas Kling 2010-07-12 17:28:39 PDT
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]
Comment 14 Darin Adler 2010-07-13 09:27:13 PDT
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!
Comment 15 Darin Adler 2010-07-13 09:28:53 PDT
(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.
Comment 16 Andreas Kling 2010-07-13 10:36:08 PDT
(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 :-)
Comment 17 Darin Adler 2010-07-13 10:42:36 PDT
(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.
Comment 18 Andreas Kling 2010-07-13 15:37:14 PDT
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.
Comment 19 WebKit Review Bot 2010-07-13 15:41:14 PDT
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.
Comment 20 Andreas Kling 2010-07-13 15:53:53 PDT
Comment on attachment 61424 [details]
Proposed patch v5

Unsetting cq? because I love you, Stylebot.
Comment 21 Darin Adler 2010-07-13 15:59:06 PDT
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.
Comment 22 Andreas Kling 2010-07-13 17:30:03 PDT
Committed r63268: <http://trac.webkit.org/changeset/63268>