<!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>[180926] releases/WebKitGTK/webkit-2.8/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/180926">180926</a></dd>
<dt>Author</dt> <dd>carlosgc@webkit.org</dd>
<dt>Date</dt> <dd>2015-03-03 00:55:14 -0800 (Tue, 03 Mar 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Merge <a href="http://trac.webkit.org/projects/webkit/changeset/180908">r180908</a> - bmalloc: Eagerly remove allocated objects from the free list
https://bugs.webkit.org/show_bug.cgi?id=142194
Reviewed by Andreas Kling.
This reduces the pressure to garbage collect the free list.
Might be a 1% speedup on MallocBench.
* bmalloc/FreeList.cpp: Put this comment at the top of the file instead
of repeating it inside of each function. Tried to clarify the details.
(bmalloc::FreeList::takeGreedy): Matched the other iteration code in this
file for consistency -- even though either direction works fine in this
function.
(bmalloc::FreeList::take): Change to iterate from low to high so that we
can maintain an index into the vector that is not disturbed even if we
pop from the middle (which invalidates the last index in the vector).
Decrement i when popping from the middle to make sure that we don't
skip the next item after popping.
(bmalloc::FreeList::removeInvalidAndDuplicateEntries): Ditto.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#releasesWebKitGTKwebkit28SourcebmallocChangeLog">releases/WebKitGTK/webkit-2.8/Source/bmalloc/ChangeLog</a></li>
<li><a href="#releasesWebKitGTKwebkit28SourcebmallocbmallocFreeListcpp">releases/WebKitGTK/webkit-2.8/Source/bmalloc/bmalloc/FreeList.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="releasesWebKitGTKwebkit28SourcebmallocChangeLog"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.8/Source/bmalloc/ChangeLog (180925 => 180926)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/Source/bmalloc/ChangeLog 2015-03-03 08:47:17 UTC (rev 180925)
+++ releases/WebKitGTK/webkit-2.8/Source/bmalloc/ChangeLog 2015-03-03 08:55:14 UTC (rev 180926)
</span><span class="lines">@@ -1,3 +1,30 @@
</span><ins>+2015-03-02 Geoffrey Garen <ggaren@apple.com>
+
+ bmalloc: Eagerly remove allocated objects from the free list
+ https://bugs.webkit.org/show_bug.cgi?id=142194
+
+ Reviewed by Andreas Kling.
+
+ This reduces the pressure to garbage collect the free list.
+
+ Might be a 1% speedup on MallocBench.
+
+ * bmalloc/FreeList.cpp: Put this comment at the top of the file instead
+ of repeating it inside of each function. Tried to clarify the details.
+
+ (bmalloc::FreeList::takeGreedy): Matched the other iteration code in this
+ file for consistency -- even though either direction works fine in this
+ function.
+
+ (bmalloc::FreeList::take): Change to iterate from low to high so that we
+ can maintain an index into the vector that is not disturbed even if we
+ pop from the middle (which invalidates the last index in the vector).
+
+ Decrement i when popping from the middle to make sure that we don't
+ skip the next item after popping.
+
+ (bmalloc::FreeList::removeInvalidAndDuplicateEntries): Ditto.
+
</ins><span class="cx"> 2015-02-27 Ryosuke Niwa <rniwa@webkit.org>
</span><span class="cx">
</span><span class="cx"> Fixed a typo in the previous commit.
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit28SourcebmallocbmallocFreeListcpp"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.8/Source/bmalloc/bmalloc/FreeList.cpp (180925 => 180926)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/Source/bmalloc/bmalloc/FreeList.cpp 2015-03-03 08:47:17 UTC (rev 180925)
+++ releases/WebKitGTK/webkit-2.8/Source/bmalloc/bmalloc/FreeList.cpp 2015-03-03 08:55:14 UTC (rev 180926)
</span><span class="lines">@@ -29,18 +29,24 @@
</span><span class="cx">
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><ins>+// We don't eagerly remove invalidated entries from the free list when we merge
+// large objects. This means that the free list can contain invalid and/or
+// duplicate entries. (Repeating a merge-and-then-split produces a duplicate.)
+
+// To avoid infinite growth in invalid entries, we incrementally remove
+// invalid entries as we discover them during allocation, and we also garbage
+// collect the free list as it grows.
+
</ins><span class="cx"> LargeObject FreeList::takeGreedy(Owner owner)
</span><span class="cx"> {
</span><del>- for (size_t i = m_vector.size(); i-- > 0; ) {
- // We don't eagerly remove items when we merge and/or split ranges,
- // so we need to validate each free list entry before using it.
</del><ins>+ for (size_t i = 0; i < m_vector.size(); ++i) {
</ins><span class="cx"> LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
</span><span class="cx"> if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
</span><del>- m_vector.pop(i);
</del><ins>+ m_vector.pop(i--);
</ins><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- m_vector.pop(i);
</del><ins>+ m_vector.pop(i--);
</ins><span class="cx"> return largeObject;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -49,27 +55,29 @@
</span><span class="cx">
</span><span class="cx"> LargeObject FreeList::take(Owner owner, size_t size)
</span><span class="cx"> {
</span><del>- LargeObject first;
- size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
- for (size_t i = m_vector.size(); i-- > end; ) {
- // We don't eagerly remove items when we merge and/or split ranges, so
- // we need to validate each free list entry before using it.
</del><ins>+ LargeObject candidate;
+ size_t candidateIndex;
+ size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
+ for (size_t i = begin; i < m_vector.size(); ++i) {
</ins><span class="cx"> LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
</span><span class="cx"> if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
</span><del>- m_vector.pop(i);
</del><ins>+ m_vector.pop(i--);
</ins><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (largeObject.size() < size)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- if (!!first && first.begin() < largeObject.begin())
</del><ins>+ if (!!candidate && candidate.begin() < largeObject.begin())
</ins><span class="cx"> continue;
</span><span class="cx">
</span><del>- first = largeObject;
</del><ins>+ candidate = largeObject;
+ candidateIndex = i;
</ins><span class="cx"> }
</span><del>-
- return first;
</del><ins>+
+ if (!!candidate)
+ m_vector.pop(candidateIndex);
+ return candidate;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> LargeObject FreeList::take(Owner owner, size_t alignment, size_t size, size_t unalignedSize)
</span><span class="lines">@@ -77,14 +85,13 @@
</span><span class="cx"> BASSERT(isPowerOfTwo(alignment));
</span><span class="cx"> size_t alignmentMask = alignment - 1;
</span><span class="cx">
</span><del>- LargeObject first;
- size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
- for (size_t i = m_vector.size(); i-- > end; ) {
- // We don't eagerly remove items when we merge and/or split ranges, so
- // we need to validate each free list entry before using it.
</del><ins>+ LargeObject candidate;
+ size_t candidateIndex;
+ size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
+ for (size_t i = begin; i < m_vector.size(); ++i) {
</ins><span class="cx"> LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
</span><span class="cx"> if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
</span><del>- m_vector.pop(i);
</del><ins>+ m_vector.pop(i--);
</ins><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -94,31 +101,34 @@
</span><span class="cx"> if (test(largeObject.begin(), alignmentMask) && largeObject.size() < unalignedSize)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- if (!!first && first.begin() < largeObject.begin())
</del><ins>+ if (!!candidate && candidate.begin() < largeObject.begin())
</ins><span class="cx"> continue;
</span><span class="cx">
</span><del>- first = largeObject;
</del><ins>+ candidate = largeObject;
+ candidateIndex = i;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- return first;
</del><ins>+ if (!!candidate)
+ m_vector.pop(candidateIndex);
+ return candidate;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void FreeList::removeInvalidAndDuplicateEntries(Owner owner)
</span><span class="cx"> {
</span><del>- for (size_t i = m_vector.size(); i-- > 0; ) {
</del><ins>+ for (size_t i = 0; i < m_vector.size(); ++i) {
</ins><span class="cx"> LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
</span><span class="cx"> if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
</span><del>- m_vector.pop(i);
</del><ins>+ m_vector.pop(i--);
</ins><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> largeObject.setMarked(false);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- for (size_t i = m_vector.size(); i-- > 0; ) {
</del><ins>+ for (size_t i = 0; i < m_vector.size(); ++i) {
</ins><span class="cx"> LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
</span><span class="cx"> if (largeObject.isMarked()) {
</span><del>- m_vector.pop(i);
</del><ins>+ m_vector.pop(i--);
</ins><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>