<!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>[198375] trunk/Source</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/198375">198375</a></dd>
<dt>Author</dt> <dd>sbarati@apple.com</dd>
<dt>Date</dt> <dd>2016-03-17 19:11:31 -0700 (Thu, 17 Mar 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>Implement SmallPtrSet and integrate it into the Parser
https://bugs.webkit.org/show_bug.cgi?id=155552
Reviewed by Filip Pizlo.
Source/JavaScriptCore:
Using SmallPtrSet instead of HashSet really helps speed
up the parser. What saves us most is not needing to always
malloc/free memory in the HashSet.
* parser/Parser.cpp:
(JSC::Parser<LexerType>::parseInner):
* parser/Parser.h:
(JSC::Scope::Scope):
(JSC::Scope::startSwitch):
(JSC::Scope::endSwitch):
(JSC::Scope::startLoop):
(JSC::Scope::hasDeclaredParameter):
(JSC::Scope::declareWrite):
(JSC::Scope::declareParameter):
(JSC::Scope::usedVariablesContains):
(JSC::Scope::useVariable):
(JSC::Scope::collectFreeVariables):
(JSC::Scope::getCapturedVars):
(JSC::Scope::isValidStrictMode):
(JSC::Scope::shadowsArguments):
(JSC::Scope::copyCapturedVariablesToVector):
(JSC::Scope::setIsModule):
(JSC::Parser::pushScope):
(JSC::Scope::getUsedVariables): Deleted.
Source/WTF:
This patch implements the SmallPtrSet data struture.
Inspired by the implementation in llvm:
http://llvm.org/docs/doxygen/html/SmallPtrSet_8h_source.html
The data structure uses an inline array for storage up until
a fixed limit (8 entries in our implementation). If that storage
fills up, we fall back to a simple hash table implementation.
Crucially, this implementation doesn't support the remove
operation. This is on purpose. The hash table will only ever
grow.
Also, the implementation allows for it to be memcopied around.
I.e, we can put SmallPtrSet inside a Vector and allow that
Vector to use memcpy as its move operation (of course this
is only valid if the SmallPtrSet in the old memory doesn't have
its destructor called unless it is set back to its initial state.)
For now, SmallPtrSet only supports pointer types that are trivially
destructible. It's probably not too difficult to extend this to
smart pointers, but it's not part of this original implementation.
I've also implemented a pure forwarding varargs constructAndAppend
method on Vector. This allows you to do:
Vector<T> v;
v.constructAndAppend(a1, a2, ...)
as long as T has a constructor that accepts arguments (a1, a2, ...).
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/SmallPtrSet.h: Added.
(WTF::SmallPtrSet::SmallPtrSet):
(WTF::SmallPtrSet::operator=):
(WTF::SmallPtrSet::~SmallPtrSet):
(WTF::SmallPtrSet::add):
(WTF::SmallPtrSet::contains):
(WTF::SmallPtrSet::iterator::operator++):
(WTF::SmallPtrSet::iterator::operator*):
(WTF::SmallPtrSet::iterator::operator==):
(WTF::SmallPtrSet::iterator::operator!=):
(WTF::SmallPtrSet::begin):
(WTF::SmallPtrSet::end):
(WTF::SmallPtrSet::size):
(WTF::SmallPtrSet::emptyValue):
(WTF::SmallPtrSet::isValidEntry):
(WTF::SmallPtrSet::isSmall):
(WTF::SmallPtrSet::initialize):
(WTF::SmallPtrSet::grow):
(WTF::SmallPtrSet::bucket):
* wtf/Vector.h:
(WTF::Vector::append):
(WTF::Vector::uncheckedAppend):
(WTF::minCapacity>::append):
(WTF::minCapacity>::constructAndAppend):
(WTF::minCapacity>::appendSlowCase):
(WTF::minCapacity>::constructAndAppendSlowCase):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreparserParsercpp">trunk/Source/JavaScriptCore/parser/Parser.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreparserParserh">trunk/Source/JavaScriptCore/parser/Parser.h</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
<li><a href="#trunkSourceWTFwtfVectorh">trunk/Source/WTF/wtf/Vector.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfSmallPtrSeth">trunk/Source/WTF/wtf/SmallPtrSet.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (198374 => 198375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-03-18 02:11:31 UTC (rev 198375)
</span><span class="lines">@@ -1,3 +1,35 @@
</span><ins>+2016-03-17 Saam barati <sbarati@apple.com>
+
+ Implement SmallPtrSet and integrate it into the Parser
+ https://bugs.webkit.org/show_bug.cgi?id=155552
+
+ Reviewed by Filip Pizlo.
+
+ Using SmallPtrSet instead of HashSet really helps speed
+ up the parser. What saves us most is not needing to always
+ malloc/free memory in the HashSet.
+
+ * parser/Parser.cpp:
+ (JSC::Parser<LexerType>::parseInner):
+ * parser/Parser.h:
+ (JSC::Scope::Scope):
+ (JSC::Scope::startSwitch):
+ (JSC::Scope::endSwitch):
+ (JSC::Scope::startLoop):
+ (JSC::Scope::hasDeclaredParameter):
+ (JSC::Scope::declareWrite):
+ (JSC::Scope::declareParameter):
+ (JSC::Scope::usedVariablesContains):
+ (JSC::Scope::useVariable):
+ (JSC::Scope::collectFreeVariables):
+ (JSC::Scope::getCapturedVars):
+ (JSC::Scope::isValidStrictMode):
+ (JSC::Scope::shadowsArguments):
+ (JSC::Scope::copyCapturedVariablesToVector):
+ (JSC::Scope::setIsModule):
+ (JSC::Parser::pushScope):
+ (JSC::Scope::getUsedVariables): Deleted.
+
</ins><span class="cx"> 2016-03-17 Brian Burg <bburg@apple.com>
</span><span class="cx">
</span><span class="cx"> Web Inspector: protocol generator shouldn't generate enums for parameters with non-anonymous enum types
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreparserParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/parser/Parser.cpp (198374 => 198375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/parser/Parser.cpp 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/JavaScriptCore/parser/Parser.cpp 2016-03-18 02:11:31 UTC (rev 198375)
</span><span class="lines">@@ -311,10 +311,8 @@
</span><span class="cx"> for (auto& entry : capturedVariables)
</span><span class="cx"> varDeclarations.markVariableAsCaptured(entry);
</span><span class="cx">
</span><del>- IdentifierSet usedVariables;
- scope->getUsedVariables(usedVariables);
</del><span class="cx"> if (parseMode == SourceParseMode::GeneratorWrapperFunctionMode) {
</span><del>- if (usedVariables.contains(m_vm->propertyNames->arguments.impl()))
</del><ins>+ if (scope->usedVariablesContains(m_vm->propertyNames->arguments.impl()))
</ins><span class="cx"> context.propagateArgumentsUse();
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreparserParserh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/parser/Parser.h (198374 => 198375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/parser/Parser.h 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/JavaScriptCore/parser/Parser.h 2016-03-18 02:11:31 UTC (rev 198375)
</span><span class="lines">@@ -40,13 +40,15 @@
</span><span class="cx"> #include <wtf/Forward.h>
</span><span class="cx"> #include <wtf/Noncopyable.h>
</span><span class="cx"> #include <wtf/RefPtr.h>
</span><ins>+#include <wtf/SmallPtrSet.h>
+
</ins><span class="cx"> namespace JSC {
</span><span class="cx"> struct Scope;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span><del>-template <> struct VectorTraits<JSC::Scope> : SimpleClassVectorTraits {
- static const bool canInitializeWithMemset = false; // Not all Scope data members initialize to 0.
</del><ins>+template <> struct VectorTraits<JSC::Scope> : VectorTraitsBase</* is pod */ false, void> {
+ static const bool canMoveWithMemcpy = true;
</ins><span class="cx"> };
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -60,6 +62,8 @@
</span><span class="cx"> class ProgramNode;
</span><span class="cx"> class SourceCode;
</span><span class="cx">
</span><ins>+typedef SmallPtrSet<UniquedStringImpl*> UniquedStringImplPtrSet;
+
</ins><span class="cx"> // Macros to make the more common TreeBuilder types a little less verbose
</span><span class="cx"> #define TreeStatement typename TreeBuilder::Statement
</span><span class="cx"> #define TreeExpression typename TreeBuilder::Expression
</span><span class="lines">@@ -158,6 +162,9 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> struct Scope {
</span><ins>+ WTF_MAKE_NONCOPYABLE(Scope);
+
+public:
</ins><span class="cx"> Scope(const VM* vm, bool isFunction, bool isGenerator, bool strictMode, bool isArrowFunction)
</span><span class="cx"> : m_vm(vm)
</span><span class="cx"> , m_shadowsArguments(false)
</span><span class="lines">@@ -186,43 +193,6 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>- Scope(const Scope& rhs)
- : m_vm(rhs.m_vm)
- , m_shadowsArguments(rhs.m_shadowsArguments)
- , m_usesEval(rhs.m_usesEval)
- , m_needsFullActivation(rhs.m_needsFullActivation)
- , m_hasDirectSuper(rhs.m_hasDirectSuper)
- , m_needsSuperBinding(rhs.m_needsSuperBinding)
- , m_allowsVarDeclarations(rhs.m_allowsVarDeclarations)
- , m_allowsLexicalDeclarations(rhs.m_allowsLexicalDeclarations)
- , m_strictMode(rhs.m_strictMode)
- , m_isFunction(rhs.m_isFunction)
- , m_isGenerator(rhs.m_isGenerator)
- , m_isGeneratorBoundary(rhs.m_isGeneratorBoundary)
- , m_isArrowFunction(rhs.m_isArrowFunction)
- , m_isArrowFunctionBoundary(rhs.m_isArrowFunctionBoundary)
- , m_isLexicalScope(rhs.m_isLexicalScope)
- , m_isFunctionBoundary(rhs.m_isFunctionBoundary)
- , m_isValidStrictMode(rhs.m_isValidStrictMode)
- , m_hasArguments(rhs.m_hasArguments)
- , m_isEvalContext(rhs.m_isEvalContext)
- , m_constructorKind(rhs.m_constructorKind)
- , m_expectedSuperBinding(rhs.m_expectedSuperBinding)
- , m_loopDepth(rhs.m_loopDepth)
- , m_switchDepth(rhs.m_switchDepth)
- , m_innerArrowFunctionFeatures(rhs.m_innerArrowFunctionFeatures)
- , m_moduleScopeData(rhs.m_moduleScopeData)
- {
- if (rhs.m_labels) {
- m_labels = std::make_unique<LabelStack>();
-
- typedef LabelStack::const_iterator iterator;
- iterator end = rhs.m_labels->end();
- for (iterator it = rhs.m_labels->begin(); it != end; ++it)
- m_labels->append(ScopeLabelInfo { it->uid, it->isLoop });
- }
- }
-
</del><span class="cx"> void startSwitch() { m_switchDepth++; }
</span><span class="cx"> void endSwitch() { m_switchDepth--; }
</span><span class="cx"> void startLoop() { m_loopDepth++; }
</span><span class="lines">@@ -454,7 +424,7 @@
</span><span class="cx">
</span><span class="cx"> bool hasDeclaredParameter(const RefPtr<UniquedStringImpl>& ident)
</span><span class="cx"> {
</span><del>- return m_declaredParameters.contains(ident) || hasDeclaredVariable(ident);
</del><ins>+ return m_declaredParameters.contains(ident.get()) || hasDeclaredVariable(ident);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void declareWrite(const Identifier* ident)
</span><span class="lines">@@ -492,11 +462,7 @@
</span><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void getUsedVariables(IdentifierSet& usedVariables)
- {
- usedVariables.swap(m_usedVariables);
- }
-
</del><ins>+ bool usedVariablesContains(UniquedStringImpl* impl) const { return m_usedVariables.contains(impl); }
</ins><span class="cx"> void useVariable(const Identifier* ident, bool isEval)
</span><span class="cx"> {
</span><span class="cx"> m_usesEval |= isEval;
</span><span class="lines">@@ -548,7 +514,7 @@
</span><span class="cx"> m_usesEval = true;
</span><span class="cx">
</span><span class="cx"> {
</span><del>- for (const RefPtr<UniquedStringImpl>& impl : nestedScope->m_usedVariables) {
</del><ins>+ for (UniquedStringImpl* impl : nestedScope->m_usedVariables) {
</ins><span class="cx"> if (nestedScope->m_declaredVariables.contains(impl) || nestedScope->m_lexicalVariables.contains(impl))
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="lines">@@ -573,11 +539,10 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (nestedScope->m_writtenVariables.size()) {
</span><del>- IdentifierSet::iterator end = nestedScope->m_writtenVariables.end();
- for (IdentifierSet::iterator ptr = nestedScope->m_writtenVariables.begin(); ptr != end; ++ptr) {
- if (nestedScope->m_declaredVariables.contains(*ptr) || nestedScope->m_lexicalVariables.contains(*ptr))
</del><ins>+ for (UniquedStringImpl* impl : nestedScope->m_writtenVariables) {
+ if (nestedScope->m_declaredVariables.contains(impl) || nestedScope->m_lexicalVariables.contains(impl))
</ins><span class="cx"> continue;
</span><del>- m_writtenVariables.add(*ptr);
</del><ins>+ m_writtenVariables.add(impl);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -605,11 +570,10 @@
</span><span class="cx"> if (shadowsArguments())
</span><span class="cx"> modifiedArguments = true;
</span><span class="cx"> if (m_declaredParameters.size()) {
</span><del>- IdentifierSet::iterator end = m_writtenVariables.end();
- for (IdentifierSet::iterator ptr = m_writtenVariables.begin(); ptr != end; ++ptr) {
- if (*ptr == m_vm->propertyNames->arguments.impl())
</del><ins>+ for (UniquedStringImpl* impl : m_writtenVariables) {
+ if (impl == m_vm->propertyNames->arguments.impl())
</ins><span class="cx"> modifiedArguments = true;
</span><del>- if (!m_declaredParameters.contains(*ptr))
</del><ins>+ if (!m_declaredParameters.contains(impl))
</ins><span class="cx"> continue;
</span><span class="cx"> modifiedParameter = true;
</span><span class="cx"> break;
</span><span class="lines">@@ -621,13 +585,12 @@
</span><span class="cx"> bool isValidStrictMode() const { return m_isValidStrictMode; }
</span><span class="cx"> bool shadowsArguments() const { return m_shadowsArguments; }
</span><span class="cx">
</span><del>- void copyCapturedVariablesToVector(const IdentifierSet& capturedVariables, Vector<RefPtr<UniquedStringImpl>>& vector)
</del><ins>+ void copyCapturedVariablesToVector(const UniquedStringImplPtrSet& capturedVariables, Vector<RefPtr<UniquedStringImpl>>& vector)
</ins><span class="cx"> {
</span><del>- IdentifierSet::iterator end = capturedVariables.end();
- for (IdentifierSet::iterator it = capturedVariables.begin(); it != end; ++it) {
- if (m_declaredVariables.contains(*it) || m_lexicalVariables.contains(*it))
</del><ins>+ for (UniquedStringImpl* impl : capturedVariables) {
+ if (m_declaredVariables.contains(impl) || m_lexicalVariables.contains(impl))
</ins><span class="cx"> continue;
</span><del>- vector.append(*it);
</del><ins>+ vector.append(impl);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -694,40 +657,43 @@
</span><span class="cx"> m_moduleScopeData = ModuleScopeData::create();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // All the fields in Scope must be able to use memcpy as their
+ // move operation. If you add a field that violates this, make sure
+ // to remove this comment and update WTF::VectorTraits<JSC::Scope>.
</ins><span class="cx"> const VM* m_vm;
</span><del>- bool m_shadowsArguments : 1;
- bool m_usesEval : 1;
- bool m_needsFullActivation : 1;
- bool m_hasDirectSuper : 1;
- bool m_needsSuperBinding : 1;
- bool m_allowsVarDeclarations : 1;
- bool m_allowsLexicalDeclarations : 1;
- bool m_strictMode : 1;
- bool m_isFunction : 1;
- bool m_isGenerator : 1;
- bool m_isGeneratorBoundary : 1;
- bool m_isArrowFunction : 1;
- bool m_isArrowFunctionBoundary : 1;
- bool m_isLexicalScope : 1;
- bool m_isFunctionBoundary : 1;
- bool m_isValidStrictMode : 1;
- bool m_hasArguments : 1;
- bool m_isEvalContext : 1;
- unsigned m_constructorKind : 2;
- unsigned m_expectedSuperBinding : 2;
</del><ins>+ bool m_shadowsArguments;
+ bool m_usesEval;
+ bool m_needsFullActivation;
+ bool m_hasDirectSuper;
+ bool m_needsSuperBinding;
+ bool m_allowsVarDeclarations;
+ bool m_allowsLexicalDeclarations;
+ bool m_strictMode;
+ bool m_isFunction;
+ bool m_isGenerator;
+ bool m_isGeneratorBoundary;
+ bool m_isArrowFunction;
+ bool m_isArrowFunctionBoundary;
+ bool m_isLexicalScope;
+ bool m_isFunctionBoundary;
+ bool m_isValidStrictMode;
+ bool m_hasArguments;
+ bool m_isEvalContext;
+ unsigned m_constructorKind;
+ unsigned m_expectedSuperBinding;
</ins><span class="cx"> int m_loopDepth;
</span><span class="cx"> int m_switchDepth;
</span><span class="cx"> InnerArrowFunctionCodeFeatures m_innerArrowFunctionFeatures;
</span><span class="cx">
</span><span class="cx"> typedef Vector<ScopeLabelInfo, 2> LabelStack;
</span><span class="cx"> std::unique_ptr<LabelStack> m_labels;
</span><del>- IdentifierSet m_declaredParameters;
</del><ins>+ UniquedStringImplPtrSet m_declaredParameters;
</ins><span class="cx"> VariableEnvironment m_declaredVariables;
</span><span class="cx"> VariableEnvironment m_lexicalVariables;
</span><del>- IdentifierSet m_usedVariables;
</del><ins>+ UniquedStringImplPtrSet m_usedVariables;
</ins><span class="cx"> IdentifierSet m_closedVariableCandidates;
</span><del>- IdentifierSet m_writtenVariables;
- RefPtr<ModuleScopeData> m_moduleScopeData { };
</del><ins>+ UniquedStringImplPtrSet m_writtenVariables;
+ RefPtr<ModuleScopeData> m_moduleScopeData;
</ins><span class="cx"> DeclarationStacks::FunctionStack m_functionDeclarations;
</span><span class="cx"> };
</span><span class="cx">
</span><span class="lines">@@ -1004,7 +970,7 @@
</span><span class="cx"> isGenerator = m_scopeStack.last().isGenerator();
</span><span class="cx"> isArrowFunction = m_scopeStack.last().isArrowFunction();
</span><span class="cx"> }
</span><del>- m_scopeStack.append(Scope(m_vm, isFunction, isGenerator, isStrict, isArrowFunction));
</del><ins>+ m_scopeStack.constructAndAppend(m_vm, isFunction, isGenerator, isStrict, isArrowFunction);
</ins><span class="cx"> return currentScope();
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (198374 => 198375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/WTF/ChangeLog 2016-03-18 02:11:31 UTC (rev 198375)
</span><span class="lines">@@ -1,3 +1,66 @@
</span><ins>+2016-03-17 Saam barati <sbarati@apple.com>
+
+ Implement SmallPtrSet and integrate it into the Parser
+ https://bugs.webkit.org/show_bug.cgi?id=155552
+
+ Reviewed by Filip Pizlo.
+
+ This patch implements the SmallPtrSet data struture.
+ Inspired by the implementation in llvm:
+ http://llvm.org/docs/doxygen/html/SmallPtrSet_8h_source.html
+
+ The data structure uses an inline array for storage up until
+ a fixed limit (8 entries in our implementation). If that storage
+ fills up, we fall back to a simple hash table implementation.
+ Crucially, this implementation doesn't support the remove
+ operation. This is on purpose. The hash table will only ever
+ grow.
+
+ Also, the implementation allows for it to be memcopied around.
+ I.e, we can put SmallPtrSet inside a Vector and allow that
+ Vector to use memcpy as its move operation (of course this
+ is only valid if the SmallPtrSet in the old memory doesn't have
+ its destructor called unless it is set back to its initial state.)
+
+ For now, SmallPtrSet only supports pointer types that are trivially
+ destructible. It's probably not too difficult to extend this to
+ smart pointers, but it's not part of this original implementation.
+
+ I've also implemented a pure forwarding varargs constructAndAppend
+ method on Vector. This allows you to do:
+ Vector<T> v;
+ v.constructAndAppend(a1, a2, ...)
+ as long as T has a constructor that accepts arguments (a1, a2, ...).
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/SmallPtrSet.h: Added.
+ (WTF::SmallPtrSet::SmallPtrSet):
+ (WTF::SmallPtrSet::operator=):
+ (WTF::SmallPtrSet::~SmallPtrSet):
+ (WTF::SmallPtrSet::add):
+ (WTF::SmallPtrSet::contains):
+ (WTF::SmallPtrSet::iterator::operator++):
+ (WTF::SmallPtrSet::iterator::operator*):
+ (WTF::SmallPtrSet::iterator::operator==):
+ (WTF::SmallPtrSet::iterator::operator!=):
+ (WTF::SmallPtrSet::begin):
+ (WTF::SmallPtrSet::end):
+ (WTF::SmallPtrSet::size):
+ (WTF::SmallPtrSet::emptyValue):
+ (WTF::SmallPtrSet::isValidEntry):
+ (WTF::SmallPtrSet::isSmall):
+ (WTF::SmallPtrSet::initialize):
+ (WTF::SmallPtrSet::grow):
+ (WTF::SmallPtrSet::bucket):
+ * wtf/Vector.h:
+ (WTF::Vector::append):
+ (WTF::Vector::uncheckedAppend):
+ (WTF::minCapacity>::append):
+ (WTF::minCapacity>::constructAndAppend):
+ (WTF::minCapacity>::appendSlowCase):
+ (WTF::minCapacity>::constructAndAppendSlowCase):
+
</ins><span class="cx"> 2016-03-16 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Replace all of the various non-working and non-compiling sampling profiler hacks with a single super hack
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (198374 => 198375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-03-18 02:11:31 UTC (rev 198375)
</span><span class="lines">@@ -106,6 +106,7 @@
</span><span class="cx"> 70ECA60D1B02426800449739 /* AtomicStringImpl.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 70ECA60A1B02426800449739 /* AtomicStringImpl.cpp */; };
</span><span class="cx"> 70ECA60E1B02426800449739 /* SymbolImpl.h in Headers */ = {isa = PBXBuildFile; fileRef = 70ECA60B1B02426800449739 /* SymbolImpl.h */; };
</span><span class="cx"> 70ECA60F1B02426800449739 /* UniquedStringImpl.h in Headers */ = {isa = PBXBuildFile; fileRef = 70ECA60C1B02426800449739 /* UniquedStringImpl.h */; };
</span><ins>+ 79EC70611C99F9BC003A3AE2 /* SmallPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */; };
</ins><span class="cx"> 7CBBA07419BB7FDC00BBF025 /* OSObjectPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = 7CBBA07319BB7FDC00BBF025 /* OSObjectPtr.h */; };
</span><span class="cx"> 7CDD7FF8186D291E007433CD /* IteratorAdaptors.h in Headers */ = {isa = PBXBuildFile; fileRef = 7CDD7FF7186D291E007433CD /* IteratorAdaptors.h */; };
</span><span class="cx"> 7CDD7FFA186D2A54007433CD /* IteratorRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 7CDD7FF9186D2A54007433CD /* IteratorRange.h */; };
</span><span class="lines">@@ -421,6 +422,7 @@
</span><span class="cx"> 70ECA60A1B02426800449739 /* AtomicStringImpl.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringImpl.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 70ECA60B1B02426800449739 /* SymbolImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SymbolImpl.h; sourceTree = "<group>"; };
</span><span class="cx"> 70ECA60C1B02426800449739 /* UniquedStringImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniquedStringImpl.h; sourceTree = "<group>"; };
</span><ins>+ 7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SmallPtrSet.h; sourceTree = "<group>"; };
</ins><span class="cx"> 7CBBA07319BB7FDC00BBF025 /* OSObjectPtr.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = OSObjectPtr.h; sourceTree = "<group>"; };
</span><span class="cx"> 7CDD7FF7186D291E007433CD /* IteratorAdaptors.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IteratorAdaptors.h; sourceTree = "<group>"; };
</span><span class="cx"> 7CDD7FF9186D2A54007433CD /* IteratorRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IteratorRange.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -914,6 +916,7 @@
</span><span class="cx"> A748744F17A0BDAE00FA04CB /* SixCharacterHash.cpp */,
</span><span class="cx"> A748745017A0BDAE00FA04CB /* SixCharacterHash.h */,
</span><span class="cx"> A8A4730C151A825B004123FF /* SizeLimits.cpp */,
</span><ins>+ 7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
</ins><span class="cx"> A8A4730D151A825B004123FF /* Spectrum.h */,
</span><span class="cx"> A8A4730E151A825B004123FF /* StackBounds.cpp */,
</span><span class="cx"> A8A4730F151A825B004123FF /* StackBounds.h */,
</span><span class="lines">@@ -1150,6 +1153,7 @@
</span><span class="cx"> A8A47395151A825B004123FF /* CheckedBoolean.h in Headers */,
</span><span class="cx"> A8A4745F151A825B004123FF /* Collator.h in Headers */,
</span><span class="cx"> 0FC4EDE61696149600F65041 /* CommaPrinter.h in Headers */,
</span><ins>+ 79EC70611C99F9BC003A3AE2 /* SmallPtrSet.h in Headers */,
</ins><span class="cx"> DE5A09FC1BA36992003D4424 /* CommonCryptoSPI.h in Headers */,
</span><span class="cx"> 0F8F2B91172E00FC007DBDA5 /* CompilationThread.h in Headers */,
</span><span class="cx"> A8A47398151A825B004123FF /* Compiler.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (198374 => 198375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-03-18 02:11:31 UTC (rev 198375)
</span><span class="lines">@@ -94,6 +94,7 @@
</span><span class="cx"> SaturatedArithmetic.h
</span><span class="cx"> ScopedLambda.h
</span><span class="cx"> SegmentedVector.h
</span><ins>+ SmallPtrSet.h
</ins><span class="cx"> StackBounds.h
</span><span class="cx"> StackStats.h
</span><span class="cx"> StaticConstructors.h
</span></span></pre></div>
<a id="trunkSourceWTFwtfSmallPtrSeth"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/SmallPtrSet.h (0 => 198375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/SmallPtrSet.h (rev 0)
+++ trunk/Source/WTF/wtf/SmallPtrSet.h 2016-03-18 02:11:31 UTC (rev 198375)
</span><span class="lines">@@ -0,0 +1,253 @@
</span><ins>+/*
+ * 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 SmallPtrSet_h
+#define SmallPtrSet_h
+
+#include <wtf/Assertions.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/HashFunctions.h>
+#include <wtf/Noncopyable.h>
+
+namespace WTF {
+
+template<typename PtrType>
+class SmallPtrSet {
+ WTF_MAKE_NONCOPYABLE(SmallPtrSet);
+ static_assert(std::is_trivially_destructible<PtrType>::value, "We currently don't support non-trivially destructible pointer types.");
+ static_assert(sizeof(PtrType) == sizeof(void*), "Only support pointer sized things.");
+
+public:
+ SmallPtrSet()
+ {
+ initialize();
+ }
+
+ // We take care to have SmallPtrSet have partial move semantics allowable through
+ // memcpy. It's partial move semantics because our destructor should not be called
+ // on the SmallPtrObject in the old memory we were moved from (otherwise, we might free m_buffer twice)
+ // unless that old memory is reset to be isSmall(). See move constructor below.
+ // To maintain these semantics, we determine if we're small by checking our size
+ // and not our m_buffer pointer. And when we're small, we don't do operations on
+ // m_buffer, instead, we perform operations on m_smallStorage directly. The reason we want
+ // these semantics is that it's beneficial to have a Vector that contains SmallPtrSet
+ // (or an object with SmallPtrSet as a field) be allowed to use memcpy for its move operation.
+
+ SmallPtrSet(SmallPtrSet&& other)
+ {
+ *this = WTFMove(other);
+ }
+
+ SmallPtrSet& operator=(SmallPtrSet&& other)
+ {
+ memcpy(this, &other, sizeof(SmallPtrSet));
+ other.initialize();
+ return *this;
+ }
+
+ ~SmallPtrSet()
+ {
+ if (!isSmall())
+ fastFree(m_buffer);
+ }
+
+ inline void add(PtrType ptr)
+ {
+ ASSERT(isValidEntry(ptr));
+
+ if (isSmall()) {
+ for (unsigned i = 0; i < m_size; i++) {
+ if (m_smallStorage[i] == ptr)
+ return;
+ }
+
+ if (m_size < SmallArraySize) {
+ m_smallStorage[m_size] = ptr;
+ ++m_size;
+ return;
+ }
+
+ grow(64);
+ // Fall through. We're no longer small :(
+ }
+
+ // If we're more than 3/4ths full we grow.
+ if (UNLIKELY(m_size * 4 >= m_capacity * 3)) {
+ grow(m_capacity * 2);
+ ASSERT(!(m_capacity & (m_capacity - 1)));
+ }
+
+ void** bucket = this->bucket(ptr);
+ if (*bucket != ptr) {
+ *bucket = ptr;
+ ++m_size;
+ }
+ }
+
+ inline bool contains(PtrType ptr) const
+ {
+ ASSERT(isValidEntry(ptr));
+ if (isSmall()) {
+ for (unsigned i = 0; i < m_size; i++) { // We only need to search up to m_size because we store things linearly inside m_smallStorage.
+ if (m_smallStorage[i] == ptr)
+ return true;
+ }
+ return false;
+ }
+
+ void** bucket = this->bucket(ptr);
+ return *bucket == ptr;
+ }
+
+ class iterator {
+ public:
+ iterator& operator++()
+ {
+ m_index++;
+ ASSERT(m_index <= m_capacity);
+ while (m_index < m_capacity && m_buffer[m_index] == emptyValue())
+ m_index++;
+ return *this;
+ }
+
+ PtrType operator*() const { ASSERT(m_index < m_capacity); return static_cast<PtrType>(m_buffer[m_index]); }
+ bool operator==(const iterator& other) const { ASSERT(m_buffer == other.m_buffer); return m_index == other.m_index; }
+ bool operator!=(const iterator& other) const { ASSERT(m_buffer == other.m_buffer); return !(*this == other); }
+
+ private:
+ template<typename U> friend class WTF::SmallPtrSet;
+ unsigned m_index;
+ unsigned m_capacity;
+ void** m_buffer;
+ };
+
+ iterator begin() const
+ {
+ iterator it;
+ it.m_index = -1;
+ it.m_capacity = m_capacity;
+ if (isSmall())
+ it.m_buffer = const_cast<void**>(m_smallStorage);
+ else
+ it.m_buffer = m_buffer;
+
+ ++it;
+
+ return it;
+ }
+
+ iterator end() const
+ {
+ iterator it;
+ it.m_index = m_capacity;
+ it.m_capacity = m_capacity;
+ if (isSmall())
+ it.m_buffer = const_cast<void**>(m_smallStorage);
+ else
+ it.m_buffer = m_buffer;
+
+ return it;
+ }
+
+ inline unsigned size() const { return m_size; }
+
+private:
+ constexpr static void* emptyValue()
+ {
+ return bitwise_cast<void*>(std::numeric_limits<uintptr_t>::max());
+ }
+
+ bool isValidEntry(const PtrType ptr) const
+ {
+ return ptr != emptyValue();
+ }
+
+ inline bool isSmall() const
+ {
+ return m_capacity == SmallArraySize;
+ }
+
+ inline void initialize()
+ {
+ m_size = 0;
+ m_buffer = nullptr;
+ m_capacity = SmallArraySize;
+ memset(m_smallStorage, -1, sizeof(void*) * SmallArraySize);
+ ASSERT(isSmall());
+ }
+
+ inline void grow(unsigned size)
+ {
+ ASSERT(static_cast<int32_t>(bitwise_cast<intptr_t>(emptyValue())) == -1);
+
+ size_t allocationSize = sizeof(void*) * size;
+ bool wasSmall = isSmall();
+ void** oldBuffer = wasSmall ? m_smallStorage : m_buffer;
+ unsigned oldCapacity = m_capacity;
+ m_buffer = static_cast<void**>(fastMalloc(allocationSize));
+ memset(m_buffer, -1, allocationSize);
+ m_capacity = size;
+
+ for (unsigned i = 0; i < oldCapacity; i++) {
+ if (oldBuffer[i] != emptyValue()) {
+ void** ptr = this->bucket(static_cast<PtrType>(oldBuffer[i]));
+ *ptr = oldBuffer[i];
+ }
+ }
+
+ if (!wasSmall)
+ fastFree(oldBuffer);
+ }
+
+
+ inline void** bucket(PtrType target) const
+ {
+ ASSERT(!(m_capacity & (m_capacity - 1)));
+ unsigned bucket = PtrHashBase<PtrType, false /* isSmartPtr */>::hash(target) & (m_capacity - 1);
+ unsigned index = 0;
+ while (true) {
+ void** ptr = m_buffer + bucket;
+ if (*ptr == emptyValue())
+ return ptr;
+ if (*ptr == target)
+ return ptr;
+ index++;
+ bucket = (bucket + index) & (m_capacity - 1);
+ }
+ }
+
+ static const unsigned SmallArraySize = 8;
+
+ unsigned m_size;
+ unsigned m_capacity;
+ void** m_buffer;
+ void* m_smallStorage[SmallArraySize];
+};
+
+} // namespace WTF
+
+using WTF::SmallPtrSet;
+
+#endif // SmallPtrSet_h
</ins></span></pre></div>
<a id="trunkSourceWTFwtfVectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Vector.h (198374 => 198375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Vector.h 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/WTF/wtf/Vector.h 2016-03-18 02:11:31 UTC (rev 198375)
</span><span class="lines">@@ -725,6 +725,7 @@
</span><span class="cx">
</span><span class="cx"> void append(ValueType&& value) { append<ValueType>(std::forward<ValueType>(value)); }
</span><span class="cx"> template<typename U> void append(U&&);
</span><ins>+ template<typename... Args> void constructAndAppend(Args&&...);
</ins><span class="cx">
</span><span class="cx"> void uncheckedAppend(ValueType&& value) { uncheckedAppend<ValueType>(std::forward<ValueType>(value)); }
</span><span class="cx"> template<typename U> void uncheckedAppend(U&&);
</span><span class="lines">@@ -787,6 +788,7 @@
</span><span class="cx"> const T* tryExpandCapacity(size_t newMinCapacity, const T*);
</span><span class="cx"> template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
</span><span class="cx"> template<typename U> void appendSlowCase(U&&);
</span><ins>+ template<typename... Args> void constructAndAppendSlowCase(Args&&...);
</ins><span class="cx">
</span><span class="cx"> void asanSetInitialBufferSizeTo(size_t);
</span><span class="cx"> void asanSetBufferSizeToFullCapacity();
</span><span class="lines">@@ -1214,6 +1216,19 @@
</span><span class="cx"> appendSlowCase(std::forward<U>(value));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename... Args>
+ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppend(Args&&... args)
+{
+ if (size() != capacity()) {
+ asanBufferSizeWillChangeTo(m_size + 1);
+ new (NotNull, end()) T(std::forward<Args>(args)...);
+ ++m_size;
+ return;
+ }
+
+ constructAndAppendSlowCase(std::forward<Args>(args)...);
+}
+
</ins><span class="cx"> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
</span><span class="cx"> void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
</span><span class="cx"> {
</span><span class="lines">@@ -1228,6 +1243,19 @@
</span><span class="cx"> ++m_size;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename... Args>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppendSlowCase(Args&&... args)
+{
+ ASSERT(size() == capacity());
+
+ expandCapacity(size() + 1);
+ ASSERT(begin());
+
+ asanBufferSizeWillChangeTo(m_size + 1);
+ new (NotNull, end()) T(std::forward<Args>(args)...);
+ ++m_size;
+}
+
</ins><span class="cx"> // This version of append saves a branch in the case where you know that the
</span><span class="cx"> // vector's capacity is large enough for the append to succeed.
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>