Age the number string cache so it does not keep strings

src/heap.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 812 matching lines @@
   // maps.
   isolate_->keyed_lookup_cache()->Clear();
   isolate_->context_slot_cache()->Clear();
   isolate_->descriptor_lookup_cache()->Clear();
   StringSplitCache::Clear(string_split_cache());
 
   isolate_->compilation_cache()->MarkCompactPrologue();
 
   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());
   }
 
   ClearNormalizedMapCaches();
 }
 
 
 Object* Heap::FindCodeObject(Address a) {
   return isolate()->inner_pointer_to_code_cache()->
@@ skipping 1608 matching lines @@
 
 void StringSplitCache::Clear(FixedArray* cache) {
   for (int i = 0; i < kStringSplitCacheSize; i++) {
     cache->set(i, Smi::FromInt(0));
   }
 }
 
 
 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());
+    }
   }
 }
 
 
 static inline int double_get_hash(double d) {
   DoubleRepresentation rep(d);
   return static_cast<int>(rep.bits) ^ static_cast<int>(rep.bits >> 32);
 }
 
 
-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();
 }
 
 
 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));
 }
 
 
 MaybeObject* Heap::NumberToString(Object* number,
                                   bool check_number_string_cache) {
   isolate_->counters()->number_to_string_runtime()->Increment();
   if (check_number_string_cache) {
     Object* cached = GetNumberStringCache(number);
     if (cached != undefined_value()) {
       return cached;
@@ skipping 3870 matching lines @@
   isolate_->heap()->store_buffer()->Compact();
   isolate_->heap()->store_buffer()->Filter(MemoryChunk::ABOUT_TO_BE_FREED);
   for (chunk = chunks_queued_for_free_; chunk != NULL; chunk = next) {
     next = chunk->next_chunk();
     isolate_->memory_allocator()->Free(chunk);
   }
   chunks_queued_for_free_ = NULL;
 }
 
 } }  // namespace v8::internal