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

Source/platform/heap/Heap.cpp

Index: Source/platform/heap/Heap.cpp
diff --git a/Source/platform/heap/Heap.cpp b/Source/platform/heap/Heap.cpp
index 96a3bebd1d58c422fb5e370da5f9d2f6b4f04d60..2bf4ad9485b77c093b54e0d3c11873f809a8bced 100644
--- a/Source/platform/heap/Heap.cpp
+++ b/Source/platform/heap/Heap.cpp
@@ -56,8 +56,15 @@
 #if OS(POSIX)
 #include <sys/mman.h>
 #include <unistd.h>
+#if COMPILER(GCC)
+#define PREFETCH(ptr)  __builtin_prefetch(static_cast<void*>(ptr))
+#else
+#define PREFETCH(ptr)
+#endif
 #elif OS(WIN)
 #include <windows.h>
+#include <xmmintrin.h>
+#define PREFETCH(ptr) _mm_prefetch((char*)(ptr), _MM_HINT_T0)

[haraken, 2014/12/15 15:42:55]

I think we should add these macros to wtf/, or at least ThreadState.h.

 #endif
 
 namespace blink {
@@ -678,7 +685,7 @@ void ThreadHeap<Header>::updateRemainingAllocationSize()
 }
 
 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)
@@ -687,55 +694,88 @@ Address ThreadHeap<Header>::outOfLineAllocate(size_t payloadSize, size_t allocat
     updateRemainingAllocationSize();
     threadState()->scheduleGCOrForceConservativeGCIfNeeded();
 
-    setAllocationPoint(nullptr, 0);
     ASSERT(allocationSize >= allocationGranularity);
-    if (allocateFromFreeList(allocationSize))
-        return allocate(payloadSize, gcInfo);
-    if (coalesce(allocationSize) && allocateFromFreeList(allocationSize))
-        return allocate(payloadSize, gcInfo);
+    Address result = allocateFromFreeList(allocationSize, gcInfo);
+    if (result)
+        return result;
+    setAllocationPoint(nullptr, 0);
+    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;
 }
 
 template<typename Header>
-FreeListEntry* FreeList<Header>::takeEntry(size_t allocationSize)
+Address ThreadHeap<Header>::allocateFromFreeListEntry(FreeListEntry* entry, size_t allocationSize, const GCInfo* gcInfo)

[haraken, 2014/12/15 15:42:55]

I'd prefer inline this method in the (only one) call site.

[sof, 2014/12/15 16:25:11]

I'd hope to reuse it for quicklists, but why not for now.

[sof, 2014/12/15 21:36:40]

Done.

+{
+    ASSERT(entry->size() >= allocationSize);
+    if (entry->size() > allocationSize)
+        addToFreeList(entry->address() + allocationSize, entry->size() - allocationSize);
+    Heap::increaseAllocatedObjectSize(allocationSize);
+    return allocateInto(entry->address(), allocationSize, gcInfo);
+}
+
+static bool useFirstFitForHeap(int heapIndex)

[haraken, 2014/12/15 15:42:55]

useFirstFitForHeap => shouldUseBestFit ?

[sof, 2014/12/15 21:36:40]

shouldUseFirstFitForHeap()

 {
-    size_t bucketSize = 1 << m_biggestFreeListIndex;
-    int i = m_biggestFreeListIndex;
+    if (heapIndex >= VectorBackingHeap && heapIndex <= HashTableBackingHeap)

[haraken, 2014/12/15 15:42:55]

Add a comment about why we should use a best-fit scheme for these backing
storages.

[sof, 2014/12/15 21:36:40]

Done.

+        return true;
+    if (heapIndex >= VectorBackingHeapNonFinalized && heapIndex <= HashTableBackingHeapNonFinalized)
+        return true;
+
+    return false;
+}
+
+template<typename Header>
+Address ThreadHeap<Header>::allocateFromFreeList(size_t allocationSize, const GCInfo* gcInfo)

[haraken, 2014/12/15 15:42:56]

Let's add a comment about the allocation scheme.

[sof, 2014/12/15 21:36:40]

Done.

+{
+    int bucket = FreeList<Header>::bucketIndexForSize(allocationSize) + 1;

[haraken, 2014/12/15 15:42:55]

Nit: I'm not sure if this matters for performance, but the current way of
calculating bucketIndexForSize is slow. I think we should replace the
implementation with a smarter bit-wise operation (if it matters for
performance). allocateFromFreeList is in a hot call path.

[sof, 2014/12/15 16:25:11]

Thought you said last week that outOfLineAllocate() wasn't a perf concern?

[haraken, 2014/12/15 16:38:18]

Right, so it wouldn't be worth doing. Ignore my comment.

+    if (bucket <= m_freeList.m_biggestFreeListIndex && useFirstFitForHeap(m_index)) {
+        if (FreeListEntry* entry = m_freeList.m_freeLists[bucket]) {
+            PREFETCH(entry->address());

[haraken, 2014/12/15 15:42:55]

Does this matter for performance?

- If no, let's remove it.
- If yes, you might also want to insert more PREFETCHes to the marking phase (as
you experimented before) in a follow-up CL.

(I'd prefer introducing PREFETCH in a separate CL either way.)

[sof, 2014/12/15 21:36:40]

It improves perf by 0.5-1% on a handful of shadow_dom tests, we can handle
prefetching separately.

I haven't thought about how prefetching could be utilized with eager marking -
prefetching the vtbl?

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

Ah, it wouldn't be trivial to utilize prefetching in eager tracing.

That said, I think we should look for more opportunity of prefetching. Probably
would it be helpful for sweeping?

+            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;

[haraken, 2014/12/15 15:42:56]

int maxIndex = m_freeList.m_biggestFreeListIndex - 1;

[sof, 2014/12/15 21:36:40]

Done.

+                for (; maxIndex >= 0 && !m_freeList.m_freeLists[maxIndex]; maxIndex--) { }
+                m_freeList.m_biggestFreeListIndex = maxIndex < 0 ? 0 : maxIndex;
+            }
+            // Allocate into the freelist block without disturbing the current allocation area.

[haraken, 2014/12/15 15:42:56]

I do agree that the best fit scheme works fine for collection backings, but
what's the point of not disturbing the current allocation point? What happens if
we just adjust the current allocation point to the best-fit position?

Intuitively, if we want to reuse as much promptly freed area of hash table
backings as possible, I guess we should adjust the current allocation point to
the best-fit slot, so that we can fall back to outOfLineAllocate more frequently
and thus have more chances to allocate the backings on the best-fit positions.

[sof, 2014/12/15 16:25:11]

What if you have a fairly big slab left, but you switch to a smaller one by
changing -- are you better off?

(And I did try to come up with heuristics for when it makes sense to switch,
without finding any.)

[haraken, 2014/12/15 16:38:18]

Hmm, I'm getting a bit confused.

You're at this point because you've eaten up the remaining size of the current
allocation area, so at this point there should be no big area left in the
current allocation area, right? Then it seems it doesn't really matter whether
we should switch the current allocation point to the best fit area or not in
most cases.

[sof, 2014/12/15 16:52:52]

It does matter in this case. What if the backing store allocation is larger than
most in a sequence, or that you get to reuse another freelist entry for the next
allocation by not switching? I don't have all the answers here about why this
particularly helps performance on this test.

[haraken, 2014/12/15 17:03:32]

Thanks, I'm 80% convinced :) Either way let's land this CL and iterate from
there. I'll take another close look tomorrow.

+            return allocateFromFreeListEntry(entry, 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 i = m_freeList.m_biggestFreeListIndex;

[haraken, 2014/12/15 15:42:56]

i => index

[sof, 2014/12/15 21:36:40]

Done.

     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)
+        FreeListEntry* entry = m_freeList.m_freeLists[i];
+        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) {
+            PREFETCH(entry->address());
+            entry->unlink(&m_freeList.m_freeLists[i]);
+            setAllocationPoint(entry->address(), entry->size());
+            ASSERT(hasCurrentAllocationArea());
+            ASSERT(remainingAllocationSize() >= allocationSize);
+            m_freeList.m_biggestFreeListIndex = i;
+            return allocateSize(allocationSize, gcInfo);
         }
     }
-    m_biggestFreeListIndex = i;
+    m_freeList.m_biggestFreeListIndex = i;
     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)