bmalloc: Segregate pages by objects size
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 20 Apr 2014 19:33:14 +0000 (19:33 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 20 Apr 2014 19:33:14 +0000 (19:33 +0000)
https://bugs.webkit.org/show_bug.cgi?id=131909

Reviewed by Andreas Kling.

2% reduction in memory-at-end on the Membuster memory_warning benchmarks.

* bmalloc/Allocator.cpp:
(bmalloc::Allocator::allocateSlowCase):
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase):
(bmalloc::Allocator::smallAllocatorFor): Use the new shared helper
function for size class calculation.

* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::Deallocator):
(bmalloc::Deallocator::scavenge):
(bmalloc::Deallocator::deallocateSmallLine):
(bmalloc::Deallocator::allocateSmallLine):
* bmalloc/Deallocator.h: Keep a cache for every size class, since the
cache can't be shared anymore.

* bmalloc/Heap.cpp:
(bmalloc::Heap::allocateSmallLineSlowCase):
* bmalloc/Heap.h:
(bmalloc::Heap::deallocateSmallLine): Ditto.

(bmalloc::Heap::allocateSmallLine): Check size class in addition to
page refcount when allocating a line because we might have deallocated
the page and the recycled it for another size class.

(bmalloc::Heap::deallocateMediumLine):
(bmalloc::Heap::allocateMediumLine):
* bmalloc/Line.h:
(bmalloc::Line::refCount):
* bmalloc/Page.h:
(bmalloc::Page::refCount):
(bmalloc::Page::smallSizeClass):
(bmalloc::Page::setSmallSizeClass):
(bmalloc::Page<Traits>::refCount): Deleted.
* bmalloc/Sizes.h:
(bmalloc::Sizes::smallSizeClassFor): New shared API for computing
an index into an array from a size.

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

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/Allocator.h
Source/bmalloc/bmalloc/Deallocator.cpp
Source/bmalloc/bmalloc/Deallocator.h
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/Line.h
Source/bmalloc/bmalloc/Page.h
Source/bmalloc/bmalloc/Sizes.h

index 2e6472c..bb8080f 100644 (file)
@@ -1,3 +1,49 @@
+2014-04-20  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Segregate pages by objects size
+        https://bugs.webkit.org/show_bug.cgi?id=131909
+
+        Reviewed by Andreas Kling.
+
+        2% reduction in memory-at-end on the Membuster memory_warning benchmarks.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::allocateSlowCase):
+        * bmalloc/Allocator.h:
+        (bmalloc::Allocator::allocateFastCase):
+        (bmalloc::Allocator::smallAllocatorFor): Use the new shared helper
+        function for size class calculation.
+
+        * bmalloc/Deallocator.cpp:
+        (bmalloc::Deallocator::Deallocator):
+        (bmalloc::Deallocator::scavenge):
+        (bmalloc::Deallocator::deallocateSmallLine):
+        (bmalloc::Deallocator::allocateSmallLine):
+        * bmalloc/Deallocator.h: Keep a cache for every size class, since the
+        cache can't be shared anymore.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::allocateSmallLineSlowCase):
+        * bmalloc/Heap.h:
+        (bmalloc::Heap::deallocateSmallLine): Ditto.
+
+        (bmalloc::Heap::allocateSmallLine): Check size class in addition to
+        page refcount when allocating a line because we might have deallocated
+        the page and the recycled it for another size class.
+
+        (bmalloc::Heap::deallocateMediumLine):
+        (bmalloc::Heap::allocateMediumLine):
+        * bmalloc/Line.h:
+        (bmalloc::Line::refCount):
+        * bmalloc/Page.h:
+        (bmalloc::Page::refCount):
+        (bmalloc::Page::smallSizeClass):
+        (bmalloc::Page::setSmallSizeClass):
+        (bmalloc::Page<Traits>::refCount): Deleted.
+        * bmalloc/Sizes.h:
+        (bmalloc::Sizes::smallSizeClassFor): New shared API for computing
+        an index into an array from a size.
+
 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
 
         bmalloc: Improved alignment in LargeChunk
index 784393e..eab2b6a 100644 (file)
@@ -145,9 +145,10 @@ IF_DEBUG(
     BASSERT(!allocateFastCase(size, dummy));
 )
     if (size <= smallMax) {
-        SmallAllocator& allocator = smallAllocatorFor(size);
+        size_t smallSizeClass = smallSizeClassFor(size);
+        SmallAllocator& allocator = m_smallAllocators[smallSizeClass];
         log(allocator);
-        allocator.refill(m_deallocator.allocateSmallLine());
+        allocator.refill(m_deallocator.allocateSmallLine(smallSizeClass));
         return allocator.allocate();
     }
 
index 5e6b2a0..a50e41a 100644 (file)
@@ -50,7 +50,6 @@ public:
     void scavenge();
 
 private:
-    SmallAllocator& smallAllocatorFor(size_t);
     void* allocateFastCase(SmallAllocator&);
 
     void* allocateMedium(size_t);
@@ -72,18 +71,12 @@ private:
     FixedVector<std::pair<MediumLine*, unsigned char>, mediumAllocatorLogCapacity> m_mediumAllocatorLog;
 };
 
-inline SmallAllocator& Allocator::smallAllocatorFor(size_t size)
-{
-    size_t index = mask((size - 1ul) / alignment, m_smallAllocators.size() - 1);
-    return m_smallAllocators[index];
-}
-
 inline bool Allocator::allocateFastCase(size_t size, void*& object)
 {
     if (size > smallMax)
         return false;
 
-    SmallAllocator& allocator = smallAllocatorFor(size);
+    SmallAllocator& allocator = m_smallAllocators[smallSizeClassFor(size)];
     if (!allocator.canAllocate())
         return false;
 
index 86a9209..fec941b 100644 (file)
@@ -40,7 +40,7 @@ namespace bmalloc {
 
 Deallocator::Deallocator()
     : m_objectLog()
-    , m_smallLineCache()
+    , m_smallLineCaches()
     , m_mediumLineCache()
 {
 }
@@ -57,8 +57,10 @@ void Deallocator::scavenge()
     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
     Heap* heap = PerProcess<Heap>::getFastCase();
     
-    while (m_smallLineCache.size())
-        heap->deallocateSmallLine(lock, m_smallLineCache.pop());
+    for (auto& smallLineCache : m_smallLineCaches) {
+        while (smallLineCache.size())
+            heap->deallocateSmallLine(lock, smallLineCache.pop());
+    }
     while (m_mediumLineCache.size())
         heap->deallocateMediumLine(lock, m_mediumLineCache.pop());
 }
@@ -119,23 +121,25 @@ void Deallocator::deallocateSlowCase(void* object)
 
 void Deallocator::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
 {
-    if (m_smallLineCache.size() == m_smallLineCache.capacity())
+    SmallLineCache& smallLineCache = m_smallLineCaches[SmallPage::get(line)->smallSizeClass()];
+    if (smallLineCache.size() == smallLineCache.capacity())
         return PerProcess<Heap>::getFastCase()->deallocateSmallLine(lock, line);
 
-    m_smallLineCache.push(line);
+    smallLineCache.push(line);
 }
 
-SmallLine* Deallocator::allocateSmallLine()
+SmallLine* Deallocator::allocateSmallLine(size_t smallSizeClass)
 {
-    if (!m_smallLineCache.size()) {
+    SmallLineCache& smallLineCache = m_smallLineCaches[smallSizeClass];
+    if (!smallLineCache.size()) {
         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
         Heap* heap = PerProcess<Heap>::getFastCase();
 
-        while (m_smallLineCache.size() != m_smallLineCache.capacity())
-            m_smallLineCache.push(heap->allocateSmallLine(lock));
+        while (smallLineCache.size() != smallLineCache.capacity())
+            smallLineCache.push(heap->allocateSmallLine(lock, smallSizeClass));
     }
 
-    return m_smallLineCache.pop();
+    return smallLineCache.pop();
 }
 
 void Deallocator::deallocateMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine* line)
index 0521b00..50a91ff 100644 (file)
@@ -45,7 +45,7 @@ public:
     void deallocateSlowCase(void*);
 
     void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
-    SmallLine* allocateSmallLine();
+    SmallLine* allocateSmallLine(size_t smallSizeClass);
 
     void deallocateMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
     MediumLine* allocateMediumLine();
@@ -53,13 +53,16 @@ public:
     void scavenge();
     
 private:
+    typedef FixedVector<SmallLine*, smallLineCacheCapacity> SmallLineCache;
+    typedef FixedVector<MediumLine*, mediumLineCacheCapacity> MediumLineCache;
+
     void deallocateLarge(void*);
     void deallocateXLarge(void*);
     void processObjectLog();
 
     FixedVector<void*, deallocatorLogCapacity> m_objectLog;
-    FixedVector<SmallLine*, smallLineCacheCapacity> m_smallLineCache;
-    FixedVector<MediumLine*, mediumLineCacheCapacity> m_mediumLineCache;
+    std::array<SmallLineCache, smallMax / alignment> m_smallLineCaches;
+    MediumLineCache m_mediumLineCache;
 };
 
 inline bool Deallocator::deallocateFastCase(void* object)
index f49960f..3fdd83d 100644 (file)
@@ -116,7 +116,7 @@ void Heap::scavengeLargeRanges(std::unique_lock<StaticMutex>& lock, std::chrono:
     }
 }
 
-SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<StaticMutex>& lock)
+SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<StaticMutex>& lock, size_t smallSizeClass)
 {
     m_isAllocatingPages = true;
 
@@ -130,9 +130,12 @@ SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<StaticMutex>& lock)
     }();
 
     SmallLine* line = page->begin();
+    Vector<SmallLine*>& smallLines = m_smallLines[smallSizeClass];
     for (auto it = line + 1; it != page->end(); ++it)
-        m_smallLines.push(it);
+        smallLines.push(it);
 
+    BASSERT(!line->refCount(lock));
+    page->setSmallSizeClass(smallSizeClass);
     page->ref(lock);
     return line;
 }
index bcf0794..2c417d2 100644 (file)
@@ -49,7 +49,7 @@ class Heap {
 public:
     Heap(std::lock_guard<StaticMutex>&);
 
-    SmallLine* allocateSmallLine(std::lock_guard<StaticMutex>&);
+    SmallLine* allocateSmallLine(std::lock_guard<StaticMutex>&, size_t smallSizeClass);
     void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
 
     MediumLine* allocateMediumLine(std::lock_guard<StaticMutex>&);
@@ -66,7 +66,7 @@ public:
 private:
     ~Heap() = delete;
 
-    SmallLine* allocateSmallLineSlowCase(std::lock_guard<StaticMutex>&);
+    SmallLine* allocateSmallLineSlowCase(std::lock_guard<StaticMutex>&, size_t smallSizeClass);
     MediumLine* allocateMediumLineSlowCase(std::lock_guard<StaticMutex>&);
 
     void* allocateLarge(Range, size_t);
@@ -82,7 +82,7 @@ private:
     void scavengeMediumPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
     void scavengeLargeRanges(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
 
-    Vector<SmallLine*> m_smallLines;
+    std::array<Vector<SmallLine*>, smallMax / alignment> m_smallLines;
     Vector<MediumLine*> m_mediumLines;
 
     Vector<SmallPage*> m_smallPages;
@@ -98,31 +98,35 @@ private:
 
 inline void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
 {
+    BASSERT(!line->refCount(lock));
     SmallPage* page = SmallPage::get(line);
     if (page->deref(lock)) {
         m_smallPages.push(page);
         m_scavenger.run();
         return;
     }
-    m_smallLines.push(line);
+    m_smallLines[page->smallSizeClass()].push(line);
 }
 
-inline SmallLine* Heap::allocateSmallLine(std::lock_guard<StaticMutex>& lock)
+inline SmallLine* Heap::allocateSmallLine(std::lock_guard<StaticMutex>& lock, size_t smallSizeClass)
 {
-    while (m_smallLines.size()) {
-        SmallLine* line = m_smallLines.pop();
+    Vector<SmallLine*>& smallLines = m_smallLines[smallSizeClass];
+    while (smallLines.size()) {
+        SmallLine* line = smallLines.pop();
         SmallPage* page = SmallPage::get(line);
-        if (!page->refCount(lock)) // The line was promoted to the small pages list.
+        if (!page->refCount(lock) || page->smallSizeClass() != smallSizeClass) // The line was promoted to the small pages list.
             continue;
+        BASSERT(!line->refCount(lock));
         page->ref(lock);
         return line;
     }
 
-    return allocateSmallLineSlowCase(lock);
+    return allocateSmallLineSlowCase(lock, smallSizeClass);
 }
 
 inline void Heap::deallocateMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine* line)
 {
+    BASSERT(!line->refCount(lock));
     MediumPage* page = MediumPage::get(line);
     if (page->deref(lock)) {
         m_mediumPages.push(page);
@@ -139,6 +143,7 @@ inline MediumLine* Heap::allocateMediumLine(std::lock_guard<StaticMutex>& lock)
         MediumPage* page = MediumPage::get(line);
         if (!page->refCount(lock)) // The line was promoted to the medium pages list.
             continue;
+        BASSERT(!line->refCount(lock));
         page->ref(lock);
         return line;
     }
index b9e1634..dc00a1e 100644 (file)
@@ -47,6 +47,7 @@ public:
 
     void concurrentRef(unsigned char = 1);
     bool deref(std::lock_guard<StaticMutex>&, unsigned char = 1);
+    unsigned refCount(std::lock_guard<StaticMutex>&) { return m_refCount; }
     
     char* begin();
     char* end();
index 692ff7f..9e829d6 100644 (file)
@@ -47,13 +47,17 @@ public:
 
     void ref(std::lock_guard<StaticMutex>&);
     bool deref(std::lock_guard<StaticMutex>&);
-    unsigned refCount(std::lock_guard<StaticMutex>&);
+    unsigned refCount(std::lock_guard<StaticMutex>&) { return m_refCount; }
+    
+    size_t smallSizeClass() { return m_smallSizeClass; }
+    void setSmallSizeClass(size_t smallSizeClass) { m_smallSizeClass = smallSizeClass; }
     
     Line* begin();
     Line* end();
 
 private:
     unsigned char m_refCount;
+    unsigned char m_smallSizeClass;
 };
 
 template<typename Traits>
@@ -72,12 +76,6 @@ inline bool Page<Traits>::deref(std::lock_guard<StaticMutex>&)
 }
 
 template<typename Traits>
-inline unsigned Page<Traits>::refCount(std::lock_guard<StaticMutex>&)
-{
-    return m_refCount;
-}
-
-template<typename Traits>
 inline auto Page<Traits>::get(Line* line) -> Page*
 {
     Chunk* chunk = Chunk::get(line);
index 035da50..dbedb76 100644 (file)
@@ -89,6 +89,12 @@ namespace Sizes {
     static const size_t mediumAllocatorLogCapacity = 8;
     
     static const std::chrono::milliseconds scavengeSleepDuration = std::chrono::milliseconds(512);
+
+    inline size_t smallSizeClassFor(size_t size)
+    {
+        static const size_t smallSizeClassMask = (smallMax / alignment) - 1;
+        return mask((size - 1ul) / alignment, smallSizeClassMask);
+    }
 };
 
 using namespace Sizes;