Array.prototype.reverse should call [[HasProperty]] on elements before [[Get]]

Array.prototype.reverse should call [[HasProperty]] on elements before [[Get]]

This is a change from ES5 to ES6: When reversing an array, first it is checked
whether the element exists, before the element is looked up. The order in ES6
is

[[HasElement]] lower
[[Get]] lower (if present)
[[HasElement]] upper
[[Get]] upper (if present)

In ES5, on the other hand, the order was

[[Get]] lower
[[Get]] upper
[[HasElement]] lower
[[HasElement]] upper

To mitigate the performance impact, this patch implements a new, third copy
of reversing arrays if %_HasPackedElements. This allows us to skip all
membership tests, and a quick and dirty benchmark shows that the new version
is faster:

Over 4 runs, the slowest for the new version:
d8> var start = Date.now(); for (var i = 0; i < 100000000; i++) [1, 2, 3, 4, 5].reverse(); Date.now() - start
4658

Over 3 runs, the fastest for the old version:
d8> var start = Date.now(); for (var i = 0; i < 100000000; i++) [1, 2, 3, 4, 5].reverse(); Date.now() - start
5176

BUG=v8:4223
R=adamk
LOG=Y

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

[Dan Ehrenberg, 2015-07-16 03:11:16]

I couldn't figure out how to trigger sparse reverse. If anyone has advice,
that'd be appreciated.

[adamk, 2015-07-16 19:39:20]

High-level question: this should be visible in ES5 with getters anyway, so I
don't think proxies come into play. Any idea why ES6 decided to change the
ordering?

[adamk, 2015-07-16 19:55:47]

Answering my own question:

https://bugs.ecmascript.org/show_bug.cgi?id=2607

Looks like neither Allen nor Brian realized that this changed behavior in ES5,
not just ES6 proxies.

[adamk, 2015-07-16 20:06:24]

I would tend to agree that this behavior change isn't going to break real code.
Just slightly annoyed by all the spec churn (as we burn down the list of ES6
bugs).

[Dan Ehrenberg, 2015-07-16 20:43:58]

On 2015/07/16 20:06:24, adamk wrote:
> I would tend to agree that this behavior change isn't going to break real
code.
> Just slightly annoyed by all the spec churn (as we burn down the list of ES6
> bugs).

Seems strange to optimize for proxies here, if that's all it was, when it's a
pessimization on arrays. We'll pay closer attention next time to all this churn,
but for this time, I think we should just go with the spec to make sure things
are all locked down across browsers for good. Or, what do you think?

[Dan Ehrenberg, 2015-07-16 21:51:51]

PTAL

[Dan Ehrenberg, 2015-07-16 21:52:09]

PTAL

[adamk, 2015-07-16 22:08:14]

https://codereview.chromium.org/1238593003/diff/40001/src/array.js
File src/array.js (left):

https://codereview.chromium.org/1238593003/diff/40001/src/array.js#oldcode571
src/array.js:571: if (!IS_UNDEFINED(current_i) || low in array) {
As discussed offline, I don't think SparseReverse needs to be changed at all,
since it's guaranteed that [[Get]] and [[HasProperty]] are both side-effect free
in here.

https://codereview.chromium.org/1238593003/diff/40001/src/array.js
File src/array.js (right):

https://codereview.chromium.org/1238593003/diff/40001/src/array.js#newcode637
src/array.js:637: } else if (%_HasFastPackedElements(array)) {
This needs an IS_ARRAY check (you can cache this above). Please add a test
covering this. This object violates the contract PackedArrayReverse() is
expecting:

{ length: 2, 0: 'foo', __proto__: { get 1() { delete this[1] } } }

Arrays can't have this problem because of their exotic 'length'.

https://codereview.chromium.org/1238593003/diff/40001/src/array.js#newcode640
src/array.js:640: return InnerArrayReverse(array, len);
how about "GenericArrayReverse" as the name for this instead?

https://codereview.chromium.org/1238593003/diff/40001/test/mjsunit/es6/array-...
File test/mjsunit/es6/array-reverse-order.js (right):

https://codereview.chromium.org/1238593003/diff/40001/test/mjsunit/es6/array-...
test/mjsunit/es6/array-reverse-order.js:10: {length:2, get 0(){delete this[0];},
1: "b"}))
Can you spread this out over multiple statements to make it a bit more readable?
I.e., assign the object to a variable, assign the result of reverse.

Also, "order" in the name of this test doesn't help me much. I'd just drop it
from the name, leaving this as es6/array-reverse.js

[Toon Verwaest, 2015-07-16 22:15:31]

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

[Toon Verwaest, 2015-07-16 22:15:32]

https://codereview.chromium.org/1238593003/diff/40001/src/array.js
File src/array.js (right):

https://codereview.chromium.org/1238593003/diff/40001/src/array.js#newcode637
src/array.js:637: } else if (%_HasFastPackedElements(array)) {
On 2015/07/16 22:08:13, adamk wrote:
> This needs an IS_ARRAY check (you can cache this above). Please add a test
> covering this. This object violates the contract PackedArrayReverse() is
> expecting:
> 
> { length: 2, 0: 'foo', __proto__: { get 1() { delete this[1] } } }
> 
> Arrays can't have this problem because of their exotic 'length'.

Do we have objects with packed elements that are not arrays?

[Dan Ehrenberg, 2015-07-16 22:16:49]

littledan@chromium.org changed reviewers:
- verwaest@chromium.org

[Dan Ehrenberg, 2015-07-16 22:16:49]

https://codereview.chromium.org/1238593003/diff/40001/src/array.js
File src/array.js (left):

https://codereview.chromium.org/1238593003/diff/40001/src/array.js#oldcode571
src/array.js:571: if (!IS_UNDEFINED(current_i) || low in array) {
On 2015/07/16 22:08:13, adamk wrote:
> As discussed offline, I don't think SparseReverse needs to be changed at all,
> since it's guaranteed that [[Get]] and [[HasProperty]] are both side-effect
free
> in here.

Done.

https://codereview.chromium.org/1238593003/diff/40001/src/array.js
File src/array.js (right):

https://codereview.chromium.org/1238593003/diff/40001/src/array.js#newcode637
src/array.js:637: } else if (%_HasFastPackedElements(array)) {
On 2015/07/16 22:08:13, adamk wrote:
> This needs an IS_ARRAY check (you can cache this above). Please add a test
> covering this. This object violates the contract PackedArrayReverse() is
> expecting:
> 
> { length: 2, 0: 'foo', __proto__: { get 1() { delete this[1] } } }
> 
> Arrays can't have this problem because of their exotic 'length'.

Done.

https://codereview.chromium.org/1238593003/diff/40001/src/array.js#newcode640
src/array.js:640: return InnerArrayReverse(array, len);
On 2015/07/16 22:08:13, adamk wrote:
> how about "GenericArrayReverse" as the name for this instead?

Done.

[adamk, 2015-07-16 22:16:50]

On 2015/07/16 22:15:32, Toon Verwaest wrote:
> https://codereview.chromium.org/1238593003/diff/40001/src/array.js
> File src/array.js (right):
> 
> https://codereview.chromium.org/1238593003/diff/40001/src/array.js#newcode637
> src/array.js:637: } else if (%_HasFastPackedElements(array)) {
> On 2015/07/16 22:08:13, adamk wrote:
> > This needs an IS_ARRAY check (you can cache this above). Please add a test
> > covering this. This object violates the contract PackedArrayReverse() is
> > expecting:
> > 
> > { length: 2, 0: 'foo', __proto__: { get 1() { delete this[1] } } }
> > 
> > Arrays can't have this problem because of their exotic 'length'.
> 
> Do we have objects with packed elements that are not arrays?

I'm guessing you are saying the answer is no? You're the expert on elements
transitions :)

[adamk, 2015-07-16 22:19:09]

lgtm

[Dan Ehrenberg, 2015-07-16 22:31:15]

The CQ bit was checked by littledan@chromium.org

[commit-bot: I haz the power, 2015-07-16 22:31:33]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1238593003/60001

[commit-bot: I haz the power, 2015-07-16 23:12:13]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2015-07-16 23:12:34]

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