Replace PushIfAbsent by a Stack object

Replace PushIfAbsent by a Stack object

This significantly speeds up String(array).
BUG=

Committed: https://crrev.com/d3583574780848476dbde62122317452fddddb99
Cr-Commit-Position: refs/heads/master@{#34745}

[Toon Verwaest, 2016-03-10 15:15:17]

verwaest@chromium.org changed reviewers:
+ cbruni@chromium.org

[Toon Verwaest, 2016-03-10 15:15:19]

ptal

[Toon Verwaest, 2016-03-10 15:47:15]

The CQ bit was checked by verwaest@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-03-10 15:47:23]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1775403008/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1775403008/20001

[Camillo Bruni, 2016-03-10 15:50:38]

lgtm

[commit-bot: I haz the power, 2016-03-10 16:08:10]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-03-10 16:08:10]

Dry run: This issue passed the CQ dry run.

[Toon Verwaest, 2016-03-10 17:09:05]

Description was changed from

==========
Move PushIfAbsent to JavaScript.

BUG=
==========

to

==========
Replace PushIfAbsent by a Stack object and move StringBuilderJoin to JS

This significantly speeds up String(array).
BUG=
==========

[Toon Verwaest, 2016-03-10 17:10:01]

The CQ bit was checked by verwaest@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-03-10 17:10:04]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1775403008/40001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1775403008/40001

[Toon Verwaest, 2016-03-10 17:11:56]

The CQ bit was checked by verwaest@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-03-10 17:12:03]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1775403008/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1775403008/60001

[Camillo Bruni, 2016-03-10 17:20:03]

cbruni@chromium.org changed reviewers:
+ adamk@chromium.org

[Camillo Bruni, 2016-03-10 17:20:04]

adam could have a quick look at this?

For me this CL is still ok

[commit-bot: I haz the power, 2016-03-10 17:38:22]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-03-10 17:38:22]

Dry run: This issue passed the CQ dry run.

[Toon Verwaest, 2016-03-10 17:46:47]

I guess I should declare the instance variables on Stack.prototype to avoid
leaking them through Object.prototype...

[adamk, 2016-03-10 19:34:05]

Seems fine except for the exact bit that Toon already pointed out :)

https://codereview.chromium.org/1775403008/diff/60001/src/js/array.js
File src/js/array.js (right):

https://codereview.chromium.org/1775403008/diff/60001/src/js/array.js#newcode177
src/js/array.js:177: this.length = 0;
As Toon mentioned, this is indeed the problematic bit: you can't write to
'length' and 'values' here since they could trigger setters on Object.prototype.

[Toon Verwaest, 2016-03-10 19:47:46]

Updated the CL

[adamk, 2016-03-10 19:53:55]

https://codereview.chromium.org/1775403008/diff/80001/src/js/array.js
File src/js/array.js (right):

https://codereview.chromium.org/1775403008/diff/80001/src/js/array.js#newcode181
src/js/array.js:181: Stack.prototype.length = null;
Please add a comment noting that these are to mask any possible Object.prototype
properties, as well as a regression test showing that these two properties are
properly handled even if Object.prototype is mucked with. Otherwise I'd worry
that someone might remove them in a "cleanup"

[adamk, 2016-03-10 19:55:27]

lgtm once the Object.prototype-avoidance is commented and tested

[Toon Verwaest, 2016-03-10 19:59:58]

Added comment and test.

[adamk, 2016-03-10 20:06:25]

still lgtm

[Toon Verwaest, 2016-03-10 20:06:42]

The CQ bit was checked by verwaest@chromium.org

[Toon Verwaest, 2016-03-10 20:06:42]

The patchset sent to the CQ was uploaded after l-g-t-m from cbruni@chromium.org
Link to the patchset: https://codereview.chromium.org/1775403008/#ps100001
(title: "Add test and comment")

[commit-bot: I haz the power, 2016-03-10 20:06:47]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1775403008/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1775403008/100001

[commit-bot: I haz the power, 2016-03-10 23:24:15]

Description was changed from

==========
Replace PushIfAbsent by a Stack object and move StringBuilderJoin to JS

This significantly speeds up String(array).
BUG=
==========

to

==========
Replace PushIfAbsent by a Stack object and move StringBuilderJoin to JS

This significantly speeds up String(array).
BUG=
==========

[commit-bot: I haz the power, 2016-03-10 23:24:17]

Committed patchset #6 (id:100001)

[commit-bot: I haz the power, 2016-03-10 23:24:30]

Description was changed from

==========
Replace PushIfAbsent by a Stack object and move StringBuilderJoin to JS

This significantly speeds up String(array).
BUG=
==========

to

==========
Replace PushIfAbsent by a Stack object and move StringBuilderJoin to JS

This significantly speeds up String(array).
BUG=

Committed: https://crrev.com/c91faa0b39b62025460eb9f8b578e20d88f3549e
Cr-Commit-Position: refs/heads/master@{#34696}
==========

[commit-bot: I haz the power, 2016-03-10 23:24:31]

Patchset 6 (id:??) landed as
https://crrev.com/c91faa0b39b62025460eb9f8b578e20d88f3549e
Cr-Commit-Position: refs/heads/master@{#34696}

[Benedikt Meurer, 2016-03-11 07:59:27]

bmeurer@chromium.org changed reviewers:
+ bmeurer@chromium.org

[Benedikt Meurer, 2016-03-11 07:59:28]

Awesome!

[Michael Achenbach, 2016-03-11 08:39:44]

A revert of this CL (patchset #6 id:100001) has been created in
https://codereview.chromium.org/1785003004/ by machenbach@chromium.org.

The reason for reverting is: [Sheriff] This lets a gc stress test time out:
https://build.chromium.org/p/client.v8/builders/V8%20Linux%20-%20gc%20stress/...

The test ran in <2sec before this. Please fix the test as well on a reland..

[Michael Hablich, 2016-03-11 11:30:32]

On 2016/03/11 08:39:44, Michael Achenbach wrote:
> A revert of this CL (patchset #6 id:100001) has been created in
> https://codereview.chromium.org/1785003004/ by mailto:machenbach@chromium.org.
> 
> The reason for reverting is: [Sheriff] This lets a gc stress test time out:
>
https://build.chromium.org/p/client.v8/builders/V8%20Linux%20-%20gc%20stress/...
> 
> The test ran in <2sec before this. Please fix the test as well on a reland..

This also breaks some Chromium bots:
https://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium...

[Toon Verwaest, 2016-03-11 19:32:05]

Description was changed from

==========
Replace PushIfAbsent by a Stack object and move StringBuilderJoin to JS

This significantly speeds up String(array).
BUG=

Committed: https://crrev.com/c91faa0b39b62025460eb9f8b578e20d88f3549e
Cr-Commit-Position: refs/heads/master@{#34696}
==========

to

==========
Replace PushIfAbsent by a Stack object

This significantly speeds up String(array).
BUG=
==========

[Toon Verwaest, 2016-03-11 20:28:37]

Patchset #8 (id:140001) has been deleted

[Toon Verwaest, 2016-03-11 20:45:48]

PTAL again.

I restored the C++ stringbuilder since it handles huge arrays  better. Large
arrays cause huge chains of cons-strings otherwise, which uses a lot of memory
(e.g., ~700mb to render a ~10mb uint8array; for 30mb arrays we go OOM). The
self-hosted approach is better for smaller but nested arrays (delay flattening
until the result is ready); so we might want to have mixed version in the
future...

The changes in the CL already do give a significant speedup for both flat arrays
with strings and sparse arrays.

As a sidenote; I did notice that sparse arrays are actually broken. The spec
says we have to go from 0 to len, and convert element by element to string if
it's not undefined. We're very careful about not going sparse if there are
special elements; but obviously we have no control over toString of objects.

You could e.g., have the following case:

var a = [{toString() { a[1] = 1; return 0 }}, ];
a.length = 1000;
a.join(''); -> '0'

whereas

var a = [{toString() { a[1] = 1; return 0 }}, ];
a.length = 999;
a.join(''); -> '01'

[Camillo Bruni, 2016-03-14 10:09:52]

LGTM

https://codereview.chromium.org/1775403008/diff/180001/src/js/array.js
File src/js/array.js (right):

https://codereview.chromium.org/1775403008/diff/180001/src/js/array.js#newcod...
src/js/array.js:196: return %StringBuilderConcat(elements, length, '');
As you said, you could probably still create a silly cons string for small
lengths here...

[Toon Verwaest, 2016-03-14 12:21:43]

I'll profile that; and if it makes sense do it in a follow-up CL.

[Toon Verwaest, 2016-03-14 12:25:55]

The CQ bit was checked by verwaest@chromium.org

[Toon Verwaest, 2016-03-14 12:25:55]

The patchset sent to the CQ was uploaded after l-g-t-m from adamk@chromium.org
Link to the patchset: https://codereview.chromium.org/1775403008/#ps180001
(title: " ")

[Toon Verwaest, 2016-03-14 12:26:04]

The CQ bit was unchecked by verwaest@chromium.org

[Toon Verwaest, 2016-03-14 14:20:18]

The CQ bit was checked by verwaest@chromium.org

[Toon Verwaest, 2016-03-14 14:20:19]

The patchset sent to the CQ was uploaded after l-g-t-m from cbruni@chromium.org,
adamk@chromium.org
Link to the patchset: https://codereview.chromium.org/1775403008/#ps200001
(title: " ")

[commit-bot: I haz the power, 2016-03-14 14:20:29]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1775403008/200001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1775403008/200001

[commit-bot: I haz the power, 2016-03-14 14:44:23]

Description was changed from

==========
Replace PushIfAbsent by a Stack object

This significantly speeds up String(array).
BUG=
==========

to

==========
Replace PushIfAbsent by a Stack object

This significantly speeds up String(array).
BUG=
==========

[commit-bot: I haz the power, 2016-03-14 14:44:24]

Committed patchset #10 (id:200001)

[commit-bot: I haz the power, 2016-03-14 14:45:12]

Description was changed from

==========
Replace PushIfAbsent by a Stack object

This significantly speeds up String(array).
BUG=
==========

to

==========
Replace PushIfAbsent by a Stack object

This significantly speeds up String(array).
BUG=

Committed: https://crrev.com/d3583574780848476dbde62122317452fddddb99
Cr-Commit-Position: refs/heads/master@{#34745}
==========

[commit-bot: I haz the power, 2016-03-14 14:45:14]

Patchset 10 (id:??) landed as
https://crrev.com/d3583574780848476dbde62122317452fddddb99
Cr-Commit-Position: refs/heads/master@{#34745}