<!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>[185663] trunk/Source/WTF</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/185663">185663</a></dd>
<dt>Author</dt> <dd>akling@apple.com</dd>
<dt>Date</dt> <dd>2015-06-17 13:27:22 -0700 (Wed, 17 Jun 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>SegmentedVector should waste less memory.
<https://webkit.org/b/146069>
Reviewed by Anders Carlsson.
We were wasting sizeof(Vector) on every segment in SegmentVector.
The segments were using inline capacity, and would never go beyond it,
so all the size/capacity/out-of-line-buffer metadata was useless.
Change the internal representation to Vector<T[SegmentSize]> instead.
This saves 16 bytes per segment, so lower SegmentSize -> bigger savings!
* wtf/SegmentedVector.h:
(WTF::SegmentedVectorIterator::operator*):
(WTF::SegmentedVectorIterator::operator->):
(WTF::SegmentedVectorIterator::operator++):
(WTF::SegmentedVectorIterator::operator==):
(WTF::SegmentedVectorIterator::operator!=):
(WTF::SegmentedVectorIterator::SegmentedVectorIterator):
(WTF::SegmentedVector::at):
(WTF::SegmentedVector::append):
(WTF::SegmentedVector::removeLast):
(WTF::SegmentedVector::grow):
(WTF::SegmentedVector::begin):
(WTF::SegmentedVector::end):
(WTF::SegmentedVector::deleteAllSegments):
(WTF::SegmentedVector::ensureSegmentsFor):
(WTF::SegmentedVector::ensureSegment):
(WTF::SegmentedVector::allocateSegment):
(WTF::SegmentedVectorIterator::operator=): Deleted.
(WTF::SegmentedVector::SegmentedVector): Deleted.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfSegmentedVectorh">trunk/Source/WTF/wtf/SegmentedVector.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (185662 => 185663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-06-17 20:03:13 UTC (rev 185662)
+++ trunk/Source/WTF/ChangeLog 2015-06-17 20:27:22 UTC (rev 185663)
</span><span class="lines">@@ -1,3 +1,37 @@
</span><ins>+2015-06-17 Andreas Kling <akling@apple.com>
+
+ SegmentedVector should waste less memory.
+ <https://webkit.org/b/146069>
+
+ Reviewed by Anders Carlsson.
+
+ We were wasting sizeof(Vector) on every segment in SegmentVector.
+ The segments were using inline capacity, and would never go beyond it,
+ so all the size/capacity/out-of-line-buffer metadata was useless.
+
+ Change the internal representation to Vector<T[SegmentSize]> instead.
+ This saves 16 bytes per segment, so lower SegmentSize -> bigger savings!
+
+ * wtf/SegmentedVector.h:
+ (WTF::SegmentedVectorIterator::operator*):
+ (WTF::SegmentedVectorIterator::operator->):
+ (WTF::SegmentedVectorIterator::operator++):
+ (WTF::SegmentedVectorIterator::operator==):
+ (WTF::SegmentedVectorIterator::operator!=):
+ (WTF::SegmentedVectorIterator::SegmentedVectorIterator):
+ (WTF::SegmentedVector::at):
+ (WTF::SegmentedVector::append):
+ (WTF::SegmentedVector::removeLast):
+ (WTF::SegmentedVector::grow):
+ (WTF::SegmentedVector::begin):
+ (WTF::SegmentedVector::end):
+ (WTF::SegmentedVector::deleteAllSegments):
+ (WTF::SegmentedVector::ensureSegmentsFor):
+ (WTF::SegmentedVector::ensureSegment):
+ (WTF::SegmentedVector::allocateSegment):
+ (WTF::SegmentedVectorIterator::operator=): Deleted.
+ (WTF::SegmentedVector::SegmentedVector): Deleted.
+
</ins><span class="cx"> 2015-06-16 Andreas Kling <akling@apple.com>
</span><span class="cx">
</span><span class="cx"> Remove unused template parameter InlineCapacity from SegmentedVector.
</span></span></pre></div>
<a id="trunkSourceWTFwtfSegmentedVectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/SegmentedVector.h (185662 => 185663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/SegmentedVector.h 2015-06-17 20:03:13 UTC (rev 185662)
+++ trunk/Source/WTF/wtf/SegmentedVector.h 2015-06-17 20:27:22 UTC (rev 185663)
</span><span class="lines">@@ -44,56 +44,41 @@
</span><span class="cx">
</span><span class="cx"> ~SegmentedVectorIterator() { }
</span><span class="cx">
</span><del>- T& operator*() const { return m_vector.m_segments.at(m_segment)->at(m_index); }
- T* operator->() const { return &m_vector.m_segments.at(m_segment)->at(m_index); }
</del><ins>+ T& operator*() const { return m_vector.at(m_index); }
+ T* operator->() const { return &m_vector.at(m_index); }
</ins><span class="cx">
</span><span class="cx"> // Only prefix ++ operator supported
</span><span class="cx"> Iterator& operator++()
</span><span class="cx"> {
</span><del>- ASSERT(m_index != SegmentSize);
- ++m_index;
- if (m_index >= m_vector.m_segments.at(m_segment)->size()) {
- if (m_segment + 1 < m_vector.m_segments.size()) {
- ASSERT(m_vector.m_segments.at(m_segment)->size() > 0);
- ++m_segment;
- m_index = 0;
- } else {
- // Points to the "end" symbol
- m_segment = 0;
- m_index = SegmentSize;
- }
- }
</del><ins>+ m_index++;
</ins><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool operator==(const Iterator& other) const
</span><span class="cx"> {
</span><del>- return m_index == other.m_index && m_segment == other.m_segment && &m_vector == &other.m_vector;
</del><ins>+ return m_index == other.m_index && &m_vector == &other.m_vector;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool operator!=(const Iterator& other) const
</span><span class="cx"> {
</span><del>- return m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector;
</del><ins>+ return m_index != other.m_index || &m_vector != &other.m_vector;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other)
</span><span class="cx"> {
</span><span class="cx"> m_vector = other.m_vector;
</span><del>- m_segment = other.m_segment;
</del><span class="cx"> m_index = other.m_index;
</span><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t segment, size_t index)
</del><ins>+ SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t index)
</ins><span class="cx"> : m_vector(vector)
</span><del>- , m_segment(segment)
</del><span class="cx"> , m_index(index)
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> SegmentedVector<T, SegmentSize>& m_vector;
</span><del>- size_t m_segment;
</del><span class="cx"> size_t m_index;
</span><span class="cx"> };
</span><span class="cx">
</span><span class="lines">@@ -110,10 +95,7 @@
</span><span class="cx"> public:
</span><span class="cx"> typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
</span><span class="cx">
</span><del>- SegmentedVector()
- : m_size(0)
- {
- }
</del><ins>+ SegmentedVector() = default;
</ins><span class="cx">
</span><span class="cx"> ~SegmentedVector()
</span><span class="cx"> {
</span><span class="lines">@@ -125,7 +107,8 @@
</span><span class="cx">
</span><span class="cx"> T& at(size_t index)
</span><span class="cx"> {
</span><del>- return segmentFor(index)->at(subscriptFor(index));
</del><ins>+ ASSERT_WITH_SECURITY_IMPLICATION(index < m_size);
+ return segmentFor(index)->entries[subscriptFor(index)];
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> const T& at(size_t index) const
</span><span class="lines">@@ -151,10 +134,9 @@
</span><span class="cx"> template <typename U> void append(U&& value)
</span><span class="cx"> {
</span><span class="cx"> ++m_size;
</span><del>-
</del><span class="cx"> if (!segmentExistsFor(m_size - 1))
</span><del>- m_segments.append(new Segment);
- segmentFor(m_size - 1)->uncheckedAppend(std::forward<U>(value));
</del><ins>+ allocateSegment();
+ new (NotNull, &last()) T(std::forward<U>(value));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename... Args>
</span><span class="lines">@@ -166,7 +148,7 @@
</span><span class="cx">
</span><span class="cx"> void removeLast()
</span><span class="cx"> {
</span><del>- segmentFor(m_size - 1)->removeLast();
</del><ins>+ last().~T();
</ins><span class="cx"> --m_size;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -174,7 +156,10 @@
</span><span class="cx"> {
</span><span class="cx"> ASSERT(size > m_size);
</span><span class="cx"> ensureSegmentsFor(size);
</span><ins>+ size_t oldSize = m_size;
</ins><span class="cx"> m_size = size;
</span><ins>+ for (size_t i = oldSize; i < m_size; ++i)
+ new (NotNull, &at(i)) T();
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void clear()
</span><span class="lines">@@ -186,12 +171,12 @@
</span><span class="cx">
</span><span class="cx"> Iterator begin()
</span><span class="cx"> {
</span><del>- return Iterator(*this, 0, m_size ? 0 : SegmentSize);
</del><ins>+ return Iterator(*this, 0);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Iterator end()
</span><span class="cx"> {
</span><del>- return Iterator(*this, 0, SegmentSize);
</del><ins>+ return Iterator(*this, m_size);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void shrinkToFit()
</span><span class="lines">@@ -200,12 +185,16 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- typedef Vector<T, SegmentSize> Segment;
</del><ins>+ struct Segment {
+ T entries[0];
+ };
</ins><span class="cx">
</span><span class="cx"> void deleteAllSegments()
</span><span class="cx"> {
</span><del>- for (size_t i = 0; i < m_segments.size(); i++)
- delete m_segments[i];
</del><ins>+ for (size_t i = 0; i < m_size; ++i)
+ at(i).~T();
+ for (size_t i = 0; i < m_segments.size(); ++i)
+ fastFree(m_segments[i]);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool segmentExistsFor(size_t index)
</span><span class="lines">@@ -228,24 +217,23 @@
</span><span class="cx"> size_t segmentCount = (m_size + SegmentSize - 1) / SegmentSize;
</span><span class="cx"> size_t neededSegmentCount = (size + SegmentSize - 1) / SegmentSize;
</span><span class="cx">
</span><del>- // Fill up to N - 1 segments.
- size_t end = neededSegmentCount - 1;
- for (size_t i = segmentCount ? segmentCount - 1 : 0; i < end; ++i)
- ensureSegment(i, SegmentSize);
-
- // Grow segment N to accomodate the remainder.
- ensureSegment(end, subscriptFor(size - 1) + 1);
</del><ins>+ for (size_t i = segmentCount ? segmentCount - 1 : 0; i < neededSegmentCount; ++i)
+ ensureSegment(i);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void ensureSegment(size_t segmentIndex, size_t size)
</del><ins>+ void ensureSegment(size_t segmentIndex)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
</span><span class="cx"> if (segmentIndex == m_segments.size())
</span><del>- m_segments.append(new Segment);
- m_segments[segmentIndex]->grow(size);
</del><ins>+ allocateSegment();
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- size_t m_size;
</del><ins>+ void allocateSegment()
+ {
+ m_segments.append(static_cast<Segment*>(fastMalloc(sizeof(T) * SegmentSize)));
+ }
+
+ size_t m_size { 0 };
</ins><span class="cx"> Vector<Segment*> m_segments;
</span><span class="cx"> };
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>