Do a backing store sparseness check on fast element delete.

src/objects.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 3013 matching lines @@
   Heap* heap = GetHeap();
   FixedArray* backing_store = FixedArray::cast(elements());
   if (backing_store->map() == heap->non_strict_arguments_elements_map()) {
     backing_store = FixedArray::cast(backing_store->get(1));
   } else {
     Object* writable;
     MaybeObject* maybe = EnsureWritableFastElements();
     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();
 }
 
 
 MaybeObject* JSObject::DeleteDictionaryElement(uint32_t index,
                                                DeleteMode mode) {
   Isolate* isolate = GetIsolate();
   Heap* heap = isolate->heap();
   FixedArray* backing_store = FixedArray::cast(elements());
@@ skipping 8587 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal