Implement a hash based look-up to speed up containing address check in large

src/spaces.cc

Index: src/spaces.cc
===================================================================
--- src/spaces.cc	(revision 10961)
+++ src/spaces.cc	(working copy)
@@ -2520,6 +2520,9 @@
 
 // -----------------------------------------------------------------------------
 // LargeObjectSpace
+static bool match(void* key1, void* key2) {

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

Please give this function a more meaningful name, e.g.
ComparePointers/SamePointers/etc

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

+    return key1 == key2;
+}
 

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

one additional empty line

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

 LargeObjectSpace::LargeObjectSpace(Heap* heap,
                                    intptr_t max_capacity,
@@ -2529,7 +2532,8 @@
       first_page_(NULL),
       size_(0),
       page_count_(0),
-      objects_size_(0) {}
+      objects_size_(0),
+      map_(match, 1024) {}
 
 
 bool LargeObjectSpace::SetUp() {
@@ -2537,6 +2541,7 @@
   size_ = 0;
   page_count_ = 0;
   objects_size_ = 0;
+  map_.Clear();
   return true;
 }
 
@@ -2580,6 +2585,17 @@
   page->set_next_page(first_page_);
   first_page_ = page;
 
+  // map following entries to this page object, in which keys are

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

comments should start with a capital letter and end with a dot.

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

I would rephrase this comment, for example:

// Register all MemoryChunk::kAlignment-aligned chunks covered by this large
page in the chunk map.

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

+  // MemoryChunk::kAlignment-aligned addresses in this page, and
+  // hash is key/MemoryChunk::kAlignment to reduce hash conflict
+  uint32_t key = reinterpret_cast<uint32_t>(page);
+  uint32_t limit = key + page->size();
+  for (uint32_t hash = key/MemoryChunk::kAlignment;
+      key < limit;
+      key += MemoryChunk::kAlignment, hash++) {

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

I think you can just unify hash and key (make key == hash) because key is
aligned and it's 20 less significant bits are always zeros. This will make this
loop cleaner.

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

+      (map_.Lookup(reinterpret_cast<void*>(key), hash, true))->value = page;

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

I would prefer this is done in two lines instead of a single line.

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

+  }
+
   HeapObject* object = page->GetObject();
 
 #ifdef DEBUG
@@ -2596,33 +2612,39 @@
 
 // GC support
 MaybeObject* LargeObjectSpace::FindObject(Address a) {
-  for (LargePage* page = first_page_;
-       page != NULL;
-       page = page->next_page()) {
+  uint32_t key = reinterpret_cast<uint32_t>(a);
+  key -= key % MemoryChunk::kAlignment;
+  uint32_t hash = key / MemoryChunk::kAlignment;
+  HashMap::Entry* e = map_.Lookup(reinterpret_cast<void*>(key), hash, false);
+  if ( e != NULL ) {
+    ASSERT(e->value != NULL);
+    LargePage* page = reinterpret_cast<LargePage*>(e->value);
+    ASSERT(page->is_valid());
     Address page_address = page->address();
-    if (page_address <= a && a < page_address + page->size()) {
+    if ( page_address <= a && a < page_address + page->size() ) {

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

accidental edit? please revert.

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

       return page->GetObject();
     }
   }
   return Failure::Exception();
 }
 
-
 LargePage* LargeObjectSpace::FindPageContainingPc(Address pc) {
-  // TODO(853): Change this implementation to only find executable
-  // chunks and use some kind of hash-based approach to speed it up.
-  for (LargePage* chunk = first_page_;
-       chunk != NULL;
-       chunk = chunk->next_page()) {
-    Address chunk_address = chunk->address();
-    if (chunk_address <= pc && pc < chunk_address + chunk->size()) {
-      return chunk;
+  uint32_t key = reinterpret_cast<uint32_t>(pc);
+  key -= key % MemoryChunk::kAlignment;
+  uint32_t hash = key / MemoryChunk::kAlignment;
+  HashMap::Entry* e = map_.Lookup(reinterpret_cast<void*>(key), hash, false);
+  if ( e != NULL ) {
+    ASSERT(e->value != NULL);
+    LargePage* page = reinterpret_cast<LargePage*>(e->value);
+    ASSERT(page->is_valid());
+    Address page_address = page->address();
+    if ( page_address <= pc && pc < page_address + page->size() ) {
+      return page;

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

This code is duplicated in two places. Please move everything to a single helper
function. 

[kewpie.w.zp, 2012/03/12 02:00:40]

Accepted, will reduce FindObject(a) size by calling this function instead to
remove duplicated code

     }
   }
   return NULL;
 }
 
-

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

accidental edit? please revert.

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

 void LargeObjectSpace::FreeUnmarkedObjects() {
   LargePage* previous = NULL;
   LargePage* current = first_page_;
@@ -2654,6 +2676,15 @@
       objects_size_ -= object->Size();
       page_count_--;
 
+      // remove entries belonging to this page

[Vyacheslav Egorov (Chromium), 2012/03/08 11:41:23]

comments should start with a capital letter and end with a dot.

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

+      uint32_t key = reinterpret_cast<uint32_t>(page);
+      uint32_t limit = key + page->size();
+      for (uint32_t hash = key/MemoryChunk::kAlignment;
+          key < limit;
+          key += MemoryChunk::kAlignment, hash++) {
+          map_.Remove(reinterpret_cast<void*>(key), hash);
+      }
+
       if (is_pointer_object) {
         heap()->QueueMemoryChunkForFree(page);
       } else {