Bug 144622 – JSArray::setLength() should reallocate instead of zero-filling if the reallocation would be small enough

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Filip Pizlo]

This would be a speed-up on some pathological array shrinkage cases.

[Filip Pizlo]

If we fix this, we could unhack tests/mozilla/js1_5/Array/regress-101964.js.

[Mark Lam]

Created attachment 253108 [details]
the patch.

[Mark Lam]

Created attachment 253109 [details]
Summary of benchmark results

[WebKit Commit Bot]

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.

[Mark Lam]

Created attachment 253111 [details]
patch 2: fixed style issue.

[Geoffrey Garen]

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.

[Mark Lam]

(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().

[Mark Lam]

Created attachment 253156 [details]
patch 2: addressed Geoff’s feedback.

[Mark Lam]

Comment on attachment 253156 [details]
patch 2: addressed Geoff’s feedback.

The shortened test timing is still failing.  I’ll investigate.

[Mark Lam]

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.

[Mark Lam]

Created attachment 253182 [details]
patch 2: re-uploaded again to trigger EWS bots.

[Geoffrey Garen]

Comment on attachment 253182 [details]
patch 2: re-uploaded again to trigger EWS bots.

r=me

[Mark Lam]

Thanks for the review.  Landed in r184407: <http://trac.webkit.org/r184407>.

[Michael Saboff]

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

[Mark Lam]

(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.