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 38 matching lines @@
 #include <stdio.h>
 #include <utility>
 #endif
 #if ENABLE(GC_PROFILE_HEAP)
 #include "platform/TracedValue.h"
 #endif
 
 #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 {
 
 #if ENABLE(GC_PROFILE_MARKING)
 static String classOf(const void* object)
 {
     if (const GCInfo* gcInfo = Heap::findGCInfo(reinterpret_cast<Address>(const_cast<void*>(object))))
         return gcInfo->m_className;
     return "unknown";
@@ skipping 600 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;
 }
 
 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.

 {
-    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)
-                break;
-        }
-        if (FreeListEntry* entry = m_freeLists[i]) {
-            m_biggestFreeListIndex = i;
-            entry->unlink(&m_freeLists[i]);
-            return entry;
-        }
-    }
-    m_biggestFreeListIndex = i;
-    return nullptr;
+    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()

+{
+    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>
-bool ThreadHeap<Header>::allocateFromFreeList(size_t allocationSize)
+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.

 {
-    ASSERT(!hasCurrentAllocationArea());
-    if (FreeListEntry* entry = m_freeList.takeEntry(allocationSize)) {
-        setAllocationPoint(entry->address(), entry->size());
-        ASSERT(hasCurrentAllocationArea());
-        ASSERT(remainingAllocationSize() >= allocationSize);
-        return true;
+    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.
     }
-    return false;
+    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) {
+        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 (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_freeList.m_biggestFreeListIndex = i;
+    return nullptr;
 }
 
 #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));
 }
@@ skipping 2195 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