Bug 144622 - JSArray::setLength() should reallocate instead of zero-filling if the reallocation would be small enough
Summary: JSArray::setLength() should reallocate instead of zero-filling if the realloc...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Mark Lam
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-05-04 21:37 PDT by Filip Pizlo
Modified: 2015-05-15 18:13 PDT (History)
6 users (show)

See Also:


Attachments
the patch. (5.63 KB, patch)
2015-05-14 00:50 PDT, Mark Lam
no flags Details | Formatted Diff | Diff
Summary of benchmark results (14.60 KB, text/plain)
2015-05-14 00:51 PDT, Mark Lam
no flags Details
patch 2: fixed style issue. (5.62 KB, patch)
2015-05-14 00:54 PDT, Mark Lam
ggaren: review-
Details | Formatted Diff | Diff
patch 2: addressed Geoff’s feedback. (5.74 KB, patch)
2015-05-14 16:54 PDT, Mark Lam
no flags Details | Formatted Diff | Diff
patch 2: re-uploaded again to trigger EWS bots. (5.74 KB, patch)
2015-05-15 00:40 PDT, Mark Lam
ggaren: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2015-05-04 21:37:39 PDT
This would be a speed-up on some pathological array shrinkage cases.
Comment 1 Filip Pizlo 2015-05-04 21:38:40 PDT
If we fix this, we could unhack tests/mozilla/js1_5/Array/regress-101964.js.
Comment 2 Mark Lam 2015-05-14 00:50:31 PDT
Created attachment 253108 [details]
the patch.
Comment 3 Mark Lam 2015-05-14 00:51:30 PDT
Created attachment 253109 [details]
Summary of benchmark results
Comment 4 WebKit Commit Bot 2015-05-14 00:52:19 PDT
Attachment 253108 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSObject.h:832:  The parameter name "vm" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 1 in 5 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 5 Mark Lam 2015-05-14 00:54:40 PDT
Created attachment 253111 [details]
patch 2: fixed style issue.
Comment 6 Geoffrey Garen 2015-05-14 11:28:43 PDT
Comment on attachment 253111 [details]
patch 2: fixed style issue.

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

> Source/JavaScriptCore/runtime/JSArray.cpp:422
> +        // These heuristic values were picked experimentally from running benchmarks.

Is this patch a speedup on any benchmarks? If so, which ones?

> Source/JavaScriptCore/runtime/JSArray.cpp:427
> +
> +        unsigned lengthToClear = m_butterfly->publicLength() - newLength;
> +        unsigned costToTrim = newLength * costAdjustmentToMakeNewButterfly;

This code is more complicated than it needs to be, by virtue of the meaningless * 1.0 abstraction. A simpler way to write this is:

unsigned lengthToClear = m_butterfly->publicLength() - newLength;
unsigned minLengthToAllocate = 64;
if (lengthToClear > newLength && newLength > minLengthToAllocate) {
    allocateButterfly(...);
    return true;
}

> Source/JavaScriptCore/runtime/JSArray.cpp:430
> +            trimLength(exec->vm(), newLength);

"trim" usually means "do an in-place reduction in size", which is the opposite of what this function does. I would call this createButterfly.
Comment 7 Mark Lam 2015-05-14 16:53:20 PDT
(In reply to comment #6)
> Is this patch a speedup on any benchmarks? If so, which ones?

Perf is neutral on the benchmarks.  However, this patch makes it such that we don’t have to wait a long time for tests/mozilla/js1_5/Array/regress-101964.js to complete.

> > Source/JavaScriptCore/runtime/JSArray.cpp:427
> > +
> > +        unsigned lengthToClear = m_butterfly->publicLength() - newLength;
> > +        unsigned costToTrim = newLength * costAdjustmentToMakeNewButterfly;
> 
> This code is more complicated than it needs to be, by virtue of the
> meaningless * 1.0 abstraction. A simpler way to write this is:
> 
> unsigned lengthToClear = m_butterfly->publicLength() - newLength;
> unsigned minLengthToAllocate = 64;
> if (lengthToClear > newLength && newLength > minLengthToAllocate) {
>     allocateButterfly(...);
>     return true;
> }

I’ve change the test, but have to adjust the algorithm.  The one you suggested has the following flaw:

Let’s say:
    lengthToClear is 1000000.
    newLength is 16.
    minLengthToAllocate is 64.
In this case, we would want to reallocate instead of clearing 1000000 - 16 slots.  However, your test would not let us reallocate because newLength is less than minLengthToAllocate.

Instead, this is the new test I’m going with:

    unsigned lengthToClear = m_butterfly->publicLength() - newLength;
    unsigned costToAllocateNewButterfly = 64; // a heuristic.
    if (lengthToClear > newLength && lengthToClear > costToAllocateNewButterfly) {
        reallocateAndShrinkButterfly(exec->vm(), newLength);
        return true;
    }

I also considered (lengthToClear > newLength + costToAllocateNewButterfly), but that test has an overflow problem when newLength is near max unsigned.  The (lengthToClear > newLength && lengthToClear > costToAllocateNewButterfly) test is a good enough heuristic for modeling the cost of allocation overhead.  So, I’m going with that.

> > Source/JavaScriptCore/runtime/JSArray.cpp:430
> > +            trimLength(exec->vm(), newLength);
> 
> "trim" usually means "do an in-place reduction in size", which is the
> opposite of what this function does. I would call this createButterfly.

Renamed to reallocateAndShrinkButterfly().
Comment 8 Mark Lam 2015-05-14 16:54:54 PDT
Created attachment 253156 [details]
patch 2: addressed Geoff’s feedback.
Comment 9 Mark Lam 2015-05-14 16:56:06 PDT
Comment on attachment 253156 [details]
patch 2: addressed Geoff’s feedback.

The shortened test timing is still failing.  I’ll investigate.
Comment 10 Mark Lam 2015-05-15 00:37:13 PDT
Comment on attachment 253156 [details]
patch 2: addressed Geoff’s feedback.

The test time out I saw earlier was due to me doing a build on the same machine while test was being run.  As a result, the test was CPU starved from time to time.  When running only the test, there was no time out.  So, I’ll resubmit the patch for review.
Comment 11 Mark Lam 2015-05-15 00:40:43 PDT
Created attachment 253182 [details]
patch 2: re-uploaded again to trigger EWS bots.
Comment 12 Geoffrey Garen 2015-05-15 11:17:58 PDT
Comment on attachment 253182 [details]
patch 2: re-uploaded again to trigger EWS bots.

r=me
Comment 13 Mark Lam 2015-05-15 13:06:35 PDT
Thanks for the review.  Landed in r184407: <http://trac.webkit.org/r184407>.
Comment 14 Michael Saboff 2015-05-15 17:47:59 PDT
Didn't we also expect this to fix mozilla/js1_5/Array/regress-157652.js?  It has been flakey for some time and is still failing on ARM64:

JavaScriptCore Regression Test Results for 184409

JavaScriptCore Regression Test Failures - 64 bit

Failures                                                                                     184407  184409
mozilla-tests.yaml/js1_5/Array/regress-157652.js.mozilla                                     Passed  Failed
mozilla-tests.yaml/js1_5/Array/regress-157652.js.mozilla-dfg-eager-no-cjit-validate-phases   Passed  Failed
mozilla-tests.yaml/js1_5/Array/regress-157652.js.mozilla-llint                               Failed  Passed
Comment 15 Mark Lam 2015-05-15 18:13:09 PDT
(In reply to comment #14)
> Didn't we also expect this to fix mozilla/js1_5/Array/regress-157652.js?  It
> has been flakey for some time and is still failing on ARM64:
> 
> JavaScriptCore Regression Test Results for 184409
> 
> JavaScriptCore Regression Test Failures - 64 bit
> 
> Failures                                                                    
> 184407  184409
> mozilla-tests.yaml/js1_5/Array/regress-157652.js.mozilla                    
> Passed  Failed
> mozilla-tests.yaml/js1_5/Array/regress-157652.js.mozilla-dfg-eager-no-cjit-
> validate-phases   Passed  Failed
> mozilla-tests.yaml/js1_5/Array/regress-157652.js.mozilla-llint              
> Failed  Passed

I’ll look into it.