bmalloc: Add a per-thread line cache
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 24 Jun 2017 20:14:33 +0000 (20:14 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 24 Jun 2017 20:14:33 +0000 (20:14 +0000)
https://bugs.webkit.org/show_bug.cgi?id=173552

Reviewed by Darin Adler.

Previously, any thread could allocate out of any page with free lines.
Now, the first thread to free a line in a page owns that page's free
lines until the whole page becomes free.

This patch is a big speedup on multi-threaded benchmarks.
tree_churn --parallel gets 14% faster on a 2-core (4-hyper-core) MacBook
Air and 2.85X faster on 12-core (24-hyper-core) Mac Pro. Other parallel
benchmarks show significant but smaller speedups.

Thread affinity is a great predictor of object lifetime. The per-thread
line cache avoids the pathology of shuffling pages between threads,
turning predictable lifetimes into unpredictable lifetimes, increasing
fragmentation. On tree_churn --parallel, the per-thread line cache
increases free memory found per page scanned by 2.85X.

Free line scanning in fragmented pages is pretty expensive relative to
other allocate / initialize / free operations. According to Instruments,
on tree_churn --parallel, scanning is about 10X more expensive than
freeing. This explains why a 2.85X improvement in scanning efficiency
translates into a 2.85X overall speedup on tree_churn --parallel.

* bmalloc/Allocator.cpp:
(bmalloc::Allocator::refillAllocatorSlowCase): Pass through our line
cache so the Heap can fill it.

* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::scavenge): Scavenge our line cache.

(bmalloc::Deallocator::processObjectLog): Deleted.

* bmalloc/Deallocator.h:
(bmalloc::Deallocator::lineCache): Added a line cache.

* bmalloc/Heap.cpp:
(bmalloc::Heap::deallocateLineCache): Deallocation function for thread
destruction.

(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::allocateSmallBumpRangesByMetadata):
(bmalloc::Heap::allocateSmallBumpRangesByObject): Consult the new per-thread line
cache for allocation and deallocation.

* bmalloc/Heap.h:
(bmalloc::Heap::allocateSmallBumpRanges):
(bmalloc::Heap::derefSmallLine):

* bmalloc/List.h:
(bmalloc::List::remove): Remove has always been a logically static
operation. Declare it static now so that the Heap can remove a page from
a thread's line cache without holding a direct pointer to the cache.

* bmalloc/SmallPage.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@218788 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/Deallocator.cpp
Source/bmalloc/bmalloc/Deallocator.h
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/List.h
Source/bmalloc/bmalloc/SmallPage.h

index eaaba99..042bc7e 100644 (file)
@@ -1,3 +1,64 @@
+2017-06-19  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Add a per-thread line cache
+        https://bugs.webkit.org/show_bug.cgi?id=173552
+
+        Reviewed by Darin Adler.
+
+        Previously, any thread could allocate out of any page with free lines.
+        Now, the first thread to free a line in a page owns that page's free
+        lines until the whole page becomes free.
+
+        This patch is a big speedup on multi-threaded benchmarks.
+        tree_churn --parallel gets 14% faster on a 2-core (4-hyper-core) MacBook
+        Air and 2.85X faster on 12-core (24-hyper-core) Mac Pro. Other parallel
+        benchmarks show significant but smaller speedups.
+
+        Thread affinity is a great predictor of object lifetime. The per-thread
+        line cache avoids the pathology of shuffling pages between threads,
+        turning predictable lifetimes into unpredictable lifetimes, increasing
+        fragmentation. On tree_churn --parallel, the per-thread line cache
+        increases free memory found per page scanned by 2.85X.
+
+        Free line scanning in fragmented pages is pretty expensive relative to
+        other allocate / initialize / free operations. According to Instruments,
+        on tree_churn --parallel, scanning is about 10X more expensive than
+        freeing. This explains why a 2.85X improvement in scanning efficiency
+        translates into a 2.85X overall speedup on tree_churn --parallel.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::refillAllocatorSlowCase): Pass through our line
+        cache so the Heap can fill it.
+
+        * bmalloc/Deallocator.cpp:
+        (bmalloc::Deallocator::scavenge): Scavenge our line cache.
+
+        (bmalloc::Deallocator::processObjectLog): Deleted.
+
+        * bmalloc/Deallocator.h:
+        (bmalloc::Deallocator::lineCache): Added a line cache.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::deallocateLineCache): Deallocation function for thread
+        destruction.
+
+        (bmalloc::Heap::allocateSmallPage):
+        (bmalloc::Heap::deallocateSmallLine):
+        (bmalloc::Heap::allocateSmallBumpRangesByMetadata):
+        (bmalloc::Heap::allocateSmallBumpRangesByObject): Consult the new per-thread line
+        cache for allocation and deallocation.
+
+        * bmalloc/Heap.h:
+        (bmalloc::Heap::allocateSmallBumpRanges):
+        (bmalloc::Heap::derefSmallLine):
+
+        * bmalloc/List.h:
+        (bmalloc::List::remove): Remove has always been a logically static
+        operation. Declare it static now so that the Heap can remove a page from
+        a thread's line cache without holding a direct pointer to the cache.
+
+        * bmalloc/SmallPage.h:
+
 2017-06-10  Dan Bernstein  <mitz@apple.com>
 
         Reverted r218056 because it made the IDE reindex constantly.
index 9ac72d3..b4dcf62 100644 (file)
@@ -155,7 +155,8 @@ NO_INLINE void Allocator::refillAllocatorSlowCase(BumpAllocator& allocator, size
 
     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
     m_deallocator.processObjectLog(lock);
-    PerProcess<Heap>::getFastCase()->allocateSmallBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
+    PerProcess<Heap>::getFastCase()->allocateSmallBumpRanges(
+        lock, sizeClass, allocator, bumpRangeCache, m_deallocator.lineCache(lock));
 }
 
 INLINE void Allocator::refillAllocator(BumpAllocator& allocator, size_t sizeClass)
index 56bb4d6..b39a8a7 100644 (file)
@@ -59,7 +59,10 @@ void Deallocator::scavenge()
     if (m_debugHeap)
         return;
 
-    processObjectLog();
+    std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
+
+    processObjectLog(lock);
+    PerProcess<Heap>::getFastCase()->deallocateLineCache(lock, lineCache(lock));
 }
 
 void Deallocator::processObjectLog(std::lock_guard<StaticMutex>& lock)
@@ -67,17 +70,10 @@ void Deallocator::processObjectLog(std::lock_guard<StaticMutex>& lock)
     Heap* heap = PerProcess<Heap>::getFastCase();
     
     for (Object object : m_objectLog)
-        heap->derefSmallLine(lock, object);
-
+        heap->derefSmallLine(lock, object, lineCache(lock));
     m_objectLog.clear();
 }
 
-void Deallocator::processObjectLog()
-{
-    std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-    processObjectLog(lock);
-}
-
 void Deallocator::deallocateSlowCase(void* object)
 {
     if (m_debugHeap)
index 00b116d..9a64d45 100644 (file)
@@ -27,6 +27,7 @@
 #define Deallocator_h
 
 #include "FixedVector.h"
+#include "SmallPage.h"
 #include <mutex>
 
 namespace bmalloc {
@@ -45,14 +46,16 @@ public:
     void deallocate(void*);
     void scavenge();
     
-    void processObjectLog();
     void processObjectLog(std::lock_guard<StaticMutex>&);
+    
+    LineCache& lineCache(std::lock_guard<StaticMutex>&) { return m_lineCache; }
 
 private:
     bool deallocateFastCase(void*);
     void deallocateSlowCase(void*);
 
     FixedVector<void*, deallocatorLogCapacity> m_objectLog;
+    LineCache m_lineCache; // The Heap removes items from this cache.
     DebugHeap* m_debugHeap;
 };
 
index 856b6cc..fdbdc7b 100644 (file)
@@ -191,6 +191,16 @@ void Heap::scheduleScavenger(size_t bytes)
     m_scavenger.runSoon();
 }
 
+void Heap::deallocateLineCache(std::lock_guard<StaticMutex>&, LineCache& lineCache)
+{
+    for (auto& list : lineCache) {
+        while (!list.isEmpty()) {
+            size_t sizeClass = &list - &lineCache[0];
+            m_lineCache[sizeClass].push(list.popFront());
+        }
+    }
+}
+
 void Heap::allocateSmallChunk(std::lock_guard<StaticMutex>& lock, size_t pageClass)
 {
     size_t pageSize = bmalloc::pageSize(pageClass);
@@ -235,10 +245,13 @@ void Heap::deallocateSmallChunk(Chunk* chunk, size_t pageClass)
     m_largeFree.add(LargeRange(chunk, size, physicalSize));
 }
 
-SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
+SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass, LineCache& lineCache)
 {
-    if (!m_freeLines[sizeClass].isEmpty())
-        return m_freeLines[sizeClass].popFront();
+    if (!lineCache[sizeClass].isEmpty())
+        return lineCache[sizeClass].popFront();
+
+    if (!m_lineCache[sizeClass].isEmpty())
+        return m_lineCache[sizeClass].popFront();
 
     m_isGrowing = true;
     
@@ -270,7 +283,7 @@ SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t si
     return page;
 }
 
-void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, Object object)
+void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, Object object, LineCache& lineCache)
 {
     BASSERT(!object.line()->refCount(lock));
     SmallPage* page = object.page();
@@ -278,7 +291,7 @@ void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, Object object
 
     if (!page->hasFreeLines(lock)) {
         page->setHasFreeLines(lock, true);
-        m_freeLines[page->sizeClass()].push(page);
+        lineCache[page->sizeClass()].push(page);
     }
 
     if (page->refCount(lock))
@@ -287,7 +300,7 @@ void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, Object object
     size_t sizeClass = page->sizeClass();
     size_t pageClass = m_pageClasses[sizeClass];
 
-    m_freeLines[sizeClass].remove(page);
+    List<SmallPage>::remove(page); // 'page' may be in any thread's line cache.
     
     Chunk* chunk = Chunk::get(page);
     if (chunk->freePages().isEmpty())
@@ -310,9 +323,10 @@ void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, Object object
 
 void Heap::allocateSmallBumpRangesByMetadata(
     std::lock_guard<StaticMutex>& lock, size_t sizeClass,
-    BumpAllocator& allocator, BumpRangeCache& rangeCache)
+    BumpAllocator& allocator, BumpRangeCache& rangeCache,
+    LineCache& lineCache)
 {
-    SmallPage* page = allocateSmallPage(lock, sizeClass);
+    SmallPage* page = allocateSmallPage(lock, sizeClass, lineCache);
     SmallLine* lines = page->begin();
     BASSERT(page->hasFreeLines(lock));
     size_t smallLineCount = m_vmPageSizePhysical / smallLineSize;
@@ -356,7 +370,7 @@ void Heap::allocateSmallBumpRangesByMetadata(
 
         // In a fragmented page, some free ranges might not fit in the cache.
         if (rangeCache.size() == rangeCache.capacity()) {
-            m_freeLines[sizeClass].push(page);
+            lineCache[sizeClass].push(page);
             BASSERT(allocator.canAllocate());
             return;
         }
@@ -371,10 +385,11 @@ void Heap::allocateSmallBumpRangesByMetadata(
 
 void Heap::allocateSmallBumpRangesByObject(
     std::lock_guard<StaticMutex>& lock, size_t sizeClass,
-    BumpAllocator& allocator, BumpRangeCache& rangeCache)
+    BumpAllocator& allocator, BumpRangeCache& rangeCache,
+    LineCache& lineCache)
 {
     size_t size = allocator.size();
-    SmallPage* page = allocateSmallPage(lock, sizeClass);
+    SmallPage* page = allocateSmallPage(lock, sizeClass, lineCache);
     BASSERT(page->hasFreeLines(lock));
 
     auto findSmallBumpRange = [&](Object& it, Object& end) {
@@ -410,7 +425,7 @@ void Heap::allocateSmallBumpRangesByObject(
 
         // In a fragmented page, some free ranges might not fit in the cache.
         if (rangeCache.size() == rangeCache.capacity()) {
-            m_freeLines[sizeClass].push(page);
+            lineCache[sizeClass].push(page);
             BASSERT(allocator.canAllocate());
             return;
         }
index dd903bf..8a00a23 100644 (file)
@@ -59,8 +59,10 @@ public:
     
     DebugHeap* debugHeap() { return m_debugHeap; }
 
-    void allocateSmallBumpRanges(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpAllocator&, BumpRangeCache&);
-    void derefSmallLine(std::lock_guard<StaticMutex>&, Object);
+    void allocateSmallBumpRanges(std::lock_guard<StaticMutex>&, size_t sizeClass,
+        BumpAllocator&, BumpRangeCache&, LineCache&);
+    void derefSmallLine(std::lock_guard<StaticMutex>&, Object, LineCache&);
+    void deallocateLineCache(std::lock_guard<StaticMutex>&, LineCache&);
 
     void* allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
     void* tryAllocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
@@ -91,12 +93,12 @@ private:
     void initializePageMetadata();
 
     void allocateSmallBumpRangesByMetadata(std::lock_guard<StaticMutex>&,
-        size_t sizeClass, BumpAllocator&, BumpRangeCache&);
+        size_t sizeClass, BumpAllocator&, BumpRangeCache&, LineCache&);
     void allocateSmallBumpRangesByObject(std::lock_guard<StaticMutex>&,
-        size_t sizeClass, BumpAllocator&, BumpRangeCache&);
+        size_t sizeClass, BumpAllocator&, BumpRangeCache&, LineCache&);
 
-    SmallPage* allocateSmallPage(std::lock_guard<StaticMutex>&, size_t sizeClass);
-    void deallocateSmallLine(std::lock_guard<StaticMutex>&, Object);
+    SmallPage* allocateSmallPage(std::lock_guard<StaticMutex>&, size_t sizeClass, LineCache&);
+    void deallocateSmallLine(std::lock_guard<StaticMutex>&, Object, LineCache&);
 
     void allocateSmallChunk(std::lock_guard<StaticMutex>&, size_t pageClass);
     void deallocateSmallChunk(Chunk*, size_t pageClass);
@@ -116,7 +118,7 @@ private:
     Vector<LineMetadata> m_smallLineMetadata;
     std::array<size_t, sizeClassCount> m_pageClasses;
 
-    std::array<List<SmallPage>, sizeClassCount> m_freeLines;
+    LineCache m_lineCache;
     std::array<List<Chunk>, pageClassCount> m_freePages;
     std::array<List<Chunk>, pageClassCount> m_chunkCache;
 
@@ -143,18 +145,19 @@ private:
 
 inline void Heap::allocateSmallBumpRanges(
     std::lock_guard<StaticMutex>& lock, size_t sizeClass,
-    BumpAllocator& allocator, BumpRangeCache& rangeCache)
+    BumpAllocator& allocator, BumpRangeCache& rangeCache,
+    LineCache& lineCache)
 {
     if (sizeClass < bmalloc::sizeClass(smallLineSize))
-        return allocateSmallBumpRangesByMetadata(lock, sizeClass, allocator, rangeCache);
-    return allocateSmallBumpRangesByObject(lock, sizeClass, allocator, rangeCache);
+        return allocateSmallBumpRangesByMetadata(lock, sizeClass, allocator, rangeCache, lineCache);
+    return allocateSmallBumpRangesByObject(lock, sizeClass, allocator, rangeCache, lineCache);
 }
 
-inline void Heap::derefSmallLine(std::lock_guard<StaticMutex>& lock, Object object)
+inline void Heap::derefSmallLine(std::lock_guard<StaticMutex>& lock, Object object, LineCache& lineCache)
 {
     if (!object.line()->deref(lock))
         return;
-    deallocateSmallLine(lock, object);
+    deallocateSmallLine(lock, object, lineCache);
 }
 
 } // namespace bmalloc
index 32d5a3f..8de7e47 100644 (file)
@@ -103,7 +103,7 @@ public:
         return static_cast<T*>(result);
     }
 
-    void insertAfter(ListNode<T>* it, ListNode<T>* node)
+    static void insertAfter(ListNode<T>* it, ListNode<T>* node)
     {
         ListNode<T>* prev = it;
         ListNode<T>* next = it->next;
@@ -115,7 +115,7 @@ public:
         prev->next = node;
     }
 
-    void remove(ListNode<T>* node)
+    static void remove(ListNode<T>* node)
     {
         ListNode<T>* next = node->next;
         ListNode<T>* prev = node->prev;
index 3c11376..b6c29de 100644 (file)
@@ -34,6 +34,8 @@
 
 namespace bmalloc {
 
+class SmallLine;
+
 class SmallPage : public ListNode<SmallPage> {
 public:
     void ref(std::lock_guard<StaticMutex>&);
@@ -66,6 +68,8 @@ static_assert(
     "Largest size class must fit in SmallPage metadata");
 };
 
+using LineCache = std::array<List<SmallPage>, sizeClassCount>;
+
 inline void SmallPage::ref(std::lock_guard<StaticMutex>&)
 {
     BASSERT(!m_slide);