Bug 193912 - [JSC] Repeat string created from Array.prototype.join() take too much memory
Summary: [JSC] Repeat string created from Array.prototype.join() take too much memory
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: PC Linux
: P2 Normal
Assignee: Guillaume Emont
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2019-01-28 09:49 PST by Guillaume Emont
Modified: 2019-02-26 01:00 PST (History)
16 users (show)

See Also:


Attachments
Screenshot form massif-visualizer showing where memory was allocated (801.64 KB, image/png)
2019-01-31 13:04 PST, Guillaume Emont
no flags Details
Patch (4.47 KB, patch)
2019-02-04 17:04 PST, Guillaume Emont
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from ews121 for ios-simulator-wk2 (9.41 MB, application/zip)
2019-02-04 21:38 PST, Build Bot
no flags Details
Patch (4.47 KB, patch)
2019-02-05 13:07 PST, Guillaume Emont
no flags Details | Formatted Diff | Diff
Patch (6.42 KB, patch)
2019-02-11 13:03 PST, Guillaume Emont
no flags Details | Formatted Diff | Diff
Patch (7.05 KB, patch)
2019-02-25 11:30 PST, Guillaume Emont
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Guillaume Emont 2019-01-28 09:49:34 PST
The following code takes over 600M of rss on my linux x86_64 desktop:
  var a = new Array(10 * 1024 * 1024).join('M');

and takes over 2s to run (on a dual Xeon E5-2630). I would expect it to take much less time and use an order of magnitude less memory.

As a comparison, the following code runs in ~27ms:
  var a = 'M'.repeat(10 * 1024 * 1024);
Comment 1 Guillaume Emont 2019-01-28 09:52:54 PST
(In reply to Guillaume Emont from comment #0)
> The following code takes over 600M of rss on my linux x86_64 desktop:
>   var a = new Array(10 * 1024 * 1024).join('M');

The rss measure was taken on the jsc standalone interpreter.
Comment 2 Saam Barati 2019-01-31 12:32:12 PST
Seems reasonable to make this better.
Comment 3 Guillaume Emont 2019-01-31 13:00:41 PST
The first idea I'm currently exploring is to change fastJoin() in ArrayPrototype.cpp so that if the array is uninitialized (I think that's equivalent to indexingType() == ArrayType), we call String.prototype.repeat().

That's a relatively quick fix that should help in this specific test case, though I'm still curious to understand why a string of 10M chars seems to take 485MB of memory (or at least we reserve that much, according to massif). That's an average of 48.5 bytes per char, I think we could do better, even if it was a totally random string.
Comment 4 Guillaume Emont 2019-01-31 13:04:46 PST
Created attachment 360761 [details]
Screenshot form massif-visualizer showing where memory was allocated

In the attached screenshot, we see that about 485M is allocated by JSRopeString::create() and about 80M by JSArray::tryCreate().
Comment 5 Guillaume Emont 2019-02-04 17:04:28 PST
Created attachment 361132 [details]
Patch

This seems to fix the time and memory consumption of things like \'var a = new Array(10 * 1024 * 1024).join('M');\' by adding a fast case for uninitialize arrays.
Comment 6 Build Bot 2019-02-04 21:37:58 PST
Comment on attachment 361132 [details]
Patch

Attachment 361132 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: https://webkit-queues.webkit.org/results/11034977

New failing tests:
editing/pasteboard/smart-paste-007.html
editing/pasteboard/smart-paste-008.html
Comment 7 Build Bot 2019-02-04 21:38:00 PST
Created attachment 361157 [details]
Archive of layout-test-results from ews121 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews121  Port: ios-simulator-wk2  Platform: Mac OS X 10.13.6
Comment 8 Guillaume Emont 2019-02-05 13:07:25 PST
Created attachment 361213 [details]
Patch

Submitting same patch again to see if ios-sim-ews error was a flakey couple of tests
Comment 9 Saam Barati 2019-02-10 20:18:18 PST
Comment on attachment 361213 [details]
Patch

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

Mostly LGTM, but some comments.

> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:510
> +            RELEASE_AND_RETURN(scope, jsEmptyString(&state));

Is this correct even if length >= 2? Wouldn't we still access those properties? Don't we then need to check if holesMustForwardToPrototype? If that's the correct behavior, please add a test where this would've had the wrong behavior.

> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:513
> +            if (length <= 1)
> +                RELEASE_AND_RETURN(scope, jsEmptyString(&state));

Why can this go before the holesMustForwardToPrototypeCheck? Do we not access any properties if length is 1?

> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:518
> +            else

nit: no else needed here since previous if ends in a return
Comment 10 Guillaume Emont 2019-02-11 13:03:36 PST
(In reply to Saam Barati from comment #9)
> Comment on attachment 361213 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=361213&action=review
> 
> Mostly LGTM, but some comments.
> 
> > Source/JavaScriptCore/runtime/ArrayPrototype.cpp:510
> > +            RELEASE_AND_RETURN(scope, jsEmptyString(&state));
> 
> Is this correct even if length >= 2? Wouldn't we still access those
> properties? Don't we then need to check if holesMustForwardToPrototype? If
> that's the correct behavior, please add a test where this would've had the
> wrong behavior.

Indeed, this is not correct, even with length==1, this was an oversight on my part.

> 
> > Source/JavaScriptCore/runtime/ArrayPrototype.cpp:513
> > +            if (length <= 1)
> > +                RELEASE_AND_RETURN(scope, jsEmptyString(&state));
> 
> Why can this go before the holesMustForwardToPrototypeCheck? Do we not
> access any properties if length is 1?
Same as above.
> 
> > Source/JavaScriptCore/runtime/ArrayPrototype.cpp:518
> > +            else
> 
> nit: no else needed here since previous if ends in a return
Comment 11 Guillaume Emont 2019-02-11 13:03:57 PST
Created attachment 361705 [details]
Patch

New version that addresses the issues raised by Saam. I also added a test, since I did not see that issue when running tests.
Comment 12 Guillaume Emont 2019-02-12 09:57:30 PST
WPE error looks like the EWS was temporarily running out of RAM, I don't think we should be too worried about that.
Comment 13 Guillaume Emont 2019-02-14 02:02:14 PST
Ping reviewer.
Comment 14 Saam Barati 2019-02-25 00:13:09 PST
Comment on attachment 361705 [details]
Patch

r=me
Comment 15 Saam Barati 2019-02-25 00:14:19 PST
You should also add a microbenchmark
Comment 16 Guillaume Emont 2019-02-25 11:30:10 PST
Created attachment 362913 [details]
Patch

Patch for landing.
Comment 17 WebKit Commit Bot 2019-02-26 00:50:54 PST
Comment on attachment 362913 [details]
Patch

Clearing flags on attachment: 362913

Committed r242081: <https://trac.webkit.org/changeset/242081>
Comment 18 WebKit Commit Bot 2019-02-26 00:50:56 PST
All reviewed patches have been landed.  Closing bug.
Comment 19 Radar WebKit Bug Importer 2019-02-26 01:00:59 PST
<rdar://problem/48394256>