<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[191196] trunk/Source/bmalloc</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/191196">191196</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2015-10-16 12:59:30 -0700 (Fri, 16 Oct 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>bmalloc: per-thread cache data structure should be smaller
https://bugs.webkit.org/show_bug.cgi?id=150218
Reviewed by Andreas Kling.
Reduce the number of entries in the range cache because it's really
big, and the bigness only helps in cases of serious fragmentation, and
it only saves us a little bit of lock acquisition time.
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::scavenge):
(bmalloc::Allocator::refillAllocatorSlowCase):
(bmalloc::Allocator::refillAllocator):
(bmalloc::Allocator::allocateLarge):
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateBumpRangeSlowCase): Deleted.
(bmalloc::Allocator::allocateBumpRange): Deleted.
* bmalloc/Allocator.h: Pass through the empty allocator and the range
cache when refilling, and refill both. Otherwise, we always immediately
pop the last item in the range cache, wasting that slot of capacity.
* bmalloc/Heap.cpp:
(bmalloc::Heap::allocateSmallBumpRanges):
(bmalloc::Heap::allocateMediumBumpRanges): Account for the fact that
the range cache is no longer big enough to guarantee that it can hold
all the ranges in a page.
(bmalloc::Heap::refillSmallBumpRangeCache): Deleted.
(bmalloc::Heap::refillMediumBumpRangeCache): Deleted.
* bmalloc/Heap.h: Move VMHeap to the end of the object because it
contains a lot of unused / wasted space, and we want to pack our data
together in memory.
* bmalloc/Sizes.h: Make the range cache smaller.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourcebmallocChangeLog">trunk/Source/bmalloc/ChangeLog</a></li>
<li><a href="#trunkSourcebmallocbmallocAllocatorcpp">trunk/Source/bmalloc/bmalloc/Allocator.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocAllocatorh">trunk/Source/bmalloc/bmalloc/Allocator.h</a></li>
<li><a href="#trunkSourcebmallocbmallocHeapcpp">trunk/Source/bmalloc/bmalloc/Heap.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocHeaph">trunk/Source/bmalloc/bmalloc/Heap.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSizesh">trunk/Source/bmalloc/bmalloc/Sizes.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourcebmallocChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/ChangeLog (191195 => 191196)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/ChangeLog 2015-10-16 19:53:04 UTC (rev 191195)
+++ trunk/Source/bmalloc/ChangeLog 2015-10-16 19:59:30 UTC (rev 191196)
</span><span class="lines">@@ -1,3 +1,41 @@
</span><ins>+2015-10-15 Geoffrey Garen <ggaren@apple.com>
+
+ bmalloc: per-thread cache data structure should be smaller
+ https://bugs.webkit.org/show_bug.cgi?id=150218
+
+ Reviewed by Andreas Kling.
+
+ Reduce the number of entries in the range cache because it's really
+ big, and the bigness only helps in cases of serious fragmentation, and
+ it only saves us a little bit of lock acquisition time.
+
+ * bmalloc/Allocator.cpp:
+ (bmalloc::Allocator::scavenge):
+ (bmalloc::Allocator::refillAllocatorSlowCase):
+ (bmalloc::Allocator::refillAllocator):
+ (bmalloc::Allocator::allocateLarge):
+ (bmalloc::Allocator::allocateSlowCase):
+ (bmalloc::Allocator::allocateBumpRangeSlowCase): Deleted.
+ (bmalloc::Allocator::allocateBumpRange): Deleted.
+ * bmalloc/Allocator.h: Pass through the empty allocator and the range
+ cache when refilling, and refill both. Otherwise, we always immediately
+ pop the last item in the range cache, wasting that slot of capacity.
+
+ * bmalloc/Heap.cpp:
+ (bmalloc::Heap::allocateSmallBumpRanges):
+ (bmalloc::Heap::allocateMediumBumpRanges): Account for the fact that
+ the range cache is no longer big enough to guarantee that it can hold
+ all the ranges in a page.
+
+ (bmalloc::Heap::refillSmallBumpRangeCache): Deleted.
+ (bmalloc::Heap::refillMediumBumpRangeCache): Deleted.
+
+ * bmalloc/Heap.h: Move VMHeap to the end of the object because it
+ contains a lot of unused / wasted space, and we want to pack our data
+ together in memory.
+
+ * bmalloc/Sizes.h: Make the range cache smaller.
+
</ins><span class="cx"> 2015-10-13 Chris Dumez <cdumez@apple.com>
</span><span class="cx">
</span><span class="cx"> Avoid useless copies in range-loops that are using 'auto'
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocAllocatorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Allocator.cpp (191195 => 191196)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Allocator.cpp 2015-10-16 19:53:04 UTC (rev 191195)
+++ trunk/Source/bmalloc/bmalloc/Allocator.cpp 2015-10-16 19:59:30 UTC (rev 191196)
</span><span class="lines">@@ -203,25 +203,23 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-NO_INLINE BumpRange Allocator::allocateBumpRangeSlowCase(size_t sizeClass)
</del><ins>+NO_INLINE void Allocator::refillAllocatorSlowCase(BumpAllocator& allocator, size_t sizeClass)
</ins><span class="cx"> {
</span><span class="cx"> BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
</span><span class="cx">
</span><span class="cx"> std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
</span><span class="cx"> if (sizeClass <= bmalloc::sizeClass(smallMax))
</span><del>- PerProcess<Heap>::getFastCase()->refillSmallBumpRangeCache(lock, sizeClass, bumpRangeCache);
</del><ins>+ PerProcess<Heap>::getFastCase()->allocateSmallBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
</ins><span class="cx"> else
</span><del>- PerProcess<Heap>::getFastCase()->refillMediumBumpRangeCache(lock, sizeClass, bumpRangeCache);
-
- return bumpRangeCache.pop();
</del><ins>+ PerProcess<Heap>::getFastCase()->allocateMediumBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-INLINE BumpRange Allocator::allocateBumpRange(size_t sizeClass)
</del><ins>+INLINE void Allocator::refillAllocator(BumpAllocator& allocator, size_t sizeClass)
</ins><span class="cx"> {
</span><span class="cx"> BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
</span><span class="cx"> if (!bumpRangeCache.size())
</span><del>- return allocateBumpRangeSlowCase(sizeClass);
- return bumpRangeCache.pop();
</del><ins>+ return refillAllocatorSlowCase(allocator, sizeClass);
+ return allocator.refill(bumpRangeCache.pop());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> NO_INLINE void* Allocator::allocateLarge(size_t size)
</span><span class="lines">@@ -246,7 +244,7 @@
</span><span class="cx"> if (size <= mediumMax) {
</span><span class="cx"> size_t sizeClass = bmalloc::sizeClass(size);
</span><span class="cx"> BumpAllocator& allocator = m_bumpAllocators[sizeClass];
</span><del>- allocator.refill(allocateBumpRange(sizeClass));
</del><ins>+ refillAllocator(allocator, sizeClass);
</ins><span class="cx"> return allocator.allocate();
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocAllocatorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Allocator.h (191195 => 191196)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Allocator.h 2015-10-16 19:53:04 UTC (rev 191195)
+++ trunk/Source/bmalloc/bmalloc/Allocator.h 2015-10-16 19:59:30 UTC (rev 191196)
</span><span class="lines">@@ -56,8 +56,8 @@
</span><span class="cx"> void* allocateLarge(size_t);
</span><span class="cx"> void* allocateXLarge(size_t);
</span><span class="cx">
</span><del>- BumpRange allocateBumpRange(size_t sizeClass);
- BumpRange allocateBumpRangeSlowCase(size_t sizeClass);
</del><ins>+ void refillAllocator(BumpAllocator&, size_t sizeClass);
+ void refillAllocatorSlowCase(BumpAllocator&, size_t sizeClass);
</ins><span class="cx">
</span><span class="cx"> std::array<BumpAllocator, mediumMax / alignment> m_bumpAllocators;
</span><span class="cx"> std::array<BumpRangeCache, mediumMax / alignment> m_bumpRangeCaches;
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocHeapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Heap.cpp (191195 => 191196)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Heap.cpp 2015-10-16 19:53:04 UTC (rev 191195)
+++ trunk/Source/bmalloc/bmalloc/Heap.cpp 2015-10-16 19:59:30 UTC (rev 191196)
</span><span class="lines">@@ -24,6 +24,7 @@
</span><span class="cx"> */
</span><span class="cx">
</span><span class="cx"> #include "Heap.h"
</span><ins>+#include "BumpAllocator.h"
</ins><span class="cx"> #include "LargeChunk.h"
</span><span class="cx"> #include "LargeObject.h"
</span><span class="cx"> #include "Line.h"
</span><span class="lines">@@ -119,7 +120,7 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void Heap::refillSmallBumpRangeCache(std::lock_guard<StaticMutex>& lock, size_t sizeClass, BumpRangeCache& rangeCache)
</del><ins>+void Heap::allocateSmallBumpRanges(std::lock_guard<StaticMutex>& lock, size_t sizeClass, BumpAllocator& allocator, BumpRangeCache& rangeCache)
</ins><span class="cx"> {
</span><span class="cx"> BASSERT(!rangeCache.size());
</span><span class="cx"> SmallPage* page = allocateSmallPage(lock, sizeClass);
</span><span class="lines">@@ -135,6 +136,12 @@
</span><span class="cx"> if (lines[lineNumber].refCount(lock))
</span><span class="cx"> continue;
</span><span class="cx">
</span><ins>+ // In a fragmented page, some free ranges might not fit in the cache.
+ if (rangeCache.size() == rangeCache.capacity()) {
+ m_smallPagesWithFreeLines[sizeClass].push(page);
+ return;
+ }
+
</ins><span class="cx"> LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
</span><span class="cx"> char* begin = lines[lineNumber].begin() + lineMetadata.startOffset;
</span><span class="cx"> unsigned short objectCount = lineMetadata.objectCount;
</span><span class="lines">@@ -152,11 +159,14 @@
</span><span class="cx"> page->ref(lock);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- rangeCache.push({ begin, objectCount });
</del><ins>+ if (!allocator.canAllocate())
+ allocator.refill({ begin, objectCount });
+ else
+ rangeCache.push({ begin, objectCount });
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void Heap::refillMediumBumpRangeCache(std::lock_guard<StaticMutex>& lock, size_t sizeClass, BumpRangeCache& rangeCache)
</del><ins>+void Heap::allocateMediumBumpRanges(std::lock_guard<StaticMutex>& lock, size_t sizeClass, BumpAllocator& allocator, BumpRangeCache& rangeCache)
</ins><span class="cx"> {
</span><span class="cx"> MediumPage* page = allocateMediumPage(lock, sizeClass);
</span><span class="cx"> BASSERT(!rangeCache.size());
</span><span class="lines">@@ -172,6 +182,12 @@
</span><span class="cx"> if (lines[lineNumber].refCount(lock))
</span><span class="cx"> continue;
</span><span class="cx">
</span><ins>+ // In a fragmented page, some free ranges might not fit in the cache.
+ if (rangeCache.size() == rangeCache.capacity()) {
+ m_mediumPagesWithFreeLines[sizeClass].push(page);
+ return;
+ }
+
</ins><span class="cx"> LineMetadata& lineMetadata = m_mediumLineMetadata[sizeClass][lineNumber];
</span><span class="cx"> char* begin = lines[lineNumber].begin() + lineMetadata.startOffset;
</span><span class="cx"> unsigned short objectCount = lineMetadata.objectCount;
</span><span class="lines">@@ -189,7 +205,10 @@
</span><span class="cx"> page->ref(lock);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- rangeCache.push({ begin, objectCount });
</del><ins>+ if (!allocator.canAllocate())
+ allocator.refill({ begin, objectCount });
+ else
+ rangeCache.push({ begin, objectCount });
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocHeaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Heap.h (191195 => 191196)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Heap.h 2015-10-16 19:53:04 UTC (rev 191195)
+++ trunk/Source/bmalloc/bmalloc/Heap.h 2015-10-16 19:59:30 UTC (rev 191196)
</span><span class="lines">@@ -45,6 +45,7 @@
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><span class="cx"> class BeginTag;
</span><ins>+class BumpAllocator;
</ins><span class="cx"> class EndTag;
</span><span class="cx">
</span><span class="cx"> class Heap {
</span><span class="lines">@@ -53,10 +54,10 @@
</span><span class="cx">
</span><span class="cx"> Environment& environment() { return m_environment; }
</span><span class="cx">
</span><del>- void refillSmallBumpRangeCache(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpRangeCache&);
</del><ins>+ void allocateSmallBumpRanges(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpAllocator&, BumpRangeCache&);
</ins><span class="cx"> void derefSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
</span><span class="cx">
</span><del>- void refillMediumBumpRangeCache(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpRangeCache&);
</del><ins>+ void allocateMediumBumpRanges(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpAllocator&, BumpRangeCache&);
</ins><span class="cx"> void derefMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
</span><span class="cx">
</span><span class="cx"> void* allocateLarge(std::lock_guard<StaticMutex>&, size_t);
</span><span class="lines">@@ -108,11 +109,11 @@
</span><span class="cx"> Vector<Range> m_xLargeObjects;
</span><span class="cx">
</span><span class="cx"> bool m_isAllocatingPages;
</span><ins>+ AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
</ins><span class="cx">
</span><span class="cx"> Environment m_environment;
</span><span class="cx">
</span><span class="cx"> VMHeap m_vmHeap;
</span><del>- AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> inline void Heap::derefSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSizesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Sizes.h (191195 => 191196)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Sizes.h 2015-10-16 19:53:04 UTC (rev 191195)
+++ trunk/Source/bmalloc/bmalloc/Sizes.h 2015-10-16 19:59:30 UTC (rev 191196)
</span><span class="lines">@@ -93,7 +93,7 @@
</span><span class="cx"> static const uintptr_t smallOrMediumSmallTypeMask = smallType ^ mediumType; // Only valid if object is known to be small or medium.
</span><span class="cx">
</span><span class="cx"> static const size_t deallocatorLogCapacity = 256;
</span><del>- static const size_t bumpRangeCacheCapacity = vmPageSize / smallLineSize / 2;
</del><ins>+ static const size_t bumpRangeCacheCapacity = 3;
</ins><span class="cx">
</span><span class="cx"> static const std::chrono::milliseconds scavengeSleepDuration = std::chrono::milliseconds(512);
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>