Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2146293003:
[builtins] implement Array.prototype.includes in TurboFan (Closed)
Description[builtins] implement Array.prototype.includes in TurboFan
BUG=v8:5162
R=bmeurer@chromium.org, ishell@chromium.org
Committed: https://crrev.com/a488b5d8eb111a4883dc400bd826d079420edd68
Cr-Commit-Position: refs/heads/master@{#38223}
Patch Set 1 #
Total comments: 5
Patch Set 2 : Things that were missed #Patch Set 3 : More robust "init_k" block #Patch Set 4 : fix IsComparisonOpcode #
Total comments: 5
Patch Set 5 : Refactor based on bmeurer comments #
Total comments: 1
Patch Set 6 : fixit #
Total comments: 8
Patch Set 7 : try lots of tight loops #
Total comments: 7
Patch Set 8 : fix number equality checks #Patch Set 9 : move to builtins-array.cc and add indexed interceptor checks #
Total comments: 35
Patch Set 10 : Add a basic impl in ElementsAccessor, cleanup %ArrayIncludes_Slow, lots of new tests #
Total comments: 24
Patch Set 11 #Patch Set 12 : fix some things, rebase, rename some variables in TF, etc #
Total comments: 18
Patch Set 13 : Experiment: measure benefit of TF stub #Patch Set 14 : Address cbruni's comments, lots more tests, fixed some bugs #Patch Set 15 : debug fixup #
Total comments: 12
Patch Set 16 : Move impl to builtins-array.cc, fix DictionaryElementsAccessor impl #Patch Set 17 : More efficient version of the DICTIONARY_ELEMENTS fast case #Patch Set 18 : - #Patch Set 19 : Try to make MSVC happy #Patch Set 20 : Fix BranchIfSimd128Equal #
Total comments: 2
Messages
Total messages: 69 (28 generated)
The CQ bit was checked by caitp@igalia.com to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: No L-G-T-M from a valid reviewer yet. CQ run can only be started by full committers or once the patch has received an L-G-T-M from a full committer. Even if an L-G-T-M may have been provided, it was from a non-committer, _not_ a full super star committer. Committers are members of the group "project-v8-committers". Note that this has nothing to do with OWNERS files.
caitp@igalia.com changed reviewers: - bmeurer@chromium.org, ishell@chromium.org
PTAL at your leisure, this isn't really urgent or anything I haven't yet run the benchmarks from the bug, so it's entirely possible this does worse than the status quo, but I'll check that today. https://codereview.chromium.org/2146293003/diff/1/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/1/src/builtins/builtins.cc#ne... src/builtins/builtins.cc:399: assembler->GotoIf(assembler->Float64Equal( This init_k block is based on the understanding that Smis are the maximum length of JSArrays, and they can hold 29/30 bit signed integers (bit count might be off a bit) --- I __think__ this means any non-+Infinity HeapNumber at this point should result in setting `k` to 0 (per spec), but I'm not positive. I think it's possible to observe getting this wrong if indexed getters are installed on Array.prototype. I have some doubts about the way this is being done here, but I'm not sure what's the right way to go. https://codereview.chromium.org/2146293003/diff/1/src/code-stubs.cc File src/code-stubs.cc (right): https://codereview.chromium.org/2146293003/diff/1/src/code-stubs.cc#newcode24 src/code-stubs.cc:24: NanEqualsNan = 1 << 0, Hacky approach to reuse StrictEqualStub https://codereview.chromium.org/2146293003/diff/1/src/compiler/js-typed-lower... File src/compiler/js-typed-lowering.cc (right): https://codereview.chromium.org/2146293003/diff/1/src/compiler/js-typed-lower... src/compiler/js-typed-lowering.cc:848: // x === x is always true if x != NaN comment is clearly wrong, forgot to update after copy/pasting from StrictEquals https://codereview.chromium.org/2146293003/diff/1/src/js/array.js File src/js/array.js (right): https://codereview.chromium.org/2146293003/diff/1/src/js/array.js#newcode1510 src/js/array.js:1510: %GlobalPrint("InnerArrayIncludes\n"); debug edit from early on in this branch, to be removed --- also, ArrayIncludesInner remains in this file for use by TypedArrays (not yet ported) https://codereview.chromium.org/2146293003/diff/1/src/runtime/runtime-array.cc File src/runtime/runtime-array.cc (right): https://codereview.chromium.org/2146293003/diff/1/src/runtime/runtime-array.c... src/runtime/runtime-array.cc:39: if (argc < 0) { These changes are needed for any of these runtime functions implemented in TF, as far as I can tell
The CQ bit was checked by adamk@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_linux64_avx2_rel_ng on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_avx2_rel_ng/buil...) v8_linux64_avx2_rel_ng_triggered on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_avx2_rel_ng_trig...)
bmeurer@chromium.org changed reviewers: + bmeurer@chromium.org
Approach looks promising. First round of comments. https://codereview.chromium.org/2146293003/diff/60001/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/60001/src/builtins/builtins.c... src/builtins/builtins.cc:398: tagged_n.Bind(assembler->CallStub(call_to_integer, context, start_from)); ToInteger always returns a Smi if the value is in Smi range. So everything that is not a Smi cannot be less than len anyways, so you can simplify this code. https://codereview.chromium.org/2146293003/diff/60001/src/builtins/builtins.c... src/builtins/builtins.cc:437: assembler->GotoUnless(assembler->Uint32LessThan(k.value(), len.value()), This should probably by Int32LessThan, although it might not matter in this case. https://codereview.chromium.org/2146293003/diff/60001/src/builtins/builtins.c... src/builtins/builtins.cc:441: Node* element_k = assembler->CallStub(call_get_property, context, array, You shouldn't use GetPropertyStub here. You already know that you have fast elements, so if you also check above that the array prototype protector is intact (which guards that no one added elements in the Array prototype chain), you can just load the element from the backing store and do the comparison below. https://codereview.chromium.org/2146293003/diff/60001/src/builtins/builtins.c... src/builtins/builtins.cc:446: Node* result = assembler->CallStub(call_same_value_zero, context, This also shouldn't call out to a stub, but you should implement something like BranchIfSameValueZero(value, if_same, if_notsame) on the CodeStubAssembler and use that instead, otherwise this might even be slower than a naive C++ implementation.
https://codereview.chromium.org/2146293003/diff/60001/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/60001/src/builtins/builtins.c... src/builtins/builtins.cc:398: tagged_n.Bind(assembler->CallStub(call_to_integer, context, start_from)); On 2016/07/15 04:50:35, Benedikt Meurer wrote: > ToInteger always returns a Smi if the value is in Smi range. So everything that > is not a Smi cannot be less than len anyways, so you can simplify this code. The trouble is, for negative numbers that are less than -len, `k` is initialized to 0. So I don't think I can just return false in the non-Smi case. Am I missing something?
> The trouble is, for negative numbers that are less than -len, `k` is initialized > to 0. So I don't think I can just return false in the non-Smi case. Am I missing > something? Hm, I see. Missed that one indeed.
On 2016/07/15 05:59:22, Benedikt Meurer wrote: > > The trouble is, for negative numbers that are less than -len, `k` is > initialized > > to 0. So I don't think I can just return false in the non-Smi case. Am I > missing > > something? > > Hm, I see. Missed that one indeed. I've mostly addressed the comments here. There is a bug in this currently, I'll spend some time addressing it later tonight.
https://codereview.chromium.org/2146293003/diff/80001/src/code-stub-assembler.cc File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/80001/src/code-stub-assembler... src/code-stub-assembler.cc:478: BranchIf(CallRuntime(Runtime::kInlineStrictEqual, context, a, b), if_true, this was the problem --- fixing this made the perf results a lot worse, so I implemented a more proper SameValueZero here in the next patchset. The spec does not say anything about SameValueZero equating SIMD objects, so I'm not sure if it should or not. At the moment, it doesn't. Another option is to just call the StrictEquals stub and then fix the NaN stuff after, but that's probably still a slow path. With the change, the fast path is significantly faster, but not as fast as it could be maybe.
Wow, nice explorative work, Caitlin. https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.... src/builtins/builtins.cc:448: Label loop_body(assembler, 2, You really want one really tight loop per elements kind here. The loop for Smi elements will be super fast then, and same for non-holey double. For holey arrays and object elements it's a bit more involved, but still not too bad. Also I think you need to specialize depending on the type of searchElement, i.e.: 1. If Type(searchElement) is not Number, but the array is double/holey double, you can immediately return false. 2. If Type(searchElement) is Number and the array is double/holey double, convert the searchElement to a float64, and just do a fast comparison on the elements (in case of hole just skip, as undefined is not equal to any float64). and so on. https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.... src/builtins/builtins.cc:486: &if_slowpath); You can just turn the hole into undefined, since you checked the array protector. So the prototype chain cannot contain any elements, so any hole access always yields undefined. https://codereview.chromium.org/2146293003/diff/100001/src/code-stub-assemble... File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/100001/src/code-stub-assemble... src/code-stub-assembler.cc:474: void CodeStubAssembler::BranchIfSameValueZero(Node* a, Node* b, Node* context, Nice, this looks pretty good already. You'll have to handle Simd128Values tho (the SIMD.js spec defines that). See the implementation of Object::SameValueZero. https://codereview.chromium.org/2146293003/diff/100001/src/code-stub-assemble... src/code-stub-assembler.cc:513: &a_isstring, if_false); Instead of going to if_false here, you can check if a is a Simd128Value and if so, call to Runtime::kSameValueZero, otherwise go to if_false. The Simd128Value case doesn't need to be super fast for now (it's still not clear if it will make it into the ESnext spec).
Thanks for the look --- I started implementing `BranchIfSimd128Equal()` in code-stub-assembler.cc before I saw the suggestion to just call the runtime in that case. Some other comments about the looping strategy inline: https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.... src/builtins/builtins.cc:448: Label loop_body(assembler, 2, On 2016/07/15 17:59:55, Benedikt Meurer wrote: > You really want one really tight loop per elements kind here. The loop for Smi > elements will be super fast then, and same for non-holey double. For holey > arrays and object elements it's a bit more involved, but still not too bad. > > Also I think you need to specialize depending on the type of searchElement, > i.e.: > > 1. If Type(searchElement) is not Number, but the array is double/holey double, > you can immediately return false. > 2. If Type(searchElement) is Number and the array is double/holey double, > convert the searchElement to a float64, and just do a fast comparison on the > elements (in case of hole just skip, as undefined is not equal to any float64). > > and so on. This is a good idea, but currently this is not sound: as mentioned elsewhere, even with the valid Array prototype protector, it's still possible to end up on the fast path with elements on the prototype chain (subclasses of Array can do this without breaking the protector). So, these objects are not limited to own elements. It seems like a bug that the protector isn't updated for subclasses of Array, though https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.... src/builtins/builtins.cc:486: &if_slowpath); On 2016/07/15 17:59:55, Benedikt Meurer wrote: > You can just turn the hole into undefined, since you checked the array > protector. So the prototype chain cannot contain any elements, so any hole > access always yields undefined. I'm not sure, we still end up on the fast path with Array subclasses with indexed accessors on SubClass.prototype.
https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.... src/builtins/builtins.cc:448: Label loop_body(assembler, 2, Ah indeed, you also need to check that the prototype of the receiver is the Array prototype in addition to checking the protector, then it's sound. For other JSArray receivers, you can walk up the prototype chain up until either the Array prototype (if the protector is intact) or until null, and check for each object, if 1.) it's a JSReceiver, and 2.) doesn't have any elements, and 3.) doesn't have any indexed interceptors or other specialities, i.e. requires access checks, etc. In that case you can use the fast path (and you don't need to check when you see the hole). Note also that all of this is only necessary for holey arrays, i.e. if elements kind is FAST_(|SMI_|DOUBLE_)HOLEY_ELEMENTS. Otherwise you don't need to do any of this. https://codereview.chromium.org/2146293003/diff/100001/src/builtins/builtins.... src/builtins/builtins.cc:486: &if_slowpath); As mentioned above, indexed accessors in the prototype chain cannot use the fast path (if elements kind is holey).
https://codereview.chromium.org/2146293003/diff/120001/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/120001/src/builtins/builtins.... src/builtins/builtins.cc:463: assembler->Bind(&if_smiorobjects); There are lots of different tight loops here, to but it doesn't seem to make a significant difference (in the admittedly broken microbenchmark from the user) --- still ends up roughly the same (with a ~30% longer runtime than Array.prototype.indexOf() for arbitrary iteration counts with default options), and it does make the code a lot bigger and harder to read. https://codereview.chromium.org/2146293003/diff/120001/src/code-stub-assemble... File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/120001/src/code-stub-assemble... src/code-stub-assembler.cc:606: Node* int32_zero = Int32Constant(0); Code to test if it's safe to iterate only over own elements is added here --- may have gotten some of this slightly wrong, though
https://codereview.chromium.org/2146293003/diff/120001/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/120001/src/builtins/builtins.... src/builtins/builtins.cc:463: assembler->Bind(&if_smiorobjects); Awesome, I think this is the maximum you can get out of this. I agree tho, that we need some rearranging to make this easier to read (also some code sharing could happen with a TurboFan'ed version of Array.prototype.indexOf). Array.prototype.indexOf() is faster because there's special code in Crankshaft to inline a really fast, specialized version into the caller. This doesn't exist for includes, so being only ~30% slower with a general version is a pretty amazing result. To do a fair comparison, you could disable the kArrayIndexOf case for builtin inlining in hydrogen.cc. https://codereview.chromium.org/2146293003/diff/120001/src/code-stub-assemble... File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/120001/src/code-stub-assemble... src/code-stub-assembler.cc:606: Node* int32_zero = Int32Constant(0); Yeah, I think this needs to check for indexed interceptors/accessors as well. Otherwise looks pretty good.
https://codereview.chromium.org/2146293003/diff/120001/src/code-stub-assemble... File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/120001/src/code-stub-assemble... src/code-stub-assembler.cc:606: Node* int32_zero = Int32Constant(0); On 2016/07/17 06:03:18, Benedikt Meurer wrote: > Yeah, I think this needs to check for indexed interceptors/accessors as well. > Otherwise looks pretty good. added interceptors checks --- accessors are only possible with Dictionary elements, which are not handled in the slow case.
https://codereview.chromium.org/2146293003/diff/120001/src/code-stub-assemble... File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/120001/src/code-stub-assemble... src/code-stub-assembler.cc:606: Node* int32_zero = Int32Constant(0); On 2016/07/18 14:57:44, caitp wrote: > On 2016/07/17 06:03:18, Benedikt Meurer wrote: > > Yeah, I think this needs to check for indexed interceptors/accessors as well. > > Otherwise looks pretty good. > > added interceptors checks --- accessors are only possible with Dictionary > elements, which are not handled in the slow case. er, which _are_ handles in the slow case
https://codereview.chromium.org/2146293003/diff/120001/src/builtins/builtins.cc File src/builtins/builtins.cc (right): https://codereview.chromium.org/2146293003/diff/120001/src/builtins/builtins.... src/builtins/builtins.cc:463: assembler->Bind(&if_smiorobjects); On 2016/07/17 06:03:18, Benedikt Meurer wrote: > Awesome, I think this is the maximum you can get out of this. I agree tho, that > we need some rearranging to make this easier to read (also some code sharing > could happen with a TurboFan'ed version of Array.prototype.indexOf). > > Array.prototype.indexOf() is faster because there's special code in Crankshaft > to inline a really fast, specialized version into the caller. This doesn't exist > for includes, so being only ~30% slower with a general version is a pretty > amazing result. > > To do a fair comparison, you could disable the kArrayIndexOf case for builtin > inlining in hydrogen.cc. I had looked at adding a JSBuiltinReducer for ArrayIncludes, but it seems easier to do this in Crankshaft via TryInlineBuiltinMethodCall(), unless I'm missing something. It doesn't look like I can do anything other than rely on information generated by the Typer in TF, which may not be enough to tell me about an input's Map to make informed decisions in inlining. That said, when kArrayIndexOf reduction is disabled in crankshaft, the Array.prototype.includes test consistently does 3-5ms better than the indexOf test in that naive micro-benchmark, so that's a good sign.
> I had looked at adding a JSBuiltinReducer for ArrayIncludes, but it seems easier > to do this in Crankshaft via TryInlineBuiltinMethodCall(), unless I'm missing > something. It doesn't look like I can do anything other than rely on information > generated by the Typer in TF, which may not be enough to tell me about an > input's Map to make informed decisions in inlining. The JSBuiltinReducer will be able to do this in the future; I'm planning to add fundamental support for receiver-map based inlining in this quarter and probably add Array.prototype.push and maybe String.prototype.charCodeAt to serve as examples. In the meantime, you may want to add a fast case to Crankshaft > That said, when kArrayIndexOf reduction is disabled in crankshaft, the > Array.prototype.includes test consistently does 3-5ms better than the indexOf > test in that naive micro-benchmark, so that's a good sign. That's really impressive, and also suggests that we can do better for the general case of Array.prototype.indexOf *hint* *hint* :-)
bmeurer@chromium.org changed reviewers: + cbruni@chromium.org, ishell@chromium.org
Very nice work, another round of comments. Getting close to landable. Can you maybe some more tests to make sure includes properly handles (bails out) for exotic Array-like objects, dictionary Arrays, large holey Arrays, funny n inputs (i.e. -2^32, 2^32, etc.) Adding Igor (who did a lot of builtins with CodeStubAssembler already) and Camillo (for Array stuff) as reviewers. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... File src/builtins/builtins-array.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1293: Variable len(assembler, MachineRepresentation::kWord32), Nit: Can you rename those to len_var, k_var and n_var? To make it more obvious for the reader in the code below that those are variables. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1304: assembler->BranchIfFastJSArray(array, context, &init_len, &call_runtime); Nit: Move this before the { } block, and start the block with the init_len, i.e. Label init_len(assember); assembler->BranchIfFastJSArray(...); assembler->Bind(&init_len); { ... } https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1337: &abort); Instead of the abort label, go to the shared return_false. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1338: n.Bind(assembler->TruncateFloat64ToWord32(fp_n)); The fp_n can be outside the valid word32 range. And the TruncateFloat64ToWord32 to mod 2^32 truncation, which is probably not what you want. I.e. if fp_n is 2^32 then you bind n to 0 here. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1374: int32_t element_kinds[] = { Nit: Make this static const. And rename to kElementsKind. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1390: assembler->Switch(elements_kind, &return_false, element_kinds, Nice idea! https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1514: Callable callable = CodeFactory::StringEqual(assembler->isolate()); Please add a TODO here, that at some point we want to inline the String equality comparison here. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1628: if (kPointerSize == kDoubleSize) { You don't need this distinction. You can always compare just the upper bits. Or even load the double and then extract the high word using Float64ExtractHighWord32. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1660: if (kPointerSize == kDoubleSize) { See above. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins.cc File src/builtins/builtins.cc (left): https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins.... src/builtins/builtins.cc:46: Nit: undo the whitespace change. https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... src/code-stub-assembler.cc:613: Variable last_map(this, MachineRepresentation::kTagged); Move this into the check_prototype { } block below. https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... src/code-stub-assembler.cc:620: last_map.Bind(map); Move this into the check_prototype { } block below. https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... src/code-stub-assembler.cc:651: Branch(Word32Equal(holey_elements, int32_zero), if_true, &check_prototype); Nice! https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assembler.h File src/code-stub-assembler.h (right): https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... src/code-stub-assembler.h:125: void BranchIfSameValueZero(compiler::Node* a, compiler::Node* b, This is unused/inlined now. Remove this now.
what a beast!! :P Added some comments mostly to the C++ side of things, benedict should have covered the rest. I am pretty sure we do not have enough tests to cover all the special cases, if you don't mind, it would be nice if you could check that we try includes with all the element kinds (at least the array ones). + holey elements on the receiver plus a proxy on the prototype chain (may favorite examples). The same for your micro benchmarks (at least check how dict-elements perform) :) You mainly have some gaps in your array prototype checks. I added inline comments, but you should have a closer look at EnsureJSArrayWithWritableFastElements and especially PrototypeHasNoElements for all the steps. Let me know if my comments were more or less clear. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... File src/builtins/builtins-array.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1295: n(assembler, MachineRepresentation::kWord32); pretty please: use real variable names, k = key, n = ? :) https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1318: init_k_zero(assembler), init_k_n(assembler); again, I really like having readable variable names. https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... src/code-stub-assembler.cc:635: if_false); see below, this check can be folded into a single instance type check. https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... src/code-stub-assembler.cc:685: if_false); The interceptor checks can be folded into the instance type check above. Only API objects can have interceptors or would need access checks: GotoIf(Word32EqualOrLessThan(LoadMapInstanceType(proto_map), Int32Constant(LAST_CUSTOM_ELEMENTS_RECEIVER)), if_false); see PrototypeHasNoElements in builtins-array.cc https://codereview.chromium.org/2146293003/diff/160001/src/code-stub-assemble... src/code-stub-assembler.cc:691: if_false); NO_ELEMENTS is not used yet, you have to compare the elements() FixedArray against the empty_array (again see PrototypeHasNoElements). https://codereview.chromium.org/2146293003/diff/160001/src/runtime/runtime-ar... File src/runtime/runtime-array.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:492: Maybe let's postpone this to a followup CL: With your CL you will hit a performance cliff for dictionary-elements JSArrays since you will try to do a full lookup for all the dict elements. This has two disadvantages, 1. dictionaries are sparse, so you will do more lookups than necessary, 2. for each lookup you will instantiate a lookup iterator. I'd suggest to add a prototype-check for the receiver to see whether it has a valid JSArray prototype and then implement the fast-path in elements.cc to only perform a minimal amount of fast lookups. The slow path below would still stay and deal with all sorts of exotic array-like objects. https://codereview.chromium.org/2146293003/diff/160001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:494: len < std::numeric_limits<uint32_t>::max()) { this "fast-path" is not needed, see comments below. https://codereview.chromium.org/2146293003/diff/160001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:508: IsFastElementsKind(object->map()->elements_kind()); - the stable bool is not necessary GetElement (LookupIterator) will convert the index to name if it finds a proxy. - The LookupIterator will just work fine for dictionary elements (it will avoid the toString conversion for k for valid element indices on arrays, which are the ones handled by the elements backing store). I hope I didn't miss anything here... https://codereview.chromium.org/2146293003/diff/160001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:515: isolate, element_k, Object::GetElement(isolate, object, index)); Nit: JSReceiver::GetElement (doesn't change anything, but makes the implication that `object` is a JSReceiver clear)
Mostly clear. I have some other questions, though https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... File src/builtins/builtins-array.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1337: &abort); On 2016/07/19 03:53:19, Benedikt Meurer wrote: > Instead of the abort label, go to the shared return_false. The issue with that is that the return_false label wants `k_var` to be bound, even though return_false doesn't use it and has no successor blocks. If there's a way around this that I've missed, I'd love to hear it. Otherwise, I think all I can do is branch to a label, bind `k_var` to something, and exit to return_false https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1338: n.Bind(assembler->TruncateFloat64ToWord32(fp_n)); On 2016/07/19 03:53:18, Benedikt Meurer wrote: > The fp_n can be outside the valid word32 range. And the TruncateFloat64ToWord32 > to mod 2^32 truncation, which is probably not what you want. I.e. if fp_n is > 2^32 then you bind n to 0 here. `len` is pulled directly from kLengthOffset of JSArray (an Smi), and the above GotoIf bails out if `double(n) >= double(len)`. Does that not mean it's safe to truncate to 32 bits, since it must fit within an Smi range? https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1374: int32_t element_kinds[] = { On 2016/07/19 03:53:19, Benedikt Meurer wrote: > Nit: Make this static const. And rename to kElementsKind. Acknowledged. Requires a change to the Switch() prototype though (which may not be worth it) https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1514: Callable callable = CodeFactory::StringEqual(assembler->isolate()); On 2016/07/19 03:53:18, Benedikt Meurer wrote: > Please add a TODO here, that at some point we want to inline the String equality > comparison here. Acknowledged. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1628: if (kPointerSize == kDoubleSize) { On 2016/07/19 03:53:19, Benedikt Meurer wrote: > You don't need this distinction. You can always compare just the upper bits. Or > even load the double and then extract the high word using > Float64ExtractHighWord32. Acknowledged. This pattern is used elsewhere though (mainly CodeStubAssembler::TryLookupElement)
Thanks, questions addressed (and pinged danno about the Label issue). https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... File src/builtins/builtins-array.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1337: &abort); That seems suspicious. Maybe a bug in the CodeAssembler. Can you try to declare the Labels first, then the Variables? https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1338: n.Bind(assembler->TruncateFloat64ToWord32(fp_n)); It could still be negative, i.e. -2^32. Truncating that to word32 yields 0, which would pass the test below. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1374: int32_t element_kinds[] = { On 2016/07/19 19:59:21, caitp wrote: > On 2016/07/19 03:53:19, Benedikt Meurer wrote: > > Nit: Make this static const. And rename to kElementsKind. > > Acknowledged. Requires a change to the Switch() prototype though (which may not > be worth it) Acknowledged. https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1628: if (kPointerSize == kDoubleSize) { Hm, ok, we could also simplify that.
Sorry for chiming in so late. I'd like to first see a full includes implementation in elements.cc, mainly for two reasons. 1. we need a fast baseline first 2. I'd like to see the benefit of the turbofan stub clearly
https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... File src/builtins/builtins-array.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1338: n.Bind(assembler->TruncateFloat64ToWord32(fp_n)); On 2016/07/20 03:55:01, Benedikt Meurer wrote: > It could still be negative, i.e. -2^32. Truncating that to word32 yields 0, > which would pass the test below. well, here's the rationale for this I came up with: 1. `fp_len <= Smi::kMaxValue` --- This is always true 2. `fp_len >= 0` --- I believe this is always true, I don't believe the length field of a JSArray is ever set to a negative value. 3. IF `fp_n >= fp_len`, we can return false as no iteration occurs and no items are tested 4. IF `fp_n <= -fp_len`, then `(fp_len + fp_n) <= 0`, which will always result in binding `k` to 0 in the algorithm So, given all of those, I _think_ it's okay to truncate. I can't come up with an example where this does the wrong thing. In your example, assuming `fp_len == Smi::kMaxValue` and `fp_n == -(2^32)`, fp_n + fp_len would be negative and should result in binding k to 0. https://codereview.chromium.org/2146293003/diff/160001/src/runtime/runtime-ar... File src/runtime/runtime-array.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:508: IsFastElementsKind(object->map()->elements_kind()); On 2016/07/19 12:08:38, Camillo Bruni wrote: > - the stable bool is not necessary GetElement (LookupIterator) will convert the > index to name if it finds a proxy. > - The LookupIterator will just work fine for dictionary elements (it will avoid > the toString conversion for k for valid element indices on arrays, which are the > ones handled by the elements backing store). > > I hope I didn't miss anything here... Acknowledged. Will shrink the runtime version a lot then =)
Updated + some questions for Camillo https://codereview.chromium.org/2146293003/diff/180001/src/builtins/builtins-... File src/builtins/builtins-array.cc (left): https://codereview.chromium.org/2146293003/diff/180001/src/builtins/builtins-... src/builtins/builtins-array.cc:58: inline bool PrototypeHasNoElements(Isolate* isolate, JSObject* object) { Moved to JSObject to be usable from other files https://codereview.chromium.org/2146293003/diff/180001/src/code-stub-assemble... File src/code-stub-assembler.cc (right): https://codereview.chromium.org/2146293003/diff/180001/src/code-stub-assemble... src/code-stub-assembler.cc:474: void CodeStubAssembler::BranchIfSameValueZero(Node* a, Node* b, Node* context, this isn't really used in the TF implementation currently, will probably not be part of this when it's ready to land, unless people think it could be useful in the future. https://codereview.chromium.org/2146293003/diff/180001/src/code-stub-assemble... src/code-stub-assembler.cc:657: GotoIf(Int32LessThanOrEqual(LoadMapInstanceType(proto_map), Updated to avoid the interceptors/access check tests by relying on instance type instead https://codereview.chromium.org/2146293003/diff/180001/src/code-stub-assemble... src/code-stub-assembler.cc:662: GotoUnless(WordEqual(LoadElements(proto), empty_elements), if_false); Updated to point to the empty fixed array https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:1074: UNREACHABLE(); mostly for debugging, could make this fall back to the SlowPath when not implemented https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:1434: for (uint32_t k = start_from; k < length; ++k) { This comment _may_ be wrong --- if there's some sort of guarantee that indexes will always be in order, then I'm sure we can actually just iterate over the occupied slots in the dictionary https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:1842: if (value == undefined && elements_base->length() < length) { I think this assumption holds if there are no elements in the prototype chain https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:1848: if (!value->IsNumber()) { I prefer not to add these sorts of fast paths in a C++ version of this, because it looks like a pile of tech debt, even if it is faster. Maybe the TF and Crankshaft versions can be complicated like this, but maybe not the ElementsAccessor? https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:2672: return IncludesValueSlowPath(isolate, object, value, k + 1, length); I don't think a map check is really adequate for this (or for the similar DICTIONARY_ELEMENTS case), in case there are changes higher in the prototype chain. Is there a better way that doesn't totally sacrifice performance? Maybe just always bail out to the slow path after calling an accessor?
next round of comments and nits on the C++ part :). https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:1434: for (uint32_t k = start_from; k < length; ++k) { On 2016/07/21 at 03:28:55, caitp wrote: > This comment _may_ be wrong --- if there's some sort of guarantee that indexes will always be in order, then I'm sure we can actually just iterate over the occupied slots in the dictionary Right, this is probably tricky to get fast always. Dictionary are unsorted and cause quite a bit of pain (see the KeyAccumulator which has to sort a temp array for dict-elements). You can iterate all the dictionary entries directly as long as you don't see a accessor. The moment you see an accessor you have to restart the search using your approach. This might be slightly slower for the accessor case than your approach but would speed up the normal dictionary-elements case (not sure by how much). https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:1848: if (!value->IsNumber()) { I'd vouch for exactly the opposite. TF and Crankshaft are terrible to debug :) if we get a crash in there it takes significantly longer to find out what went wrong. For C++ we get a nice stack trace :P + it's way easier to understand. https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:2672: return IncludesValueSlowPath(isolate, object, value, k + 1, length); You can only have a dictionary (with potential accessors) in the SlowSloppyArguments case. Maybe duplicate the IncludesValueImpl for the two arguments subclasses, this way you might be able to share the dictionary part with the normal DICTIONARY_ELEMENTS case. https://codereview.chromium.org/2146293003/diff/180001/src/objects-inl.h File src/objects-inl.h (right): https://codereview.chromium.org/2146293003/diff/180001/src/objects-inl.h#newc... src/objects-inl.h:1137: bool JSObject::PrototypeHasNoElements(Isolate* isolate, JSObject* object) { indeed makes more sense here :) https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... File src/runtime/runtime-array.cc (right): https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:459: } nit: isolate->heap()->ToBoolean(result.FromJust()); https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:464: HandleScope shs(isolate); uber-nit: shs => sh (it's not a SealedHandleScope) https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:465: DCHECK(args.length() == 3); nit: DCHECK_EQ https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:474: // 2. Let len be ? ToLength(? Get(O, "length")). Maybe add a shortcut for JS_ARRAY instance types directly reading the length from the accessor, avoiding a full-fledged lookup. https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:477: handle(isolate->heap()->length_string(), isolate); nit: isolate->factory()->length_string() returns directly a handle https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:497: int64_t k; nit: despite the spec, can you give reasonable variable names, something like start_index? https://codereview.chromium.org/2146293003/diff/180001/test/mjsunit/es7/array... File test/mjsunit/es7/array-includes-receiver.js (right): https://codereview.chromium.org/2146293003/diff/180001/test/mjsunit/es7/array... test/mjsunit/es7/array-includes-receiver.js:8: // kinds, and various exotic receiver types, Massive Test! Awesome work!
bit more work on ElementsAccessor impl. https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:1848: if (!value->IsNumber()) { On 2016/07/21 08:01:55, Camillo Bruni wrote: > I'd vouch for exactly the opposite. TF and Crankshaft are terrible to debug :) > if we get a crash in there it takes significantly longer to find out what went > wrong. For C++ we get a nice stack trace :P + it's way easier to understand. Maybe the way to do this is to have just a C++ builtin, and a crankshaft inlined version for certain fast cases. Otherwise, it seems like the C++ code is starting to do a lot of the same stuff the TF version is doing. My goal here is to get the performance of A.p.includes more or less on par with indexOf (for the typical use-case), and possibly reduce startup time for V8 a little bit as a bonus. I don't think we want to have to implement a whole bunch of implementations of the same thing just to accomplish those goals. https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:2672: return IncludesValueSlowPath(isolate, object, value, k + 1, length); On 2016/07/21 08:01:55, Camillo Bruni wrote: > You can only have a dictionary (with potential accessors) in the > SlowSloppyArguments case. > > Maybe duplicate the IncludesValueImpl for the two arguments subclasses, this way > you might be able to share the dictionary part with the normal > DICTIONARY_ELEMENTS case. I agree that it only applies to the SlowArgumentsCase --- I think it might not be worth distinguishing between them, since this operation on Arguments objects is probably not going to be very common in the future (similarly, `Array.prototype.indexOf.call(arguments, ...)` is probably not very common pattern today). What do you think? Anyways, my question was really about whether a map check is enough to know if it's safe to continue on the "fast" path (where the prototype is assumed to have no elements). Is it possible for the map to remain the same even if the elements backing store changes? Or even if some map higher in the prototype chain is changed? Or if <receiver>.[[Prototype]] itself changes? It seems like there are a lot of things that invalidate the fast path, and checking them all could be more expensive than it's worth https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... File src/runtime/runtime-array.cc (right): https://codereview.chromium.org/2146293003/diff/180001/src/runtime/runtime-ar... src/runtime/runtime-array.cc:497: int64_t k; On 2016/07/21 08:01:55, Camillo Bruni wrote: > nit: despite the spec, can you give reasonable variable names, something like > start_index? Done.
danno@chromium.org changed reviewers: + danno@chromium.org
https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... File src/builtins/builtins-array.cc (right): https://codereview.chromium.org/2146293003/diff/160001/src/builtins/builtins-... src/builtins/builtins-array.cc:1337: &abort); On 2016/07/20 03:55:01, Benedikt Meurer wrote: > That seems suspicious. Maybe a bug in the CodeAssembler. Can you try to declare > the Labels first, then the Variables? I don't think this is a bug (although I haven't debugged it). The CodeStubAssembler is pretty dumb, it only knows how to merge variables in two situations, either at a label where you explicitly said the merge is needed, or at a label where all paths bind the value of the variables before forward-jumping to the label. It has no flow analysis to know that a variable that has been defined previously will never be used again, either. So if you jump to an label where a in-scope variable is bound on a single path, it must be bound on every path to that variable, regardless of wether the variable is actually used again or not. So, since k_var is declared top level, and snakes its way through the whole routine until any possible path to abort, if it isn't bound on every path, you will get an assert. One possible work around: immediately after the variable declaration you can bind it to undefined.
+ Jakob (to hear an answer from a question asked on the bug). The newest patch-set (#13) adds infrastructure for comparing the speed of the C++ version by its own, vs the TF version (which will call out to C++ code if it needs to). From the simple benchmark provided on the bug, it takes a little more than twice as long as the TF stub to get through 1,000,000 runs of the test. This number is pretty consistent if bumped up to 10,000,000 runs or 100,000,000 runs. The crankshaft reduction boosts the indexOf tests runs in about two thirds the time of the includes tests, or between 1/4 and 1/3 the time of the C++ version of includes. So, that's roughly the benefit that the TF stub provides, at least for simple benchmarks like this, if that answers the question. https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/180001/src/elements.cc#newcod... src/elements.cc:2672: return IncludesValueSlowPath(isolate, object, value, k + 1, length); On 2016/07/21 20:32:29, caitp wrote: > On 2016/07/21 08:01:55, Camillo Bruni wrote: > > You can only have a dictionary (with potential accessors) in the > > SlowSloppyArguments case. > > > > Maybe duplicate the IncludesValueImpl for the two arguments subclasses, this > way > > you might be able to share the dictionary part with the normal > > DICTIONARY_ELEMENTS case. > > I agree that it only applies to the SlowArgumentsCase --- I think it might not > be worth distinguishing between them, since this operation on Arguments objects > is probably not going to be very common in the future (similarly, > `Array.prototype.indexOf.call(arguments, ...)` is probably not very common > pattern today). > > What do you think? > > Anyways, my question was really about whether a map check is enough to know if > it's safe to continue on the "fast" path (where the prototype is assumed to have > no elements). Is it possible for the map to remain the same even if the elements > backing store changes? Or even if some map higher in the prototype chain is > changed? Or if <receiver>.[[Prototype]] itself changes? It seems like there are > a lot of things that invalidate the fast path, and checking them all could be > more expensive than it's worth the map-check was not enough --- I changed it to a `JSObject::PrototypeHasNoElements()` check. I think it should be fast enough most of the time, but it might be better to just leave and go to the proper slow path right away without the prototype elements test.
almost there, thanks for your patience! Added some more minor comments. https://codereview.chromium.org/2146293003/diff/220001/src/builtins/builtins.h File src/builtins/builtins.h (right): https://codereview.chromium.org/2146293003/diff/220001/src/builtins/builtins.... src/builtins/builtins.h:193: /* ES7 section 22.1.3.11 Array.prototype.includes */ \ nit: apparently we should refer to the spec sections by the more stable html anchor ES7 #sec-array.prototype.includes https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:474: uint32_t start_from, uint32_t length) { nit: expose this globally and use the common implementation from the builtin, this way we can reduce some duplication. https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:1467: if (search_for_hole) goto slow_path; shush, I didn't see this goto :D. For the sake of consistency you may resort to a fast helper that returns true on completing the fast-path plus a bool pointer for the result. https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:1513: LookupIterator it(isolate, receiver, k, LookupIterator::OWN); nit: You can minimally speed up the lookup iterator by passing in OWN_SKIP_INTERCEPTOR. In elements.cc we are sure that there are no elements on the prototype and we have not interceptors. https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:1921: if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) { nit: please add comments to each branch on what you are checking (it's easy to get confused with negated vs. non-negated checks) https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2363: template <ElementsKind Kind, typename ctype> nice :) https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2485: auto HasNeuteredArrayBuffer = [](JSObject* object) -> bool { can you just put this in a helper on this elements accessor? I'd like to keep the code style roughly the same, makes navigation and error spotting more efficient. https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2504: length); nit: If we have nothing on the prototype chain we can just do an early return here. https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2517: if (Kind < FLOAT32_ELEMENTS || Kind > FLOAT64_ELEMENTS) { I think you can use kind() which is consistent across all elements accessors
https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:474: uint32_t start_from, uint32_t length) { On 2016/07/28 12:57:29, Camillo Bruni wrote: > nit: expose this globally and use the common implementation from the builtin, > this way we can reduce some duplication. The builtin has to deal with non-JSObject receivers and lengths up to 2^53-1, whereas this one does not. While it is possible to make it support both, it results in messier code :( https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:1467: if (search_for_hole) goto slow_path; On 2016/07/28 12:57:29, Camillo Bruni wrote: > shush, I didn't see this goto :D. > For the sake of consistency you may resort to a fast helper that returns true on > completing the fast-path plus a bool pointer for the result. Done. https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:1513: LookupIterator it(isolate, receiver, k, LookupIterator::OWN); On 2016/07/28 12:57:29, Camillo Bruni wrote: > nit: You can minimally speed up the lookup iterator by passing in > OWN_SKIP_INTERCEPTOR. > In elements.cc we are sure that there are no elements on the prototype and we > have not interceptors. Done. https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:1921: if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) { On 2016/07/28 12:57:29, Camillo Bruni wrote: > nit: please add comments to each branch on what you are checking (it's easy to > get confused with negated vs. non-negated checks) Done. https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2485: auto HasNeuteredArrayBuffer = [](JSObject* object) -> bool { On 2016/07/28 12:57:29, Camillo Bruni wrote: > can you just put this in a helper on this elements accessor? > I'd like to keep the code style roughly the same, makes navigation and error > spotting more efficient. Done (moved to `static inline JSObject::HasNeuteredArrayBuffer(JSObject* object)`) --- and then subsequently deleted after realizing it's not needed https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2504: length); On 2016/07/28 12:57:29, Camillo Bruni wrote: > nit: If we have nothing on the prototype chain we can just do an early return > here. Actually, I think this whole thing can be removed, since the only caller never reaches this point if the buffer is detached (because neutering the buffer sets its length to 0, which causes the algorithm to abort early). Removed it, and added lots of new tests for TypedArray elements https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2517: if (Kind < FLOAT32_ELEMENTS || Kind > FLOAT64_ELEMENTS) { On 2016/07/28 12:57:29, Camillo Bruni wrote: > I think you can use kind() which is consistent across all elements accessors Done https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2520: } else if (search_value < std::numeric_limits<ctype>::min() || switched to numeric_limits<ctype>::lowest() rather than min()... TIL numeric_limits<T>::min() refers to the lowest positive value (which ends up being the same as epsilon, greater than 0). Luckily new tests caught that.
awesome job! I will do a final pass on monday morning so you can finally land it :) https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/220001/src/elements.cc#newcod... src/elements.cc:2520: } else if (search_value < std::numeric_limits<ctype>::min() || On 2016/07/29 at 20:27:47, caitp wrote: > switched to numeric_limits<ctype>::lowest() rather than min()... TIL numeric_limits<T>::min() refers to the lowest positive value (which ends up being the same as epsilon, greater than 0). Luckily new tests caught that. argh, good catch!
LGTM with nits. https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc#newcod... src/elements.cc:2003: } bah, sucks that you can just fold the hole check into the line below (DCHECK in-place in get_scalar). https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc#newcod... src/elements.cc:2043: // elementK->IsHeapNumber() && std::isnan(elementK->Number()) thanks for all the comments! https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc#newcod... src/elements.cc:2800: uint32_t start_from, uint32_t length) { nit: could you add DCHECK(JSObject::PrototypeHasNoElements(isolate, object)) now that we have the nice helper on JSObject (if you feel like improving the world, maybe also on the dictionary elements accessor ;-). https://codereview.chromium.org/2146293003/diff/280001/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/2146293003/diff/280001/src/objects.cc#newcode... src/objects.cc:19003: Handle<Object> from_index) { nit: Any particular reason this has to be on JSReceiver? Otherwise I'm fine with pushing the implementation back into runtime-arrays.cc or at least have the JSReceiver directly take sane input values (aka. uint32 / int64) since we usually do the argument conversion in the builtins/runtime functions. https://codereview.chromium.org/2146293003/diff/280001/src/objects.cc#newcode... src/objects.cc:19009: len_ = handle(JSArray::cast(*object)->length(), isolate); nit: A JSArray can only have sane length values (0 to 2^32-1 see JSArray::SetLength), thus you can avoid the handlification and only use the ToLength path for all the other objects.
Done https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc#newcod... src/elements.cc:1485: return false; Unfortunately, this doesn't work. The only thing that can be done is to search for accessors, and always take the ordered iteration path if any are found. Otherwise, it's possible to return true for elements that would be deleted by an accessor, but aren't because they're hit out of order. I'm not sure if the fast path is really worth it since you need to walk the list looking for accessors first. https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc#newcod... src/elements.cc:2800: uint32_t start_from, uint32_t length) { On 2016/08/01 07:23:47, Camillo Bruni wrote: > nit: could you add DCHECK(JSObject::PrototypeHasNoElements(isolate, object)) now > that we have the nice helper on JSObject (if you feel like improving the world, > maybe also on the dictionary elements accessor ;-). I've added the DCHECK for all of the ElementsAccessor implementations, since initially it should always be true https://codereview.chromium.org/2146293003/diff/280001/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/2146293003/diff/280001/src/objects.cc#newcode... src/objects.cc:19003: Handle<Object> from_index) { On 2016/08/01 07:23:47, Camillo Bruni wrote: > nit: Any particular reason this has to be on JSReceiver? > Otherwise I'm fine with pushing the implementation back into runtime-arrays.cc > or at least have the JSReceiver directly take sane input values (aka. uint32 / > int64) since we usually do the argument conversion in the builtins/runtime > functions. had moved it here to make it easy to share the c++ impl between teo builtins in patchset #13. I've now moved it back to runtime-array.cc https://codereview.chromium.org/2146293003/diff/280001/src/objects.cc#newcode... src/objects.cc:19009: len_ = handle(JSArray::cast(*object)->length(), isolate); On 2016/08/01 07:23:47, Camillo Bruni wrote: > nit: A JSArray can only have sane length values (0 to 2^32-1 see > JSArray::SetLength), thus you can avoid the handlification and only use the > ToLength path for all the other objects. updated to use ToArrayLength() for JS_ARRAY_TYPE
The CQ bit was checked by caitp@igalia.com to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_win64_rel_ng on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win64_rel_ng/builds/11582) v8_win_nosnap_shared_rel_ng on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_nosnap_shared_rel_ng...)
https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc#newcod... src/elements.cc:1485: return false; right. We already have a check HasAccessorsImpl() in place for this which can be fast (so you can convert the kAccessor case to UNREACHABLE). Given that dictionaries might be used for large arrays I still think this fast-path makes sense. https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc#newcod... src/elements.cc:2800: uint32_t start_from, uint32_t length) { On 2016/08/01 at 15:10:45, caitp wrote: > On 2016/08/01 07:23:47, Camillo Bruni wrote: > > nit: could you add DCHECK(JSObject::PrototypeHasNoElements(isolate, object)) now > > that we have the nice helper on JSObject (if you feel like improving the world, > > maybe also on the dictionary elements accessor ;-). > > I've added the DCHECK for all of the ElementsAccessor implementations, since initially it should always be true nice
The CQ bit was checked by caitp@igalia.com to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_linux64_gyp_rel_ng on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng/build...) v8_linux64_gyp_rel_ng_triggered on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng_trigg...)
The CQ bit was checked by caitp@igalia.com to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
seems to be building and passing tests everywhere now. So, the last thing is the question "should I delete the TF implementation" --- the benefits of it are mentioned at https://codereview.chromium.org/2146293003#msg38, but there is clearly a complexity cost that we may not want to pay. https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc File src/elements.cc (right): https://codereview.chromium.org/2146293003/diff/280001/src/elements.cc#newcod... src/elements.cc:1485: return false; On 2016/08/01 15:37:03, Camillo Bruni wrote: > right. We already have a check HasAccessorsImpl() in place for this which can be > fast (so you can convert the kAccessor case to UNREACHABLE). > Given that dictionaries might be used for large arrays I still think this > fast-path makes sense. I've changed this to avoid having to loop through the dictionary twice, so that's probably as good as it's going to get for dictionary elements
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
This is LGTM from me. I'd vote for not only keeping the TF version (which removes a lot of the otherwise unpredictable performance difference to a potential inlined version and thus improves the real world performance and predictability of V8/Chrome), but I'd even strongly suggest to do the same for various other array builtins like for example Array.prototype.indexOf, Array.prototype.lastIndexOf, and various others.
littledan@chromium.org changed reviewers: + littledan@chromium.org
Are there tests for a primitive receiver? Or for fewer arguments than expected? I don't see them here, but aren't they code paths that could come up in the TF stub? Maybe they were already included in surrounding code. https://codereview.chromium.org/2146293003/diff/380001/test/mjsunit/es7/array... File test/mjsunit/es7/array-includes-receiver.js (right): https://codereview.chromium.org/2146293003/diff/380001/test/mjsunit/es7/array... test/mjsunit/es7/array-includes-receiver.js:619: %ArrayBufferNeuter(array.buffer); FWIW this is spec-non-compliant behavior; a TODO (that A.p.i should throw) would be nice.
On 2016/08/01 21:50:23, Dan Ehrenberg wrote: > Are there tests for a primitive receiver? Or for fewer arguments than expected? > I don't see them here, but aren't they code paths that could come up in the TF > stub? Maybe they were already included in surrounding code. I've used a mix of omitting and not omitting the `fromIndex` parameter in all of these --- omitting the search value is tested (once) in array-includes.js, which only hits the TF path currently. So that looks like a hole in the coverage of the C++ builtins, but probably not a huge one. There are also tests that ToObject(receiver) throws / doesn't throw as expected, here and there --- but yeah, some other tests with primitive receivers might not be too bad. https://codereview.chromium.org/2146293003/diff/380001/test/mjsunit/es7/array... File test/mjsunit/es7/array-includes-receiver.js (right): https://codereview.chromium.org/2146293003/diff/380001/test/mjsunit/es7/array... test/mjsunit/es7/array-includes-receiver.js:619: %ArrayBufferNeuter(array.buffer); On 2016/08/01 21:50:23, Dan Ehrenberg wrote: > FWIW this is spec-non-compliant behavior; a TODO (that A.p.i should throw) would > be nice. It's actually perfectly spec-compliant, as far as I can see --- TypedArray.prototype.includes throws if neutered (ValidateTypedArray() does this), but otherwise, getting the length of a neutered typed array is spec'd to return `0`, which is perfectly valid and legal (and just causes the algorithm to return false). (https://tc39.github.io/ecma262/#sec-array.prototype.includes vs https://tc39.github.io/ecma262/#sec-%typedarray%.prototype.includes vs https://tc39.github.io/ecma262/#sec-get-%typedarray%.prototype.length)
On 2016/08/01 21:57:35, caitp wrote: > On 2016/08/01 21:50:23, Dan Ehrenberg wrote: > > Are there tests for a primitive receiver? Or for fewer arguments than > expected? > > I don't see them here, but aren't they code paths that could come up in the TF > > stub? Maybe they were already included in surrounding code. > > I've used a mix of omitting and not omitting the `fromIndex` parameter in all of > these --- omitting the search value is tested (once) in array-includes.js, which > only hits the TF path currently. So that looks like a hole in the coverage of > the C++ builtins, but probably not a huge one. > > There are also tests that ToObject(receiver) throws / doesn't throw as expected, > here and there --- but yeah, some other tests with primitive receivers might not > be too bad. > > https://codereview.chromium.org/2146293003/diff/380001/test/mjsunit/es7/array... > File test/mjsunit/es7/array-includes-receiver.js (right): > > https://codereview.chromium.org/2146293003/diff/380001/test/mjsunit/es7/array... > test/mjsunit/es7/array-includes-receiver.js:619: > %ArrayBufferNeuter(array.buffer); > On 2016/08/01 21:50:23, Dan Ehrenberg wrote: > > FWIW this is spec-non-compliant behavior; a TODO (that A.p.i should throw) > would > > be nice. > > It's actually perfectly spec-compliant, as far as I can see --- > TypedArray.prototype.includes throws if neutered (ValidateTypedArray() does > this), but otherwise, getting the length of a neutered typed array is spec'd to > return `0`, which is perfectly valid and legal (and just causes the algorithm to > return false). > > (https://tc39.github.io/ecma262/#sec-array.prototype.includes vs > https://tc39.github.io/ecma262/#sec-%25typedarray%25.prototype.includes vs > https://tc39.github.io/ecma262/#sec-get-%25typedarray%25.prototype.length) actually, looks like tests for primitive receivers are handled in some other test files (like array-includes-to-object-strict/sloppy.js), so there might not be much to add there.
The CQ bit was checked by caitp@igalia.com
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/2146293003/#ps380001 (title: "Fix BranchIfSimd128Equal")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Message was sent while issue was closed.
Committed patchset #20 (id:380001)
Message was sent while issue was closed.
Description was changed from ========== [builtins] implement Array.prototype.includes in TurboFan BUG=v8:5162 R=bmeurer@chromium.org, ishell@chromium.org ========== to ========== [builtins] implement Array.prototype.includes in TurboFan BUG=v8:5162 R=bmeurer@chromium.org, ishell@chromium.org Committed: https://crrev.com/a488b5d8eb111a4883dc400bd826d079420edd68 Cr-Commit-Position: refs/heads/master@{#38223} ==========
Message was sent while issue was closed.
Patchset 20 (id:??) landed as https://crrev.com/a488b5d8eb111a4883dc400bd826d079420edd68 Cr-Commit-Position: refs/heads/master@{#38223}
Message was sent while issue was closed.
A revert of this CL (patchset #20 id:380001) has been created in https://codereview.chromium.org/2202163002/ by machenbach@chromium.org. The reason for reverting is: [Sheriff] Breaks: https://build.chromium.org/p/client.v8.ports/builders/V8%20Arm%20-%20builder/.... |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
