Speedup JSReceiver::GetKeys

Improve JSReceiver::GetKeys Speed
The core bottleneck lies in N-square cost of array union. Depending on the size
of the arrays involved it makes sense to rely on a hash-set/table for the lookup.

LOG=N
BUG=v8:2904
Committed: https://crrev.com/007eac94a14f5b4db36babeaa1e8fd677aec2c17
Cr-Commit-Position: refs/heads/master@{#30797}

[Camillo Bruni, 2015-09-08 15:31:10]

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

[commit-bot: I haz the power, 2015-09-08 15:31:17]

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

[commit-bot: I haz the power, 2015-09-08 16:21:45]

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

[commit-bot: I haz the power, 2015-09-08 16:21:46]

Dry run: This issue passed the CQ dry run.

[Camillo Bruni, 2015-09-09 09:33:59]

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

[Camillo Bruni, 2015-09-09 09:34:00]

PTAL

I think some more work could be done, but I am lacking the proper data
structures.
Something like a SortedHashSet would be perfect, but it seems like the existing
implementation doesn't expose a proper C++ interface (those used by JSSet and
JSMap). Then pass that along from GetKeys to all Union* calls as accumulator.

https://codereview.chromium.org/1316213008/diff/20001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/1316213008/diff/20001/src/objects.cc#newcode1...
src/objects.cc:15167: Handle<ObjectHashTable> ObjectHashTable::Put(Isolate*
isolate,
duplicated for tryout... has to be reverted

https://codereview.chromium.org/1316213008/diff/20001/src/objects.cc#newcode1...
src/objects.cc:15185: int32_t hash) {
again, test duplication

[Camillo Bruni, 2015-09-11 15:53:01]

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

[commit-bot: I haz the power, 2015-09-11 15:53:15]

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

[commit-bot: I haz the power, 2015-09-11 15:55:55]

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

[commit-bot: I haz the power, 2015-09-11 15:55:56]

Dry run: Try jobs failed on following builders:
  v8_presubmit on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/5727)

[Camillo Bruni, 2015-09-11 16:12:22]

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

[commit-bot: I haz the power, 2015-09-11 16:12:35]

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

[commit-bot: I haz the power, 2015-09-11 16:39:36]

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

[commit-bot: I haz the power, 2015-09-11 16:39:36]

Dry run: This issue passed the CQ dry run.

[Camillo Bruni, 2015-09-14 07:34:03]

The CQ bit was checked by cbruni@chromium.org

[Camillo Bruni, 2015-09-14 07:34:05]

PTAL

https://codereview.chromium.org/1316213008/diff/60001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/1316213008/diff/60001/src/objects.cc#newcode6561
src/objects.cc:6561: if (length_ * count < 100) return;
I tried a bit with different values and 100 turned out to be roughly ok...

https://codereview.chromium.org/1316213008/diff/60001/src/objects.cc#newcode6562
src/objects.cc:6562: set_ = ObjectHashTable::New(isolate_, length_);
Technically this should be a set but we only have a reasonable dict
implementation. So we waste a bit of memory here in the case we fall back to
dict.

https://codereview.chromium.org/1316213008/diff/80001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/1316213008/diff/80001/src/objects.cc#newcode6561
src/objects.cc:6561: if (length_ * count < 100) return;
I tried a bit with different values and 100 turned out to be roughly ok...

https://codereview.chromium.org/1316213008/diff/80001/src/objects.cc#newcode6562
src/objects.cc:6562: set_ = ObjectHashTable::New(isolate_, length_);
Technically this should be a set but we only have a reasonable dict
implementation. So we waste a bit of memory here in the case we fall back to
dict.

https://codereview.chromium.org/1316213008/diff/80001/src/runtime/runtime-arr...
File src/runtime/runtime-array.cc (right):

https://codereview.chromium.org/1316213008/diff/80001/src/runtime/runtime-arr...
src/runtime/runtime-array.cc:201: if (!array->elements()->IsDictionary()) {
Early return..

[commit-bot: I haz the power, 2015-09-14 07:34:11]

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

[commit-bot: I haz the power, 2015-09-14 07:34:12]

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

[commit-bot: I haz the power, 2015-09-14 07:34:13]

No L-G-T-M from a valid reviewer yet. Only full committers are accepted.
Even if an L-G-T-M may have been provided, it was from a non-committer,
_not_ a full super star committer.
See http://www.chromium.org/getting-involved/become-a-committer
Note that this has nothing to do with OWNERS files.

[Camillo Bruni, 2015-09-14 07:45:40]

https://codereview.chromium.org/1316213008/diff/80001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/1316213008/diff/80001/src/objects.h#newcode10471
src/objects.h:10471: class KeyAccumulator final BASE_EMBEDDED {
I wasn't really sure where to put the class declaration

[Camillo Bruni, 2015-09-15 15:05:27]

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

[Camillo Bruni, 2015-09-16 10:49:13]

cbruni@chromium.org changed reviewers:
- jkummerow@chromium.org

[Camillo Bruni, 2015-09-16 10:49:13]

PTAL
Updated CL with OrderedHashSet

[Camillo Bruni, 2015-09-16 10:49:18]

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

[commit-bot: I haz the power, 2015-09-16 10:49:25]

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

[commit-bot: I haz the power, 2015-09-16 11:55:48]

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

[commit-bot: I haz the power, 2015-09-16 11:55:49]

Dry run: Try jobs failed on following builders:
  v8_linux_dbg on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_dbg/builds/8710)

[Igor Sheludko, 2015-09-17 09:55:12]

Cool stuff! Mostly nits:

https://codereview.chromium.org/1316213008/diff/80001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/1316213008/diff/80001/src/objects.cc#newcode6492
src/objects.cc:6492: int KeyAccumulator::GetLength() { return length_; }
I think it's better to implement simple get/set methods inline.

https://codereview.chromium.org/1316213008/diff/80001/src/objects.cc#newcode6562
src/objects.cc:6562: set_ = ObjectHashTable::New(isolate_, length_);
On 2015/09/14 at 07:34:04, cbruni wrote:
> Technically this should be a set but we only have a reasonable dict
implementation. So we waste a bit of memory here in the case we fall back to
dict.

Maybe it's worth implementing an ObjectHashSet. It should be pretty
straightforward.

https://codereview.chromium.org/1316213008/diff/80001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/1316213008/diff/80001/src/objects.h#newcode10474
src/objects.h:10474: : isolate_(isolate), keys_(), set_(), length_(0) {}
keys_() and set_() are not really necessary here.

https://codereview.chromium.org/1316213008/diff/120001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/1316213008/diff/120001/src/objects.cc#newcode...
src/objects.cc:6500: int KeyAccumulator::GetLength() { return length_; }
Please move this implementation to the class definition.

https://codereview.chromium.org/1316213008/diff/120001/src/objects.cc#newcode...
src/objects.cc:15545: // Read the enxisting bucket values.
s/enxisting/existing/

https://codereview.chromium.org/1316213008/diff/140001/src/elements.cc
File src/elements.cc (right):

https://codereview.chromium.org/1316213008/diff/140001/src/elements.cc#newcod...
src/elements.cc:876: virtual void AddElementsToFixedArrayWithAccumulator(
WDYT about AddElementsToKeyAccumulator() name?

https://codereview.chromium.org/1316213008/diff/140001/src/elements.cc#newcod...
src/elements.cc:887: Handle<Object> value =
ElementsAccessorSubclass::GetImpl(from, i);
HasEntryImpl() returned true, so value must not be hole here.

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc#newcode...
src/objects.cc:6736: FixedArray::NON_SYMBOL_KEYS);
Why do you use a different filter than in the old code?

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc#newcode...
src/objects.cc:15432: Isolate* isolate = table->GetIsolate();
Spurious change.

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc#newcode...
src/objects.cc:15447: Isolate* isolate = table->GetIsolate();
Spurious change.

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc#newcode...
src/objects.cc:15659: table->set(new_index + 1, Smi::FromInt(previous_entry));
I think "+ kChainOffset" is better than "+ 1" for readability.

https://codereview.chromium.org/1316213008/diff/140001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/1316213008/diff/140001/src/objects.h#newcode3691
src/objects.h:3691: Object* next_entry = get(EntryToIndex(entry) + entrysize);
s/entrysize/kChainOffset/g (for readability).

https://codereview.chromium.org/1316213008/diff/140001/src/objects.h#newcode3693
src/objects.h:3693: }
Please add a blank line here.

https://codereview.chromium.org/1316213008/diff/140001/src/runtime/runtime-ob...
File src/runtime/runtime-object.cc (right):

https://codereview.chromium.org/1316213008/diff/140001/src/runtime/runtime-ob...
src/runtime/runtime-object.cc:1004: offset += 100;
int end = min(offset, length);

https://codereview.chromium.org/1316213008/diff/140001/src/runtime/runtime-ob...
src/runtime/runtime-object.cc:1005: for (int i = offset - 100; i < offset && i <
length; i++) {
...; i < end; ...

[Camillo Bruni, 2015-09-17 11:01:08]

adressed your feedback

https://codereview.chromium.org/1316213008/diff/140001/src/elements.cc
File src/elements.cc (right):

https://codereview.chromium.org/1316213008/diff/140001/src/elements.cc#newcod...
src/elements.cc:876: virtual void AddElementsToFixedArrayWithAccumulator(
On 2015/09/17 at 09:55:12, Igor Sheludko wrote:
> WDYT about AddElementsToKeyAccumulator() name?

Indeed better choice.

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc#newcode...
src/objects.cc:6736: FixedArray::NON_SYMBOL_KEYS);
On 2015/09/17 at 09:55:12, Igor Sheludko wrote:
> Why do you use a different filter than in the old code?

my mistake :)

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc#newcode...
src/objects.cc:15432: Isolate* isolate = table->GetIsolate();
On 2015/09/17 at 09:55:12, Igor Sheludko wrote:
> Spurious change.

reverted

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc#newcode...
src/objects.cc:15447: Isolate* isolate = table->GetIsolate();
On 2015/09/17 at 09:55:12, Igor Sheludko wrote:
> Spurious change.

reverted

https://codereview.chromium.org/1316213008/diff/140001/src/objects.cc#newcode...
src/objects.cc:15659: table->set(new_index + 1, Smi::FromInt(previous_entry));
On 2015/09/17 at 09:55:12, Igor Sheludko wrote:
> I think "+ kChainOffset" is better than "+ 1" for readability.

indeed

https://codereview.chromium.org/1316213008/diff/140001/src/runtime/runtime-ob...
File src/runtime/runtime-object.cc (right):

https://codereview.chromium.org/1316213008/diff/140001/src/runtime/runtime-ob...
src/runtime/runtime-object.cc:1005: for (int i = offset - 100; i < offset && i <
length; i++) {
On 2015/09/17 at 09:55:12, Igor Sheludko wrote:
> ...; i < end; ...

updated

[Igor Sheludko, 2015-09-17 11:48:45]

Lgtm with a couple of nits:

https://codereview.chromium.org/1316213008/diff/160001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/1316213008/diff/160001/src/objects.cc#newcode...
src/objects.cc:6610: int KeyAccumulator::GetLength() { return length_; }
Please move this trivial implementation to class definition.

https://codereview.chromium.org/1316213008/diff/160001/src/objects.cc#newcode...
src/objects.cc:15651: // Read the enxisting bucket values.
eNxisting -> existing

[Camillo Bruni, 2015-09-17 12:19:21]

addressing nits

[Camillo Bruni, 2015-09-17 12:19:25]

The CQ bit was checked by cbruni@chromium.org

[Camillo Bruni, 2015-09-17 12:19:25]

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

[commit-bot: I haz the power, 2015-09-17 12:19:38]

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

[Camillo Bruni, 2015-09-17 12:21:11]

The CQ bit was unchecked by cbruni@chromium.org

[Camillo Bruni, 2015-09-17 12:27:19]

The CQ bit was checked by cbruni@chromium.org

[Camillo Bruni, 2015-09-17 12:27:20]

The patchset sent to the CQ was uploaded after l-g-t-m from ishell@chromium.org
Link to the patchset: https://codereview.chromium.org/1316213008/#ps200001
(title: "Compilation Fix")

[commit-bot: I haz the power, 2015-09-17 12:27:30]

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

[commit-bot: I haz the power, 2015-09-17 12:52:50]

Committed patchset #11 (id:200001)

[commit-bot: I haz the power, 2015-09-17 12:53:02]

Patchset 11 (id:??) landed as
https://crrev.com/007eac94a14f5b4db36babeaa1e8fd677aec2c17
Cr-Commit-Position: refs/heads/master@{#30797}