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

src/spaces.h

 // 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 1309 matching lines @@
 // decreases to the non-capacity stats.
 class AllocationStats BASE_EMBEDDED {
  public:
   AllocationStats() { Clear(); }
 
   // Zero out all the allocation statistics (i.e., no capacity).
   void Clear() {
     capacity_ = 0;
     size_ = 0;
     waste_ = 0;
+    pretenure_ = 0;
   }
 
   void ClearSizeWaste() {
     size_ = capacity_;
     waste_ = 0;
+    pretenure_ = 0;
   }
 
   // Reset the allocation statistics (i.e., available = capacity with no
   // wasted or allocated bytes).
   void Reset() {
     size_ = 0;
     waste_ = 0;
+    pretenure_ = 0;
   }
 
   // Accessors for the allocation statistics.
   intptr_t Capacity() { return capacity_; }
   intptr_t Size() { return size_; }
   intptr_t Waste() { return waste_; }
+  intptr_t Pretenure() { return pretenure_; }
 
   // Grow the space by adding available bytes.  They are initially marked as
   // being in use (part of the size), but will normally be immediately freed,
   // putting them on the free list and removing them from size_.
   void ExpandSpace(int size_in_bytes) {
     capacity_ += size_in_bytes;
     size_ += size_in_bytes;
     ASSERT(size_ >= 0);
   }
 
   // Shrink the space by removing available bytes.  Since shrinking is done
   // during sweeping, bytes have been marked as being in use (part of the size)
   // and are hereby freed.
   void ShrinkSpace(int size_in_bytes) {
     capacity_ -= size_in_bytes;
     size_ -= size_in_bytes;
     ASSERT(size_ >= 0);
   }
 
   // Allocate from available bytes (available -> size).
   void AllocateBytes(intptr_t size_in_bytes) {
     size_ += size_in_bytes;
     ASSERT(size_ >= 0);
   }
 
+  void AllocatePretenureBytes(intptr_t size_in_bytes) {
+    pretenure_ += size_in_bytes;
+    ASSERT(pretenure_ >= 0);
+  }
+
   // Free allocated bytes, making them available (size -> available).
   void DeallocateBytes(intptr_t size_in_bytes) {
     size_ -= size_in_bytes;
     ASSERT(size_ >= 0);
   }
 
   // Waste free bytes (available -> waste).
   void WasteBytes(int size_in_bytes) {
     size_ -= size_in_bytes;
     waste_ += size_in_bytes;
     ASSERT(size_ >= 0);
   }
 
  private:
   intptr_t capacity_;
   intptr_t size_;
   intptr_t waste_;
+  // TODO(hpayer): We can remove the bookkeeping of pretenured objects when
+  // we provide pretenuring support for all kinds of objects.
+  intptr_t pretenure_;
 };
 
 
 // -----------------------------------------------------------------------------
 // Free lists for old object spaces
 //
 // Free-list nodes are free blocks in the heap.  They look like heap objects
 // (free-list node pointers have the heap object tag, and they have a map like
 // a heap object).  They have a size and a next pointer.  The next pointer is
 // the raw address of the next free list node (or NULL).
@@ skipping 119 matching lines @@
 
   // Clear the free list.
   void Reset();
 
   // Return the number of bytes available on the free list.
   intptr_t available() {
     return small_list_.available() + medium_list_.available() +
            large_list_.available() + huge_list_.available();
   }
 
+  enum AllocationStrategy {
+    BEST_FIT,
+    WORST_FIT
+  };
+
   // Place a node on the free list.  The block of size 'size_in_bytes'
   // starting at 'start' is placed on the free list.  The return value is the
   // number of bytes that have been lost due to internal fragmentation by
   // freeing the block.  Bookkeeping information will be written to the block,
   // i.e., its contents will be destroyed.  The start address should be word
   // aligned, and the size should be a non-zero multiple of the word size.
   int Free(Address start, int size_in_bytes);
 
   // Allocate a block of size 'size_in_bytes' from the free list.  The block
   // is unitialized.  A failure is returned if no block is available.  The
   // number of bytes lost to fragmentation is returned in the output parameter
   // 'wasted_bytes'.  The size should be a non-zero multiple of the word size.
+  template<AllocationStrategy strategy>
   MUST_USE_RESULT HeapObject* Allocate(int size_in_bytes);
 
 #ifdef DEBUG
   void Zap();
   intptr_t SumFreeLists();
   bool IsVeryLong();
 #endif
 
   // Used after booting the VM.
   void RepairLists(Heap* heap);
 
   intptr_t EvictFreeListItems(Page* p);
 
   FreeListCategory* small_list() { return &small_list_; }
   FreeListCategory* medium_list() { return &medium_list_; }
   FreeListCategory* large_list() { return &large_list_; }
   FreeListCategory* huge_list() { return &huge_list_; }
 
  private:
   // The size range of blocks, in bytes.
   static const int kMinBlockSize = 3 * kPointerSize;
   static const int kMaxBlockSize = Page::kMaxNonCodeHeapObjectSize;
 
-  FreeListNode* FindNodeFor(int size_in_bytes, int* node_size);
+  FreeListNode* FindNodeInHugeList(int size_in_bytes, int* node_size);
+
+  // Finds a node in the free-list using the best-fit allocation strategy.
+  FreeListNode* FindNodeForBestFit(int size_in_bytes, int* node_size);
+
+  // Finds a node in the free-list using the worst-fit allocation strategy
+  // and it ignores the smallest category.
+  FreeListNode* FindNodeForWorstFit(int size_in_bytes, int* node_size);
 
   PagedSpace* owner_;
   Heap* heap_;
 
   static const int kSmallListMin = 0x20 * kPointerSize;
   static const int kSmallListMax = 0xff * kPointerSize;
   static const int kMediumListMax = 0x7ff * kPointerSize;
   static const int kLargeListMax = 0x3fff * kPointerSize;
   static const int kSmallAllocationMax = kSmallListMin - kPointerSize;
   static const int kMediumAllocationMax = kSmallListMax;
@@ skipping 91 matching lines @@
   // The bytes in the linear allocation area are not included in this total
   // because updating the stats would slow down allocation.  New pages are
   // immediately added to the free list so they show up here.
   intptr_t Available() { return free_list_.available(); }
 
   // Allocated bytes in this space.  Garbage bytes that were not found due to
   // lazy sweeping are counted as being allocated!  The bytes in the current
   // linear allocation area (between top and limit) are also counted here.
   virtual intptr_t Size() { return accounting_stats_.Size(); }
 
+  intptr_t Pretenure() { return accounting_stats_.Pretenure(); }
+
   // As size, but the bytes in lazily swept pages are estimated and the bytes
   // in the current linear allocation area are not included.
   virtual intptr_t SizeOfObjects();
 
   // Wasted bytes in this space.  These are just the bytes that were thrown away
   // due to being too small to use for allocation.  They do not include the
   // free bytes that were not found at all due to lazy sweeping.
   virtual intptr_t Waste() { return accounting_stats_.Waste(); }
 
   // Returns the allocation pointer in this space.
   Address top() { return allocation_info_.top; }
   Address limit() { return allocation_info_.limit; }
 
   // The allocation top and limit addresses.
   Address* allocation_top_address() { return &allocation_info_.top; }
   Address* allocation_limit_address() { return &allocation_info_.limit; }
 
   // Allocate the requested number of bytes in the space if possible, return a
   // failure object if not.
+  template<FreeList::AllocationStrategy strategy>
   MUST_USE_RESULT inline MaybeObject* AllocateRaw(int size_in_bytes);
 
   virtual bool ReserveSpace(int bytes);
 
   // Give a block of memory to the space's free list.  It might be added to
   // the free list or accounted as waste.
   // If add_to_freelist is false then just accounting stats are updated and
   // no attempt to add area to free list is made.
   int Free(Address start, int size_in_bytes) {
     int wasted = free_list_.Free(start, size_in_bytes);
@@ skipping 11 matching lines @@
            Page::FromAddress(top) == Page::FromAddress(limit - 1));
     MemoryChunk::UpdateHighWaterMark(allocation_info_.top);
     allocation_info_.top = top;
     allocation_info_.limit = limit;
   }
 
   void Allocate(int bytes) {
     accounting_stats_.AllocateBytes(bytes);
   }
 
+  void AllocatePretenure(int bytes) {
+    accounting_stats_.AllocatePretenureBytes(bytes);
+  }
+
   void IncreaseCapacity(int size) {
     accounting_stats_.ExpandSpace(size);
   }
 
   // Releases an unused page and shrinks the space.
   void ReleasePage(Page* page, bool unlink);
 
   // The dummy page that anchors the linked list of pages.
   Page* anchor() { return &anchor_; }
 
@@ skipping 126 matching lines @@
   // Expands the space by allocating a fixed number of pages. Returns false if
   // it cannot allocate requested number of pages from OS, or if the hard heap
   // size limit has been hit.
   bool Expand();
 
   // Generic fast case allocation function that tries linear allocation at the
   // address denoted by top in allocation_info_.
   inline HeapObject* AllocateLinearly(int size_in_bytes);
 
   // Slow path of AllocateRaw.  This function is space-dependent.
-  MUST_USE_RESULT virtual HeapObject* SlowAllocateRaw(int size_in_bytes);
+  template<FreeList::AllocationStrategy strategy>
+  MUST_USE_RESULT HeapObject* SlowAllocateRaw(int size_in_bytes);
 
   friend class PageIterator;
   friend class SweeperThread;
 };
 
 
 class NumberAndSizeInfo BASE_EMBEDDED {
  public:
   NumberAndSizeInfo() : number_(0), bytes_(0) {}
 
@@ skipping 962 matching lines @@
   }
   // Must be small, since an iteration is used for lookup.
   static const int kMaxComments = 64;
 };
 #endif
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_SPACES_H_