[runtime] use std::vector in KeyAccumulator

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 39c30336ea755b86a1c9a25fccbba19d76adb284..8639bde44ade6880eb53e49be6289d03f08691a0 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -7502,7 +7502,7 @@ Handle<FixedArray> JSObject::GetEnumPropertyKeys(Handle<JSObject> object,
 
 
 KeyAccumulator::~KeyAccumulator() {
-  for (int i = 0; i < elements_.length(); i++) {
+  for (uint32_t i = 0; i < elements_.size(); i++) {

[Igor Sheludko, 2015/10/22 21:42:57]

I guess it should be size_t or you will have compilation issues on 64-bit.

[Camillo Bruni, 2015/10/23 08:56:35]

right

     delete elements_[i];
   }
 }
@@ -7523,7 +7523,7 @@ Handle<FixedArray> KeyAccumulator::GetKeys(GetKeysConversion convert) {
   Handle<FixedArray> result = isolate_->factory()->NewFixedArray(length_);
   int index = 0;
   int properties_index = 0;
-  for (int level = 0; level < levelLengths_.length(); level++) {
+  for (uint32_t level = 0; level < levelLengths_.size(); level++) {

[Igor Sheludko, 2015/10/22 21:42:57]

Ditto.

     int num_total = levelLengths_[level];
     int num_elements = 0;
     if (num_total < 0) {
@@ -7531,9 +7531,9 @@ Handle<FixedArray> KeyAccumulator::GetKeys(GetKeysConversion convert) {
       // proxy, hence we skip the integer keys in |elements_| since proxies
       // define the complete ordering.
       num_total = -num_total;
-    } else if (level < elements_.length()) {
-      List<uint32_t>* elements = elements_[level];
-      num_elements = elements->length();
+    } else if (level < elements_.size()) {
+      std::vector<uint32_t>* elements = elements_[level];
+      num_elements = static_cast<int>(elements->size());
       for (int i = 0; i < num_elements; i++) {
         Handle<Object> key;
         if (convert == KEEP_NUMBERS) {
@@ -7561,22 +7561,8 @@ Handle<FixedArray> KeyAccumulator::GetKeys(GetKeysConversion convert) {
 
 namespace {
 
-class FindKey {
- public:
-  explicit FindKey(uint32_t key) : key_(key) {}
-  int operator()(uint32_t* entry) {
-    if (*entry == key_) return 0;
-    return *entry < key_ ? -1 : 1;
-  }
-
- private:
-  uint32_t key_;
-};
-
-
-bool AccumulatorHasKey(List<uint32_t>* sub_elements, uint32_t key) {
-  int index = SortedListBSearch(*sub_elements, FindKey(key));
-  return index != -1;
+bool AccumulatorHasKey(std::vector<uint32_t>* sub_elements, uint32_t key) {
+  return std::binary_search(sub_elements->begin(), sub_elements->end(), key);
 }
 
 }  // namespace
@@ -7584,12 +7570,23 @@ bool AccumulatorHasKey(List<uint32_t>* sub_elements, uint32_t key) {
 
 bool KeyAccumulator::AddKey(uint32_t key) {
   // Make sure we do not add keys to a proxy-level (see AddKeysFromProxy).
+  // We mark proxy-levels with a negative length
   DCHECK_LE(0, levelLength_);
-  int lookup_limit = elements_.length();
-  for (int i = 0; i < lookup_limit; i++) {
-    if (AccumulatorHasKey(elements_[i], key)) return false;
+  // Binary search over all but the last level. The last one might not be
+  // sorted yet.
+  for (uint32_t i = 1; i < elements_.size(); i++) {

[Igor Sheludko, 2015/10/22 21:42:57]

Ditto.

+    if (AccumulatorHasKey(elements_[i - 1], key)) return false;
+  }
+  if (elementKeysAddCheckLimit_ == INCLUDE_CURRENT_LEVEL) {
+    // the last level may have not been sorted yet, hence we have to do
+    // a linear search here if required.
+    auto last_level = elements_.back();
+    if (std::find(last_level->begin(), last_level->end(), key) !=
+        last_level->end()) {
+      return false;
+    }
   }
-  elements_[lookup_limit - 1]->Add(key);
+  elements_.back()->push_back(key);
   length_++;
   levelLength_++;
   return true;
@@ -7683,32 +7680,28 @@ void KeyAccumulator::AddKeysFromProxy(Handle<JSObject> array_like) {
 }
 
 
-namespace {
-
-// Used for sorting indices in a List<uint32_t>.
-int compareUInt32(const uint32_t* ap, const uint32_t* bp) {
-  uint32_t a = *ap;
-  uint32_t b = *bp;
-  return (a == b) ? 0 : (a < b) ? -1 : 1;
+void KeyAccumulator::AddKeysFromInterceptor(Handle<JSObject> array_like) {
+  // The accumulator might introduce duplicates for the current level,
+  // hence we set INCLUDE_CURRENT_LEVEL

[Igor Sheludko, 2015/10/22 21:42:57]

DCHECK_EQ(EXCLUDE_CURRENT_LEVEL, elementKeysAddCheckLimit_);
or maybe save the old value to return to.

+  elementKeysAddCheckLimit_ = INCLUDE_CURRENT_LEVEL;

[Igor Sheludko, 2015/10/22 21:42:57]

WDYT about adding all the elements without checking for duplicates in the last
level, then sort the last level and erase consecutive duplicates instead of
doing linear search each time?
  std::sort(last_level.begin(), last_level.end());
  last_level.erase(std::unique(last_level.begin(), last_level.end()),
last_level.end());
  and adjust the lengths according to the number of elements deleted.

[Camillo Bruni, 2015/10/26 09:53:48]

ah right, makes sense :)

+  AddKeys(array_like, CONVERT_TO_ARRAY_INDEX);
+  elementKeysAddCheckLimit_ = EXCLUDE_CURRENT_LEVEL;
 }
 
 
-}  // namespace
-
-
 void KeyAccumulator::SortCurrentElementsList() {
-  if (elements_.length() == 0) return;
-  List<uint32_t>* element_keys = elements_[elements_.length() - 1];
-  element_keys->Sort(&compareUInt32);
+  if (elements_.empty()) return;
+  std::vector<uint32_t>* element_keys = elements_.back();
+  std::sort(element_keys->begin(), element_keys->end());
 }
 
 
 void KeyAccumulator::NextPrototype() {
   // Store the protoLength on the first call of this method.
-  if (!elements_.is_empty()) {
-    levelLengths_.Add(levelLength_);
+  if (!elements_.empty()) {
+    levelLengths_.push_back(levelLength_);
   }
-  elements_.Add(new List<uint32_t>());
+  elements_.push_back(new std::vector<uint32_t>());
   levelLength_ = 0;
 }
 
@@ -7767,7 +7760,7 @@ MaybeHandle<FixedArray> JSReceiver::GetKeys(Handle<JSReceiver> object,
       Handle<JSObject> result;
       if (JSObject::GetKeysForIndexedInterceptor(current, object)
               .ToHandle(&result)) {
-        accumulator.AddKeys(result, CONVERT_TO_ARRAY_INDEX);
+        accumulator.AddKeysFromInterceptor(result);
       }
     }