Use worst-fit allocation in old space for prentured objects.

src/spaces.cc

Index: src/spaces.cc
diff --git a/src/spaces.cc b/src/spaces.cc
index e413bf1fffc59c17d5c775eda2a3de5fd931afbf..ba3582d4881fdabfc456810493169f7cca3d92ba 100644
--- a/src/spaces.cc
+++ b/src/spaces.cc
@@ -2216,36 +2216,8 @@ int FreeList::Free(Address start, int size_in_bytes) {
 }
 
 
-FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
+FreeListNode* FreeList::FindNodeInHugeList(int size_in_bytes, int* node_size) {
   FreeListNode* node = NULL;
-  Page* page = NULL;
-
-  if (size_in_bytes <= kSmallAllocationMax) {
-    node = small_list_.PickNodeFromList(node_size);
-    if (node != NULL) {
-      page = Page::FromAddress(node->address());
-      page->add_available_in_small_free_list(-(*node_size));
-      return node;
-    }
-  }
-
-  if (size_in_bytes <= kMediumAllocationMax) {
-    node = medium_list_.PickNodeFromList(node_size);
-    if (node != NULL) {
-      page = Page::FromAddress(node->address());
-      page->add_available_in_medium_free_list(-(*node_size));
-      return node;
-    }
-  }
-
-  if (size_in_bytes <= kLargeAllocationMax) {
-    node = large_list_.PickNodeFromList(node_size);
-    if (node != NULL) {
-      page = Page::FromAddress(node->address());
-      page->add_available_in_large_free_list(-(*node_size));
-      return node;
-    }
-  }
 
   int huge_list_available = huge_list_.available();
   for (FreeListNode** cur = huge_list_.GetTopAddress();
@@ -2254,10 +2226,7 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
     FreeListNode* cur_node = *cur;
     while (cur_node != NULL &&
            Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) {
-      int size = reinterpret_cast<FreeSpace*>(cur_node)->Size();
-      huge_list_available -= size;
-      page = Page::FromAddress(cur_node->address());
-      page->add_available_in_huge_free_list(-size);
+      huge_list_available -= reinterpret_cast<FreeSpace*>(cur_node)->Size();
       cur_node = cur_node->next();
     }
 
@@ -2276,8 +2245,6 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
       *cur = node->next();
       *node_size = size;
       huge_list_available -= size;
-      page = Page::FromAddress(node->address());
-      page->add_available_in_huge_free_list(-size);
       break;
     }
   }
@@ -2293,10 +2260,68 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
 }
 
 
+FreeListNode* FreeList::FindNodeForWorstFit(int size_in_bytes, int* node_size) {
+  FreeListNode* node = FindNodeInHugeList(size_in_bytes, node_size);
+  if (node != NULL) return node;

[Michael Starzinger, 2013/04/16 13:29:27]

Missing statistical book-keeping about available_in_huge_free_list here.

[Hannes Payer (out of office), 2013/04/16 13:41:04]

Done.

+
+  if (size_in_bytes <= kLargeAllocationMax) {
+    node = large_list_.PickNodeFromList(node_size);
+    if (node != NULL) return node;

[Michael Starzinger, 2013/04/16 13:29:27]

Missing statistical book-keeping about available_in_large_free_list here.

[Hannes Payer (out of office), 2013/04/16 13:41:04]

Done.

+  }
+
+  if (size_in_bytes <= kMediumAllocationMax) {
+    node = medium_list_.PickNodeFromList(node_size);
+    if (node != NULL) return node;

[Michael Starzinger, 2013/04/16 13:29:27]

Missing statistical book-keeping about available_in_medium_free_list here.

[Hannes Payer (out of office), 2013/04/16 13:41:04]

Done.

+  }
+
+  return node;
+}
+
+
+FreeListNode* FreeList::FindNodeForBestFit(int size_in_bytes, int* node_size) {
+  FreeListNode* node = NULL;
+  Page* page = NULL;

[Michael Starzinger, 2013/04/16 13:29:27]

nit: Move the declaration of "page" down into the conditionals where it's
actually used. Local code FTW.

[Hannes Payer (out of office), 2013/04/16 13:41:04]

Done.

+
+  if (size_in_bytes <= kSmallAllocationMax) {
+    node = small_list_.PickNodeFromList(node_size);
+    if (node != NULL) {
+      page = Page::FromAddress(node->address());
+      page->add_available_in_small_free_list(-(*node_size));
+      return node;
+    }
+  }
+
+  if (size_in_bytes <= kMediumAllocationMax) {
+    node = medium_list_.PickNodeFromList(node_size);
+    if (node != NULL) {
+      page = Page::FromAddress(node->address());
+      page->add_available_in_medium_free_list(-(*node_size));
+      return node;
+    }
+  }
+
+  if (size_in_bytes <= kLargeAllocationMax) {
+    node = large_list_.PickNodeFromList(node_size);
+    if (node != NULL) {
+      page = Page::FromAddress(node->address());
+      page->add_available_in_large_free_list(-(*node_size));
+      return node;
+    }
+  }
+
+  return FindNodeInHugeList(size_in_bytes, node_size);

[Michael Starzinger, 2013/04/16 13:29:27]

Missing statistical book-keeping about available_in_huge_free_list here.

[Hannes Payer (out of office), 2013/04/16 13:41:04]

Done.

+}
+
+
+template HeapObject* FreeList::Allocate<FreeList::BEST_FIT>(int size_in_bytes);
+
+template HeapObject* FreeList::Allocate<FreeList::WORST_FIT>(int size_in_bytes);
+

[Michael Starzinger, 2013/04/16 13:29:27]

nit: Add second empty newline.

[Hannes Payer (out of office), 2013/04/16 13:41:04]

Done.

 // Allocation on the old space free list.  If it succeeds then a new linear
 // allocation space has been set up with the top and limit of the space.  If
 // the allocation fails then NULL is returned, and the caller can perform a GC
 // or allocate a new page before retrying.
+template<FreeList::AllocationStrategy strategy>
 HeapObject* FreeList::Allocate(int size_in_bytes) {
   ASSERT(0 < size_in_bytes);
   ASSERT(size_in_bytes <= kMaxBlockSize);
@@ -2305,7 +2330,12 @@ HeapObject* FreeList::Allocate(int size_in_bytes) {
   ASSERT(owner_->limit() - owner_->top() < size_in_bytes);
 
   int new_node_size = 0;
-  FreeListNode* new_node = FindNodeFor(size_in_bytes, &new_node_size);
+  FreeListNode* new_node;
+  if (FreeList::BEST_FIT == strategy) {
+    new_node = FindNodeForBestFit(size_in_bytes, &new_node_size);
+  } else {
+    new_node = FindNodeForWorstFit(size_in_bytes, &new_node_size);
+  }
   if (new_node == NULL) return NULL;
 
 
@@ -2336,10 +2366,15 @@ HeapObject* FreeList::Allocate(int size_in_bytes) {
   const int kThreshold = IncrementalMarking::kAllocatedThreshold;
 
   // Memory in the linear allocation area is counted as allocated.  We may free
-  // a little of this again immediately - see below.
-  owner_->Allocate(new_node_size);
+  // a little of this again immediately - see below. We try to create large
+  // bump pointer ranges when we use worst-fit, therefore we do not give
+  // memory back to the free-list.
+  if (FreeList::BEST_FIT == strategy) {
+    owner_->Allocate(new_node_size);
+  }
 
-  if (bytes_left > kThreshold &&
+  if (FreeList::BEST_FIT == strategy &&
+      bytes_left > kThreshold &&
       owner_->heap()->incremental_marking()->IsMarkingIncomplete() &&
       FLAG_incremental_marking_steps) {
     int linear_size = owner_->RoundSizeDownToObjectAlignment(kThreshold);
@@ -2508,8 +2543,10 @@ bool PagedSpace::ReserveSpace(int size_in_bytes) {
   Address new_top = current_top + size_in_bytes;
   if (new_top <= allocation_info_.limit) return true;
 
-  HeapObject* new_area = free_list_.Allocate(size_in_bytes);
-  if (new_area == NULL) new_area = SlowAllocateRaw(size_in_bytes);
+  HeapObject* new_area = free_list_.Allocate<FreeList::BEST_FIT>(size_in_bytes);
+  if (new_area == NULL) {
+    new_area = SlowAllocateRaw<FreeList::BEST_FIT>(size_in_bytes);
+  }
   if (new_area == NULL) return false;
 
   int old_linear_size = static_cast<int>(limit() - top());
@@ -2614,6 +2651,15 @@ bool PagedSpace::EnsureSweeperProgress(intptr_t size_in_bytes) {
 }
 
 
+template HeapObject* PagedSpace::
+    SlowAllocateRaw<FreeList::BEST_FIT>(int size_in_bytes);
+
+
+template HeapObject* PagedSpace::
+    SlowAllocateRaw<FreeList::WORST_FIT>(int size_in_bytes);
+
+
+template<FreeList::AllocationStrategy strategy>
 HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
   // Allocation in this space has failed.
 
@@ -2626,7 +2672,7 @@ HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
     sweeping_complete = EnsureSweeperProgress(size_in_bytes);
 
     // Retry the free list allocation.
-    HeapObject* object = free_list_.Allocate(size_in_bytes);
+    HeapObject* object = free_list_.Allocate<strategy>(size_in_bytes);
     if (object != NULL) return object;
   }
 
@@ -2640,7 +2686,7 @@ HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
 
   // Try to expand the space and allocate in the new next page.
   if (Expand()) {
-    return free_list_.Allocate(size_in_bytes);
+     return free_list_.Allocate<strategy>(size_in_bytes);
   }
 
   // Last ditch, sweep all the remaining pages to try to find space.  This may
@@ -2649,7 +2695,7 @@ HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
     EnsureSweeperProgress(kMaxInt);
 
     // Retry the free list allocation.
-    HeapObject* object = free_list_.Allocate(size_in_bytes);
+    HeapObject* object = free_list_.Allocate<strategy>(size_in_bytes);
     if (object != NULL) return object;
   }