Implement SmallPtrSet and integrate it into the Parser
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 18 Mar 2016 02:11:31 +0000 (02:11 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 18 Mar 2016 02:11:31 +0000 (02:11 +0000)
commit496bbc39c50c43577af9bcc5e642961eea1a884f
tree510d5835644f631b6d4bc6fe03d37d8b5d869275
parent9d9b128d7fe983381cb51ee34246c4a975dd5d07
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):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@198375 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/parser/Parser.cpp
Source/JavaScriptCore/parser/Parser.h
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/SmallPtrSet.h [new file with mode: 0644]
Source/WTF/wtf/Vector.h