Oilpan: attempt first-fit freelist allocation for backing heaps.

Source/platform/heap/Heap.cpp

 /*
  * Copyright (C) 2013 Google Inc. 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
@@ skipping 660 matching lines @@
 void ThreadHeap<Header>::updateRemainingAllocationSize()
 {
     if (m_lastRemainingAllocationSize > remainingAllocationSize()) {
         Heap::increaseAllocatedObjectSize(m_lastRemainingAllocationSize - remainingAllocationSize());
         m_lastRemainingAllocationSize = remainingAllocationSize();
     }
     ASSERT(m_lastRemainingAllocationSize == remainingAllocationSize());
 }
 
 template<typename Header>
-Address ThreadHeap<Header>::outOfLineAllocate(size_t payloadSize, size_t allocationSize, const GCInfo* gcInfo)
+Address ThreadHeap<Header>::outOfLineAllocate(size_t allocationSize, const GCInfo* gcInfo)
 {
     ASSERT(allocationSize > remainingAllocationSize());
     if (allocationSize > blinkPageSize / 2)
         return allocateLargeObject(allocationSize, gcInfo);
 
     updateRemainingAllocationSize();
     threadState()->scheduleGCOrForceConservativeGCIfNeeded();
 
+    ASSERT(allocationSize >= allocationGranularity);
+    Address result = allocateFromFreeList(allocationSize, gcInfo);
+    if (result)
+        return result;
     setAllocationPoint(nullptr, 0);
-    ASSERT(allocationSize >= allocationGranularity);
-    if (allocateFromFreeList(allocationSize))
-        return allocate(payloadSize, gcInfo);
-    if (coalesce(allocationSize) && allocateFromFreeList(allocationSize))
-        return allocate(payloadSize, gcInfo);
+    if (coalesce(allocationSize)) {
+        result = allocateFromFreeList(allocationSize, gcInfo);
+        if (result)
+            return result;
+    }
 
     addPageToHeap(gcInfo);
-    bool success = allocateFromFreeList(allocationSize);
-    RELEASE_ASSERT(success);
-    return allocate(payloadSize, gcInfo);
+    result = allocateFromFreeList(allocationSize, gcInfo);
+    RELEASE_ASSERT(result);
+    return result;
+}
+
+static bool shouldUseFirstFitForHeap(int heapIndex)

[haraken, 2014/12/16 02:26:33]

Isn't this "best fit", not "first fit"?

[sof, 2014/12/16 07:31:54]

Not as I know the terms -- best fit would search that bin for the optimal block.

[haraken, 2014/12/16 08:26:14]

(I'm not intending to bike-shed terms but) as far as I understand, what we are
doing in allocateFromFreeList is a choice between approximately-best-fit or
approximately-worst-fit. First-fit sounds like a scheme that allocates on a slot
that is found first by accident (without maintaining a list of power-of-2 free
slots).

[sof, 2014/12/16 08:32:15]

It performs first fit within segregated bins.

[haraken, 2014/12/16 08:51:19]

Then our worst-fit is also working as a first-fit within segregated bins, so
there is no difference... The difference is from which segregated bin we pick up
a free list. Best-fit segregated bin or worst-fit segregated bin. That's why I
thought best-fit or worst-fit reflects the scheme.

[sof, 2014/12/16 08:54:22]

It's performing first-fit within the worst bin in the normal case. I haven't
used the worst-fit term, i think.

[haraken, 2014/12/16 09:06:37]

That's why I think shouldUseFirstFit doesn't capture what it is doing. In your
definition, we're doing first-fit in both cases. So I suggested to use
best-fit/worst-fit as terms to distinguish allocation schemes between collection
backing heaps and other heaps.

That said, I don't really care about it since you have a very good comment here.

+{
+    // For an allocation of size N, should a heap perform a first-fit
+    // matching within the sized bin that N belongs to?
+    //
+    // Theory: quickly reusing a previously freed backing store block stands
+    // a chance of maintaining cached presence of that block (maintains
+    // "locality".) This is preferable to starting to bump allocate from a
+    // new and bigger block, which is what allocateFromFreeList() does by
+    // default. Hence, the backing store heaps are considered for binned
+    // first-fit matching.

[haraken, 2014/12/16 02:26:33]

Shall we also mention that this optimization makes sense only for backing
storages where coalescing is supported?

I think coalescing is a key. If coalescing is not supported, we cannot get any
freed block until a GC is triggered and thus this optimization wouldn't be
helpful.

[sof, 2014/12/16 07:31:54]

Coalescing is not the key -- as I pointed out yesterday, it doesn't make a
difference.

[haraken, 2014/12/16 08:26:14]

Hmm. Then probably the situation is like this?

Fact 1: Worst-fit is better than best-fit in terms of allocation overhead.

Fact 2: Best-fit is better than worst-fit in terms of memory reuse.

Therefore, a smart allocation scheme is to allocate large objects in best-fit
and small objects in worst-fit.

If this is the case, what we should do is to determine best-fit or worst-fit
depending on allocation size, not depending on whether it is a collection
backing heap or not. (I guess there are a lot of large allocations in collection
backing heaps but there are few large allocations in normal heaps. That's why
this optimization makes sense only for collection backing heaps in most cases.)
Just 2 cents.

Either way, I'm fine with landing this CL and investigate a better scheme later.

[sof, 2014/12/16 08:36:18]

As I said earlier, doing a decision based on size doesn't work out. (I'm very
sorry, but it's frustrating and off-putting when followups aren't listened to.)

[haraken, 2014/12/16 08:51:19]

I'm sorry about it... Then the situation is that we don't know why this
allocation scheme is working well.

+    //
+    // This appears to hold true through performance expermentation; at
+    // least no signficant performance regressions have been observed.
+    //
+    // This theory of improved performance does not hold true for other
+    // heap types. We are currently seeking an understanding of why;

[haraken, 2014/12/16 02:26:33]

I guess the reason this optimization doesn't help normal heaps is that normal
heaps don't support coalescing.

[sof, 2014/12/16 07:31:54]

They do coalesce when sweeping though.

+    // larger amounts of small block fragmentation might be one reason
+    // for it. TBC.
+    //
+    if (heapIndex >= VectorBackingHeap && heapIndex <= HashTableBackingHeap)

[haraken, 2014/12/16 02:26:33]

For safety, I'd prefer:

  heapIndex == VectorBackingHeap || heapIndex == HashTableBackingHeap

to exactly match what we want to match.

[sof, 2014/12/16 07:31:54]

And also the inline heap case -- this seems verbose (and a trifling detail.)

+        return true;
+    if (heapIndex >= VectorBackingHeapNonFinalized && heapIndex <= HashTableBackingHeapNonFinalized)

[haraken, 2014/12/16 02:26:33]

Ditto.

+        return true;
+
+    return false;
 }
 
 template<typename Header>
-FreeListEntry* FreeList<Header>::takeEntry(size_t allocationSize)
+Address ThreadHeap<Header>::allocateFromFreeList(size_t allocationSize, const GCInfo* gcInfo)
 {
-    size_t bucketSize = 1 << m_biggestFreeListIndex;
-    int i = m_biggestFreeListIndex;
-    for (; i > 0; i--, bucketSize >>= 1) {
-        if (bucketSize < allocationSize) {
-            // A FreeListEntry for bucketSize might be larger than allocationSize.
-            // FIXME: We check only the first FreeListEntry because searching
-            // the entire list is costly.
-            if (!m_freeLists[i] || m_freeLists[i]->size() < allocationSize)
+    // The freelist allocation scheme is currently as follows:
+    //
+    // - If the heap is of an appropriate type, try to pick the first
+    //   entry from the sized bin corresponding to |allocationSize|.
+    //   [See shouldUseFirstFitForHeap() comment for motivation on why.]
+    //
+    // - If that didn't satisfy the allocation, try reusing a block
+    //   from the largest bin. The underlying reasoning being that
+    //   we want to amortize this slow allocation call by carving
+    //   off as a large a free block as possible in one go; a block
+    //   that will service this block and let following allocations
+    //   be serviced quickly by bump allocation.
+    //
+    // - Fail; allocation cannot be serviced by the freelist.
+    //   The allocator will handle that failure by requesting more
+    //   heap pages from the OS and re-initiate the allocation request.
+    //
+    int bucket = FreeList<Header>::bucketIndexForSize(allocationSize) + 1;

[haraken, 2014/12/16 02:26:33]

bucket => index

[sof, 2014/12/16 07:31:54]

No, sorry - this is a bucket, not an index. Or do you want bucketIndex?

+    if (bucket <= m_freeList.m_biggestFreeListIndex && shouldUseFirstFitForHeap(m_index)) {
+        if (FreeListEntry* entry = m_freeList.m_freeLists[bucket]) {

[haraken, 2014/12/16 02:26:33]

Don't we want to look up the entry in m_freeLists[x] where x is larger than
bucket? I mean:

for (int index = bucket; index < blinkPageSizeLog2; ++index) {
  if (FreeListEntry* entry = m_freeList.m_freeLists[index]) {
    entry->unlink(&m_freeList.m_freeLists[index]);
    ...;
    break;
  }
}

[sof, 2014/12/16 07:31:54]

That's been checked as regressing performance earlier.

+            entry->unlink(&m_freeList.m_freeLists[bucket]);
+            if (!m_freeList.m_freeLists[bucket] && bucket == m_freeList.m_biggestFreeListIndex) {
+                // Recalculate the biggest index of non-empty buckets.
+                int maxIndex = m_freeList.m_biggestFreeListIndex - 1;
+                for (; maxIndex >= 0 && !m_freeList.m_freeLists[maxIndex]; maxIndex--) { }
+                m_freeList.m_biggestFreeListIndex = maxIndex < 0 ? 0 : maxIndex;

[haraken, 2014/12/16 02:26:33]

The calculation of m_biggestFreeListIndex is getting complicated. We might want
to have an ASSERT somewhere to verify that m_biggestFreeListIndex is actually
pointing to the max index.

+            }
+            // Allocate into the freelist block without disturbing the current allocation area.
+            ASSERT(entry->size() >= allocationSize);
+            if (entry->size() > allocationSize)
+                addToFreeList(entry->address() + allocationSize, entry->size() - allocationSize);
+            Heap::increaseAllocatedObjectSize(allocationSize);
+            return allocateAtAddress(entry->address(), allocationSize, gcInfo);
+        }
+        // Failed to find a first-fit freelist entry; fall into the standard case of
+        // chopping off the largest free block and bump allocate from it.
+    }
+    size_t bucketSize = 1 << m_freeList.m_biggestFreeListIndex;
+    int index = m_freeList.m_biggestFreeListIndex;
+    for (; index > 0; index--, bucketSize >>= 1) {

[haraken, 2014/12/16 02:26:33]

--index

+        FreeListEntry* entry = m_freeList.m_freeLists[index];
+        if (allocationSize > bucketSize) {
+            // Final bucket candidate; check initial entry if it is able
+            // to service this allocation. Do not perform a linear scan,
+            // as it is considered too costly.
+            if (!entry || entry->size() < allocationSize)
                 break;
         }
-        if (FreeListEntry* entry = m_freeLists[i]) {
-            m_biggestFreeListIndex = i;
-            entry->unlink(&m_freeLists[i]);
-            return entry;
+        if (entry) {
+            entry->unlink(&m_freeList.m_freeLists[index]);
+            setAllocationPoint(entry->address(), entry->size());
+            ASSERT(hasCurrentAllocationArea());
+            ASSERT(remainingAllocationSize() >= allocationSize);
+            m_freeList.m_biggestFreeListIndex = index;
+            return allocateSize(allocationSize, gcInfo);
         }
     }
-    m_biggestFreeListIndex = i;
+    m_freeList.m_biggestFreeListIndex = index;
     return nullptr;
 }
 
-template<typename Header>
-bool ThreadHeap<Header>::allocateFromFreeList(size_t allocationSize)
-{
-    ASSERT(!hasCurrentAllocationArea());
-    if (FreeListEntry* entry = m_freeList.takeEntry(allocationSize)) {
-        setAllocationPoint(entry->address(), entry->size());
-        ASSERT(hasCurrentAllocationArea());
-        ASSERT(remainingAllocationSize() >= allocationSize);
-        return true;
-    }
-    return false;
-}
-
 #if ENABLE(ASSERT)
 template<typename Header>
 static bool isLargeObjectAligned(LargeObject<Header>* largeObject, Address address)
 {
     // Check that a large object is blinkPageSize aligned (modulo the osPageSize
     // for the guard page).
     return reinterpret_cast<Address>(largeObject) - WTF::kSystemPageSize == roundToBlinkPageStart(reinterpret_cast<Address>(largeObject));
 }
 #endif
 
@@ skipping 2193 matching lines @@
 bool Heap::s_shutdownCalled = false;
 bool Heap::s_lastGCWasConservative = false;
 FreePagePool* Heap::s_freePagePool;
 OrphanedPagePool* Heap::s_orphanedPagePool;
 Heap::RegionTree* Heap::s_regionTree = nullptr;
 size_t Heap::s_allocatedObjectSize = 0;
 size_t Heap::s_allocatedSpace = 0;
 size_t Heap::s_markedObjectSize = 0;
 
 } // namespace blink