bmalloc: Use List<T> instead of Vector<T> in some places
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 8 Mar 2016 03:01:00 +0000 (03:01 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 8 Mar 2016 03:01:00 +0000 (03:01 +0000)
https://bugs.webkit.org/show_bug.cgi?id=155150

Reviewed by Andreas Kling.

Vector<T> is expensive when you want a lot of them because our minimum
allocation size is the system page size.

* bmalloc.xcodeproj/project.pbxproj: Added a List<T> class.

* bmalloc/Heap.cpp:
(bmalloc::Heap::scavengeSmallPages):
(bmalloc::Heap::allocateSmallPage): Use the List<T> API. No need to check
for stale entries anymore because List<T> supports O(1) eager removal
and we remove eagerly now.

(bmalloc::Heap::deallocateSmallLine): Remove eagerly. This simplifies
the allocation code and it is also required for correctness since we
only have enough metadata to be in one list at a time.

* bmalloc/Heap.h: List!

* bmalloc/SmallChunk.h: Made this assert a little more precise since this
patch triggered the old version in a benign way.

(bmalloc::SmallChunk::SmallChunk): This code moved to the SmallPage
constructor.

* bmalloc/SmallPage.h:
(bmalloc::SmallPage::SmallPage): Accomodate the List<T> data structure.
This is a net memory savings on Mac for heaps smaller than ~128MB and on
iOS for heaps smaller than ~512MB. The maximum memory saved is 512kB on
Mac and 2MB on iOS. For larger heaps, there's a memory cost of 0.4% on
Mac and 0.1% on iOS.

* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateSmallPage): Use List<T> API.

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

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/List.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SmallChunk.h
Source/bmalloc/bmalloc/SmallPage.h
Source/bmalloc/bmalloc/VMHeap.h

index ff2935e..16c4822 100644 (file)
@@ -1,3 +1,43 @@
+2016-03-07  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Use List<T> instead of Vector<T> in some places
+        https://bugs.webkit.org/show_bug.cgi?id=155150
+
+        Reviewed by Andreas Kling.
+
+        Vector<T> is expensive when you want a lot of them because our minimum
+        allocation size is the system page size.
+
+        * bmalloc.xcodeproj/project.pbxproj: Added a List<T> class.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::scavengeSmallPages):
+        (bmalloc::Heap::allocateSmallPage): Use the List<T> API. No need to check
+        for stale entries anymore because List<T> supports O(1) eager removal
+        and we remove eagerly now.
+
+        (bmalloc::Heap::deallocateSmallLine): Remove eagerly. This simplifies
+        the allocation code and it is also required for correctness since we
+        only have enough metadata to be in one list at a time.
+
+        * bmalloc/Heap.h: List!
+
+        * bmalloc/SmallChunk.h: Made this assert a little more precise since this
+        patch triggered the old version in a benign way.
+
+        (bmalloc::SmallChunk::SmallChunk): This code moved to the SmallPage
+        constructor.
+
+        * bmalloc/SmallPage.h:
+        (bmalloc::SmallPage::SmallPage): Accomodate the List<T> data structure.
+        This is a net memory savings on Mac for heaps smaller than ~128MB and on
+        iOS for heaps smaller than ~512MB. The maximum memory saved is 512kB on
+        Mac and 2MB on iOS. For larger heaps, there's a memory cost of 0.4% on
+        Mac and 0.1% on iOS.
+
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateSmallPage): Use List<T> API.
+
 2016-03-03  Geoffrey Garen  <ggaren@apple.com>
 
         Unreviewed, rolling in r197174.
index 81670f1..f1ff74c 100644 (file)
@@ -12,6 +12,7 @@
                1400274C18F89C3D00115C97 /* SegregatedFreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
                140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 140FA00219CE429C00FFD3C8 /* BumpRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
                140FA00519CE4B6800FFD3C8 /* LineMetadata.h in Headers */ = {isa = PBXBuildFile; fileRef = 140FA00419CE4B6800FFD3C8 /* LineMetadata.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               141D9B001C8E51C0000ABBA0 /* List.h in Headers */ = {isa = PBXBuildFile; fileRef = 141D9AFF1C8E51C0000ABBA0 /* List.h */; settings = {ATTRIBUTES = (Private, ); }; };
                143CB81C19022BC900B16A45 /* StaticMutex.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143CB81A19022BC900B16A45 /* StaticMutex.cpp */; };
                143CB81D19022BC900B16A45 /* StaticMutex.h in Headers */ = {isa = PBXBuildFile; fileRef = 143CB81B19022BC900B16A45 /* StaticMutex.h */; settings = {ATTRIBUTES = (Private, ); }; };
                143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */; };
@@ -86,6 +87,7 @@
                1417F64618B54A700076FA3F /* EndTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = EndTag.h; path = bmalloc/EndTag.h; sourceTree = "<group>"; };
                1417F64F18B7280C0076FA3F /* Syscall.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Syscall.h; path = bmalloc/Syscall.h; sourceTree = "<group>"; };
                1417F65218BA88A00076FA3F /* AsyncTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AsyncTask.h; path = bmalloc/AsyncTask.h; sourceTree = "<group>"; };
+               141D9AFF1C8E51C0000ABBA0 /* List.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = List.h; path = bmalloc/List.h; sourceTree = "<group>"; };
                1421A87718EE462A00B4DD68 /* Algorithm.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = Algorithm.h; path = bmalloc/Algorithm.h; sourceTree = "<group>"; };
                143CB81A19022BC900B16A45 /* StaticMutex.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = StaticMutex.cpp; path = bmalloc/StaticMutex.cpp; sourceTree = "<group>"; };
                143CB81B19022BC900B16A45 /* StaticMutex.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StaticMutex.h; path = bmalloc/StaticMutex.h; sourceTree = "<group>"; };
                                14C919C818FCC59F0028DB43 /* BPlatform.h */,
                                14D9DB4517F2447100EAAB79 /* FixedVector.h */,
                                1413E460189DCE1E00546D68 /* Inline.h */,
+                               141D9AFF1C8E51C0000ABBA0 /* List.h */,
                                144DCED617A649D90093B2F2 /* Mutex.h */,
                                14446A0717A61FA400F9EA1D /* PerProcess.h */,
                                144469FD17A61F1F00F9EA1D /* PerThread.h */,
                                14DD789818F48D4A00950702 /* Allocator.h in Headers */,
                                14DD78CB18F48D7500950702 /* PerProcess.h in Headers */,
                                14DD789318F48D0F00950702 /* ObjectType.h in Headers */,
+                               141D9B001C8E51C0000ABBA0 /* List.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index 3003ffa..c6cc510 100644 (file)
@@ -93,7 +93,7 @@ void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::millisecon
 
 void Heap::scavengeSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
 {
-    while (m_smallPages.size()) {
+    while (!m_smallPages.isEmpty()) {
         m_vmHeap.deallocateSmallPage(lock, m_smallPages.pop());
         waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
     }
@@ -177,16 +177,11 @@ void Heap::allocateSmallBumpRanges(std::lock_guard<StaticMutex>& lock, size_t si
 
 SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
 {
-    Vector<SmallPage*>& smallPagesWithFreeLines = m_smallPagesWithFreeLines[sizeClass];
-    while (smallPagesWithFreeLines.size()) {
-        SmallPage* page = smallPagesWithFreeLines.pop();
-        if (!page->refCount(lock) || page->sizeClass() != sizeClass) // Page was promoted to the pages list.
-            continue;
-        return page;
-    }
+    if (!m_smallPagesWithFreeLines[sizeClass].isEmpty())
+        return m_smallPagesWithFreeLines[sizeClass].pop();
 
     SmallPage* page = [this, &lock]() {
-        if (m_smallPages.size())
+        if (!m_smallPages.isEmpty())
             return m_smallPages.pop();
 
         m_isAllocatingPages = true;
@@ -215,6 +210,7 @@ void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* li
     if (page->refCount(lock))
         return;
 
+    m_smallPagesWithFreeLines[page->sizeClass()].remove(page);
     m_smallPages.push(page);
     m_scavenger.run();
 }
index 1007784..1e680af 100644 (file)
@@ -29,6 +29,7 @@
 #include "BumpRange.h"
 #include "Environment.h"
 #include "LineMetadata.h"
+#include "List.h"
 #include "Mutex.h"
 #include "SegregatedFreeList.h"
 #include "SmallChunk.h"
@@ -93,9 +94,9 @@ private:
 
     std::array<std::array<LineMetadata, smallLineCount>, smallMax / alignment> m_smallLineMetadata;
 
-    std::array<Vector<SmallPage*>, smallMax / alignment> m_smallPagesWithFreeLines;
+    std::array<List<SmallPage>, smallMax / alignment> m_smallPagesWithFreeLines;
 
-    Vector<SmallPage*> m_smallPages;
+    List<SmallPage> m_smallPages;
 
     SegregatedFreeList m_largeObjects;
     
diff --git a/Source/bmalloc/bmalloc/List.h b/Source/bmalloc/bmalloc/List.h
new file mode 100644 (file)
index 0000000..eb04d2f
--- /dev/null
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2016 Apple 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:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef List_h
+#define List_h
+
+namespace bmalloc {
+
+template<typename T>
+struct ListNode {
+    ListNode()
+        : prev(this)
+        , next(this)
+    {
+    }
+
+    ListNode<T>* prev;
+    ListNode<T>* next;
+};
+
+template<typename T>
+class List {
+    static_assert(std::is_trivially_destructible<T>::value, "List must have a trivial destructor.");
+public:
+    bool isEmpty() { return m_root.next == &m_root; }
+
+    T* head() { return static_cast<T*>(m_root.next); }
+    T* tail() { return static_cast<T*>(m_root.prev); }
+
+    void push(T* node)
+    {
+        ListNode<T>* it = tail();
+        insertAfter(it, node);
+    }
+
+    T* pop()
+    {
+        ListNode<T>* result = tail();
+        remove(result);
+        return static_cast<T*>(result);
+    }
+
+    void insertAfter(ListNode<T>* it, ListNode<T>* node)
+    {
+        ListNode<T>* prev = it;
+        ListNode<T>* next = it->next;
+
+        node->next = next;
+        next->prev = node;
+
+        node->prev = prev;
+        prev->next = node;
+    }
+
+    void remove(ListNode<T>* node)
+    {
+        ListNode<T>* next = node->next;
+        ListNode<T>* prev = node->prev;
+
+        next->prev = prev;
+        prev->next = next;
+    }
+
+private:
+    ListNode<T> m_root;
+};
+
+} // namespace bmalloc
+
+#endif // List_h
index 4b144dc..aeee4f2 100644 (file)
@@ -54,8 +54,8 @@ private:
 static_assert(!(vmPageSize % smallLineSize), "vmPageSize must be an even multiple of line size");
 static_assert(!(smallChunkSize % smallLineSize), "chunk size must be an even multiple of line size");
 static_assert(
-    sizeof(SmallChunk) - vmPageSize % sizeof(SmallChunk) < vmPageSize - 2 * smallMax,
-        "the first page of object memory in a small chunk can't allocate smallMax");
+    sizeof(SmallChunk) % vmPageSize + smallMax <= vmPageSize,
+    "the first page of object memory in a small chunk must be able to allocate smallMax");
 
 inline SmallChunk::SmallChunk(std::lock_guard<StaticMutex>& lock)
 {
index f33fb06..21aa461 100644 (file)
 #define SmallPage_h
 
 #include "BAssert.h"
+#include "List.h"
 #include "Mutex.h"
 #include "VMAllocate.h"
 #include <mutex>
 
 namespace bmalloc {
 
-class SmallPage {
+class SmallPage : public ListNode<SmallPage> {
 public:
     static const unsigned char maxRefCount = std::numeric_limits<unsigned char>::max();
     static_assert(smallLineCount < maxRefCount, "maximum line count must fit in SmallPage");
     
     static SmallPage* get(SmallLine*);
 
+    SmallPage()
+        : m_hasFreeLines(true)
+    {
+    }
+
     void ref(std::lock_guard<StaticMutex>&);
     bool deref(std::lock_guard<StaticMutex>&);
     unsigned refCount(std::lock_guard<StaticMutex>&) { return m_refCount; }
index 649e493..d73f0af 100644 (file)
@@ -62,7 +62,7 @@ private:
     LargeObject allocateLargeChunk(std::lock_guard<StaticMutex>&);
     void allocateSuperChunk(std::lock_guard<StaticMutex>&);
 
-    Vector<SmallPage*> m_smallPages;
+    List<SmallPage> m_smallPages;
     SegregatedFreeList m_largeObjects;
 
     Vector<SuperChunk*> m_smallChunks;
@@ -75,7 +75,7 @@ private:
 
 inline SmallPage* VMHeap::allocateSmallPage(std::lock_guard<StaticMutex>& lock)
 {
-    if (!m_smallPages.size())
+    if (m_smallPages.isEmpty())
         allocateSmallChunk(lock);
 
     SmallPage* page = m_smallPages.pop();