Do a backing store sparseness check on fast element delete.

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 74c1f42beb0c1e44dabe12c7217998685abc6e65..d0f7c099ad3413c5ed6ef1603bae212bb4f7a50e 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -3031,11 +3031,31 @@ MaybeObject* JSObject::DeleteFastElement(uint32_t index) {
     if (!maybe->ToObject(&writable)) return maybe;
     backing_store = FixedArray::cast(writable);
   }
-  int length = IsJSArray()
+  uint32_t length = static_cast<uint32_t>(
+      IsJSArray()
       ? Smi::cast(JSArray::cast(this)->length())->value()
-      : backing_store->length();
-  if (index < static_cast<uint32_t>(length)) {
+      : backing_store->length());
+  if (index < length) {
     backing_store->set_the_hole(index);
+    // If an old space backing store is larger than a certain size and
+    // has too few used values, normalize it.
+    // To avoid doing the check on every delete we require at least
+    // one adjacent hole to the value being deleted.
+    Object* hole = heap->the_hole_value();
+    const int kMinLengthForSparsenessCheck = 64;
+    if (backing_store->length() >= kMinLengthForSparsenessCheck &&
+        !heap->InNewSpace(backing_store) &&
+        ((index > 0 && backing_store->get(index - 1) == hole) ||
+         (index + 1 < length && backing_store->get(index + 1) == hole))) {
+      int num_used = 0;
+      for (int i = 0; i < backing_store->length(); ++i) {
+        if (backing_store->get(i) != hole) ++num_used;

[Vyacheslav Egorov (Chromium), 2011/07/01 12:25:58]

You can have an early exit from the loop if num_used * 4 becomes bigger then
length.

This will optimize some common cases.

[Vitaly Repeshko, 2011/07/01 13:05:02]

Good idea. Done.

+      }
+      if (4 * num_used <= backing_store->length()) {
+        MaybeObject* result = NormalizeElements();
+        if (result->IsFailure()) return result;
+      }
+    }
   }
   return heap->true_value();
 }