Age the number string cache so it does not keep strings

src/heap.cc

Index: src/heap.cc
===================================================================
--- src/heap.cc	(revision 9686)
+++ src/heap.cc	(working copy)
@@ -831,7 +831,7 @@
   CompletelyClearInstanceofCache();
 
   // TODO(1605) select heuristic for flushing NumberString cache with

[Vyacheslav Egorov (Chromium), 2011/10/18 15:30:39]

remove todo?

-  // FlushNumberStringCache
+  AgeNumberStringCache();
   if (FLAG_cleanup_code_caches_at_gc) {
     polymorphic_code_cache()->set_cache(undefined_value());
   }
@@ -2460,23 +2460,61 @@
 
 MaybeObject* Heap::InitializeNumberStringCache() {
   // Compute the size of the number string cache based on the max heap size.
-  // max_semispace_size_ == 512 KB => number_string_cache_size = 32.
-  // max_semispace_size_ ==   8 MB => number_string_cache_size = 16KB.
+  // max_semispace_size_ == 512kbyte => number_string_cache_size = 1kbyte.
+  // max_semispace_size_ ==   8Mbyte => number_string_cache_size = 16kbyte.
   int number_string_cache_size = max_semispace_size_ / 512;
   number_string_cache_size = Max(32, Min(16*KB, number_string_cache_size));
+  number_string_cache_size = RoundUpToPowerOf2(number_string_cache_size);
   Object* obj;
   MaybeObject* maybe_obj =
-      AllocateFixedArray(number_string_cache_size * 2, TENURED);
-  if (maybe_obj->ToObject(&obj)) set_number_string_cache(FixedArray::cast(obj));
+      AllocateFixedArray(number_string_cache_size * kNSCSlotsPerEntry, TENURED);
+  if (maybe_obj->ToObject(&obj)) {
+    set_number_string_cache(FixedArray::cast(obj));
+    FixedArray* array = FixedArray::cast(obj);
+    for (int i = 0;
+         i < number_string_cache_size * kNSCSlotsPerEntry;
+         i += kNSCSlotsPerEntry) {
+      array->set_undefined(this, i + kNSCNumberOffset);
+      array->set_undefined(this, i + kNSCStringOffset);
+      array->set(i + kNSCAgeOffset, Smi::FromInt(-1));
+    }
+  }
   return maybe_obj;
 }
 
 
-void Heap::FlushNumberStringCache() {
-  // Flush the number to string cache.
+void Heap::AgeNumberStringCache() {
+  // Flush the number to string cache.  The cache is laidout as a number of
+  // cache entries.  Each entry has first the number, then the string, then an
+  // age mark.  The age mark is -1 for an unused entry or n for a entry that
+  // hasn't been used for the last n GC intervals.
   int len = number_string_cache()->length();
-  for (int i = 0; i < len; i++) {
-    number_string_cache()->set_undefined(this, i);
+  ASSERT(len % kNSCSlotsPerEntry == 0);
+  STATIC_ASSERT(kNSCSlotsPerEntry == 3);  // This is needed for the next assert.
+  ASSERT(IsPowerOf2(len & (len >> 1)));  // Two thirds of len is a power of 2.
+  for (int i = 0; i < len; i += kNSCSlotsPerEntry) {
+    int recently_used =
+        Smi::cast(number_string_cache()->get(i + kNSCAgeOffset))->value();
+    if (recently_used >= kNSCMinAge) {
+      recently_used++;
+      if (recently_used > kNSCMaxAge) {
+        // Not used for too long.  Remove from cache.
+        number_string_cache()->set(i + kNSCAgeOffset, Smi::FromInt(-1));
+        number_string_cache()->set_undefined(this + kNSCNumberOffset, i);
+        number_string_cache()->set_undefined(this, i + kNSCStringOffset);
+      } else {
+        // Age the entry.
+        number_string_cache()->set(i + kNSCAgeOffset,
+                                   Smi::FromInt(recently_used));
+        ASSERT(number_string_cache()->get(i + kNSCNumberOffset)->IsNumber());
+        ASSERT(number_string_cache()->get(i + kNSCStringOffset)->IsString());
+      }
+    } else {
+      // Unused slot.
+      ASSERT(recently_used == kNSCUnusedAge);
+      ASSERT(number_string_cache()->get(i + kNSCNumberOffset)->IsUndefined());
+      ASSERT(number_string_cache()->get(i + kNSCStringOffset)->IsUndefined());
+    }
   }
 }
 
@@ -2487,26 +2525,29 @@
 }
 
 
-static inline int smi_get_hash(Smi* smi) {
-  return smi->value();
-}
-
-
 Object* Heap::GetNumberStringCache(Object* number) {
   int hash;
-  int mask = (number_string_cache()->length() >> 1) - 1;
+  int len = number_string_cache()->length();
+  ASSERT(len % kNSCSlotsPerEntry == 0);
+  STATIC_ASSERT(kNSCSlotsPerEntry == 3);
+  len &= len >> 1;  // Divide len by 3.
+  ASSERT(IsPowerOf2(len));
+  int mask = len - 1;
   if (number->IsSmi()) {
-    hash = smi_get_hash(Smi::cast(number)) & mask;
+    hash = (Smi::cast(number)->value() & mask);
   } else {
     hash = double_get_hash(number->Number()) & mask;
   }
-  Object* key = number_string_cache()->get(hash * 2);
-  if (key == number) {
-    return String::cast(number_string_cache()->get(hash * 2 + 1));
-  } else if (key->IsHeapNumber() &&
-             number->IsHeapNumber() &&
-             key->Number() == number->Number()) {
-    return String::cast(number_string_cache()->get(hash * 2 + 1));
+  hash *= kNSCSlotsPerEntry;
+  Object* key = number_string_cache()->get(hash + kNSCNumberOffset);
+  if (key == number ||
+      (key->IsHeapNumber() &&
+       number->IsHeapNumber() &&
+       key->Number() == number->Number())) {
+    // Reset age field.
+    number_string_cache()->set(hash + kNSCAgeOffset, Smi::FromInt(kNSCMinAge));
+    // Cache hit.
+    return String::cast(number_string_cache()->get(hash + kNSCStringOffset));
   }
   return undefined_value();
 }
@@ -2514,15 +2555,22 @@
 
 void Heap::SetNumberStringCache(Object* number, String* string) {
   int hash;
-  int mask = (number_string_cache()->length() >> 1) - 1;
+  int len = number_string_cache()->length();
+  ASSERT(len % kNSCSlotsPerEntry == 0);
+  STATIC_ASSERT(kNSCSlotsPerEntry == 3);
+  len &= len >> 1;  // Divide len by 3.
+  ASSERT(IsPowerOf2(len));
+  int mask = len - 1;
   if (number->IsSmi()) {
-    hash = smi_get_hash(Smi::cast(number)) & mask;
-    number_string_cache()->set(hash * 2, Smi::cast(number));
+    hash = (Smi::cast(number)->value() & mask) * kNSCSlotsPerEntry;
+    number_string_cache()->set(hash + kNSCNumberOffset, Smi::cast(number));
   } else {
-    hash = double_get_hash(number->Number()) & mask;
-    number_string_cache()->set(hash * 2, number);
+    hash = (double_get_hash(number->Number()) & mask) * kNSCSlotsPerEntry;
+    number_string_cache()->set(hash + kNSCNumberOffset, number);
   }
-  number_string_cache()->set(hash * 2 + 1, string);
+  number_string_cache()->set(hash + kNSCStringOffset, string);
+  // Reset age field.
+  number_string_cache()->set(hash + kNSCAgeOffset, Smi::FromInt(kNSCMinAge));
 }