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

src/spaces.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 2198 matching lines @@
   } else {
     huge_list_.Free(node, size_in_bytes);
     page->add_available_in_huge_free_list(size_in_bytes);
   }
 
   ASSERT(IsVeryLong() || available() == SumFreeLists());
   return 0;
 }
 
 
-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();
        *cur != NULL;
        cur = (*cur)->next_address()) {
     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();
     }
 
     *cur = cur_node;
     if (cur_node == NULL) {
       huge_list_.set_end(NULL);
       break;
     }
 
     ASSERT((*cur)->map() == heap_->raw_unchecked_free_space_map());
     FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(*cur);
     int size = cur_as_free_space->Size();
     if (size >= size_in_bytes) {
       // Large enough node found.  Unlink it from the list.
       node = *cur;
       *cur = node->next();
       *node_size = size;
       huge_list_available -= size;
-      page = Page::FromAddress(node->address());
-      page->add_available_in_huge_free_list(-size);
       break;
     }
   }
 
   if (huge_list_.top() == NULL) {
     huge_list_.set_end(NULL);
   }
 
   huge_list_.set_available(huge_list_available);
   ASSERT(IsVeryLong() || available() == SumFreeLists());
 
   return node;
 }
 
 
+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);
   ASSERT(IsAligned(size_in_bytes, kPointerSize));
   // Don't free list allocate if there is linear space available.
   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;
 
 
   int bytes_left = new_node_size - size_in_bytes;
   ASSERT(bytes_left >= 0);
 
   int old_linear_size = static_cast<int>(owner_->limit() - owner_->top());
   // Mark the old linear allocation area with a free space map so it can be
   // skipped when scanning the heap.  This also puts it back in the free list
   // if it is big enough.
@@ skipping 10 matching lines @@
 #endif
 
   // The old-space-step might have finished sweeping and restarted marking.
   // Verify that it did not turn the page of the new node into an evacuation
   // candidate.
   ASSERT(!MarkCompactCollector::IsOnEvacuationCandidate(new_node));
 
   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);
     // We don't want to give too large linear areas to the allocator while
     // incremental marking is going on, because we won't check again whether
     // we want to do another increment until the linear area is used up.
     owner_->Free(new_node->address() + size_in_bytes + linear_size,
                  new_node_size - size_in_bytes - linear_size);
     owner_->SetTop(new_node->address() + size_in_bytes,
                    new_node->address() + size_in_bytes + linear_size);
@@ skipping 148 matching lines @@
 }
 
 
 bool PagedSpace::ReserveSpace(int size_in_bytes) {
   ASSERT(size_in_bytes <= AreaSize());
   ASSERT(size_in_bytes == RoundSizeDownToObjectAlignment(size_in_bytes));
   Address current_top = allocation_info_.top;
   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());
   // Mark the old linear allocation area with a free space so it can be
   // skipped when scanning the heap.  This also puts it back in the free list
   // if it is big enough.
   Free(top(), old_linear_size);
 
   SetTop(new_area->address(), new_area->address() + size_in_bytes);
   return true;
@@ skipping 84 matching lines @@
       }
       return false;
     }
     return true;
   } else {
     return AdvanceSweeper(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.
 
   // If there are unswept pages advance lazy sweeper a bounded number of times
   // until we find a size_in_bytes contiguous piece of memory
   const int kMaxSweepingTries = 5;
   bool sweeping_complete = false;
 
   for (int i = 0; i < kMaxSweepingTries && !sweeping_complete; i++) {
     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;
   }
 
   // Free list allocation failed and there is no next page.  Fail if we have
   // hit the old generation size limit that should cause a garbage
   // collection.
   if (!heap()->always_allocate() &&
       heap()->OldGenerationAllocationLimitReached()) {
     return NULL;
   }
 
   // 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
   // cause a pause.
   if (!IsLazySweepingComplete()) {
     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;
   }
 
   // Finally, fail.
   return NULL;
 }
 
 
 #ifdef DEBUG
 void PagedSpace::ReportCodeStatistics() {
@@ skipping 513 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal