Ignore:
Timestamp:
Sep 6, 2016, 4:22:01 PM (9 years ago)
Author:
[email protected]
Message:

Make JSMap and JSSet faster
​https://bugs.webkit.org/show_bug.cgi?id=160989

Reviewed by Filip Pizlo.

JSTests:

  • microbenchmarks/dense-set.js: Added.

(bench):

  • microbenchmarks/large-map-iteration-with-additions.js: Added.

(bar):
(foo):

  • microbenchmarks/large-map-iteration-with-mutation.js: Added.

(bar):
(foo):

  • microbenchmarks/large-map-iteration.js: Added.

(bar):
(foo):

  • microbenchmarks/map-get-get-cse.js: Added.

(bar):
(foo):

  • microbenchmarks/map-has-get-cse-opportunity.js: Added.

(bar):
(foo):

  • microbenchmarks/sparse-set.js: Added.

(bench):

  • stress/map-cse-correctness.js: Added.

(assert):
(testHas):
(testGet):
(foo):

  • stress/map-iteration.js: Added.

(assert):
(test1):
(test2):
(test3):
(test4):
(test5):
(test6):
(test7):
(test8):
(test9):
(test10):
(test11):
(test12):
(test13):
(test14):
(test15):
(test16):
(test17):
(test18):

Source/JavaScriptCore:

This patch revamps how we implement Map and Set. It uses
a new hash map implementation. The hash map uses linear
probing and it uses Wang's 64 bit hash function for JSValues
that aren't strings. Strings use StringImpl's hash function.
The reason I wanted to roll our own HashTable is twofold:
I didn't want to inline WTF::HashMap's implementation into our
JIT, since that seems error prone and unmaintainable. Also, I wanted
a different structure for hash map buckets where buckets also exist in
a linked list.

The reason for making buckets part of a linked list is that iteration
is now simple. Iteration works by just traversing a linked list.
This design also allows for a simple implementation when doing iteration
while the hash table is mutating. Whenever we remove a bucket from
the hash table, it is removed from the list, meaning items in the
list don't point to it. However, the removed bucket will still point
to things that are either in the list, or have also been removed.
e.g, from a removed bucket, you can always follow pointers until you
either find an item in the list, or you find the tail of the list.
This is a really nice property because it means that a Map or Set
does not need to reason about the all the iterators that point
into its list. Also, whenever we add items to the Map or Set, we
hijack the tail as the new item, and make the new item point to a newly
created tail. This means that any iterator that pointed to the "tail" now
points to non-tail items. This makes the implementation of adding things
to the Map/Set while iterating easy.

I also made Map.prototype.get, Map.prototype.has, and Set.prototype.has
into intrinsics in the DFG. The IR can now reason about hash map
operations and can even do CSE over Wang's hash function, hash map
bucket lookups, hash map bucket loads, and testing if a key is in
the hash table. This makes code patterns for Map like so, super fast
in the FTL, since we will only be doing a single hash and hash bucket lookup:

`
function getKeyIfPresent(map, key) {

if (map.has(key))

return map.get(key);

}
`

This patch is roughly an 8% speedup on ES6SampleBench.

  • CMakeLists.txt:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • assembler/MacroAssemblerARM64.h:

(JSC::MacroAssemblerARM64::not64):

  • bytecode/SpeculatedType.cpp:

(JSC::speculationFromClassInfo):

  • bytecode/SpeculatedType.h:
  • dfg/DFGAbstractInterpreterInlines.h:

(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::execute):

  • dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::handleIntrinsicCall):

  • dfg/DFGClobberize.h:

(JSC::DFG::clobberize):

  • dfg/DFGDoesGC.cpp:

(JSC::DFG::doesGC):

  • dfg/DFGEdge.h:

(JSC::DFG::Edge::shift):
(JSC::DFG::Edge::makeWord):

  • dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):

  • dfg/DFGHeapLocation.cpp:

(WTF::printInternal):

  • dfg/DFGHeapLocation.h:
  • dfg/DFGNode.h:

(JSC::DFG::Node::hasHeapPrediction):

  • dfg/DFGNodeType.h:
  • dfg/DFGOperations.cpp:
  • dfg/DFGOperations.h:
  • dfg/DFGPredictionPropagationPhase.cpp:
  • dfg/DFGSafeToExecute.h:

(JSC::DFG::SafeToExecuteEdge::operator()):
(JSC::DFG::safeToExecute):

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::speculateMapObject):
(JSC::DFG::SpeculativeJIT::speculateSetObject):
(JSC::DFG::SpeculativeJIT::speculate):

  • dfg/DFGSpeculativeJIT.h:

(JSC::DFG::SpeculativeJIT::callOperation):

  • dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGUseKind.cpp:

(WTF::printInternal):

  • dfg/DFGUseKind.h:

(JSC::DFG::typeFilterFor):
(JSC::DFG::isCell):

  • ftl/FTLAbstractHeapRepository.h:
  • ftl/FTLCapabilities.cpp:

(JSC::FTL::canCompile):

  • ftl/FTLLowerDFGToB3.cpp:

(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileMapHash):
(JSC::FTL::DFG::LowerDFGToB3::compileGetMapBucket):
(JSC::FTL::DFG::LowerDFGToB3::compileLoadFromJSMapBucket):
(JSC::FTL::DFG::LowerDFGToB3::compileIsNonEmptyMapBucket):
(JSC::FTL::DFG::LowerDFGToB3::lowMapObject):
(JSC::FTL::DFG::LowerDFGToB3::lowSetObject):
(JSC::FTL::DFG::LowerDFGToB3::lowMapBucket):
(JSC::FTL::DFG::LowerDFGToB3::speculate):
(JSC::FTL::DFG::LowerDFGToB3::speculateMapObject):
(JSC::FTL::DFG::LowerDFGToB3::speculateSetObject):
(JSC::FTL::DFG::LowerDFGToB3::setMapBucket):
(JSC::FTL::DFG::LowerDFGToB3::lowRegExpObject): Deleted.
(JSC::FTL::DFG::LowerDFGToB3::lowStorage): Deleted.
(JSC::FTL::DFG::LowerDFGToB3::speculateRegExpObject): Deleted.
(JSC::FTL::DFG::LowerDFGToB3::setStorage): Deleted.

  • jit/AssemblyHelpers.cpp:

(JSC::AssemblyHelpers::wangsInt64Hash):

  • jit/AssemblyHelpers.h:

(JSC::AssemblyHelpers::emitAllocateDestructibleObject): Deleted.

  • jit/JITOperations.h:
  • parser/ModuleAnalyzer.cpp:

(JSC::ModuleAnalyzer::ModuleAnalyzer):

  • runtime/HashMapImpl.cpp: Added.

(JSC::HashMapBucket<Data>::visitChildren):
(JSC::HashMapImpl<HashMapBucket>::visitChildren):
(JSC::HashMapImpl<HashMapBucket>::copyBackingStore):

  • runtime/HashMapImpl.h: Added.

(JSC::HashMapBucket::selectStructure):
(JSC::HashMapBucket::createStructure):
(JSC::HashMapBucket::create):
(JSC::HashMapBucket::HashMapBucket):
(JSC::HashMapBucket::setNext):
(JSC::HashMapBucket::setPrev):
(JSC::HashMapBucket::setKey):
(JSC::HashMapBucket::setValue):
(JSC::HashMapBucket::key):
(JSC::HashMapBucket::value):
(JSC::HashMapBucket::next):
(JSC::HashMapBucket::prev):
(JSC::HashMapBucket::deleted):
(JSC::HashMapBucket::setDeleted):
(JSC::HashMapBucket::offsetOfKey):
(JSC::HashMapBucket::offsetOfValue):
(JSC::HashMapBuffer::allocationSize):
(JSC::HashMapBuffer::buffer):
(JSC::HashMapBuffer::create):
(JSC::areKeysEqual):
(JSC::normalizeMapKey):
(JSC::jsMapHash):
(JSC::HashMapImpl::selectStructure):
(JSC::HashMapImpl::createStructure):
(JSC::HashMapImpl::create):
(JSC::HashMapImpl::HashMapImpl):
(JSC::HashMapImpl::buffer):
(JSC::HashMapImpl::finishCreation):
(JSC::HashMapImpl::emptyValue):
(JSC::HashMapImpl::isEmpty):
(JSC::HashMapImpl::deletedValue):
(JSC::HashMapImpl::isDeleted):
(JSC::HashMapImpl::findBucket):
(JSC::HashMapImpl::get):
(JSC::HashMapImpl::has):
(JSC::HashMapImpl::add):
(JSC::HashMapImpl::remove):
(JSC::HashMapImpl::size):
(JSC::HashMapImpl::clear):
(JSC::HashMapImpl::bufferSizeInBytes):
(JSC::HashMapImpl::offsetOfBuffer):
(JSC::HashMapImpl::offsetOfCapacity):
(JSC::HashMapImpl::head):
(JSC::HashMapImpl::tail):
(JSC::HashMapImpl::approximateSize):
(JSC::HashMapImpl::findBucketAlreadyHashedAndNormalized):
(JSC::HashMapImpl::rehash):
(JSC::HashMapImpl::makeAndSetNewBuffer):

  • runtime/Intrinsic.h:
  • runtime/JSCJSValue.h:
  • runtime/JSCJSValueInlines.h:

(JSC::sameValue):

  • runtime/JSGlobalObject.cpp:

(JSC::JSGlobalObject::init):

  • runtime/JSMap.cpp:

(JSC::JSMap::destroy): Deleted.
(JSC::JSMap::estimatedSize): Deleted.
(JSC::JSMap::visitChildren): Deleted.
(JSC::JSMap::copyBackingStore): Deleted.
(JSC::JSMap::has): Deleted.
(JSC::JSMap::size): Deleted.
(JSC::JSMap::get): Deleted.
(JSC::JSMap::set): Deleted.
(JSC::JSMap::clear): Deleted.
(JSC::JSMap::remove): Deleted.

  • runtime/JSMap.h:

(JSC::JSMap::createStructure):
(JSC::JSMap::create):
(JSC::JSMap::get):
(JSC::JSMap::set):
(JSC::JSMap::JSMap):
(JSC::JSMap::Entry::key): Deleted.
(JSC::JSMap::Entry::value): Deleted.
(JSC::JSMap::Entry::visitChildren): Deleted.
(JSC::JSMap::Entry::setKey): Deleted.
(JSC::JSMap::Entry::setKeyWithoutWriteBarrier): Deleted.
(JSC::JSMap::Entry::setValue): Deleted.
(JSC::JSMap::Entry::clear): Deleted.

  • runtime/JSMapIterator.cpp:

(JSC::JSMapIterator::finishCreation):
(JSC::JSMapIterator::visitChildren):
(JSC::JSMapIterator::clone):

  • runtime/JSMapIterator.h:

(JSC::JSMapIterator::advanceIter):
(JSC::JSMapIterator::next):
(JSC::JSMapIterator::nextKeyValue):
(JSC::JSMapIterator::JSMapIterator):
(JSC::JSMapIterator::setIterator):
(JSC::JSMapIterator::finish): Deleted.
(JSC::JSMapIterator::iteratorData): Deleted.

  • runtime/JSModuleLoader.cpp:

(JSC::JSModuleLoader::finishCreation):

  • runtime/JSModuleLoader.h:

(JSC::JSModuleLoader::create):

  • runtime/JSModuleRecord.cpp:

(JSC::JSModuleRecord::finishCreation):

  • runtime/JSModuleRecord.h:

(JSC::JSModuleRecord::create):

  • runtime/JSSet.cpp:

(JSC::JSSet::destroy): Deleted.
(JSC::JSSet::estimatedSize): Deleted.
(JSC::JSSet::visitChildren): Deleted.
(JSC::JSSet::copyBackingStore): Deleted.
(JSC::JSSet::has): Deleted.
(JSC::JSSet::size): Deleted.
(JSC::JSSet::add): Deleted.
(JSC::JSSet::clear): Deleted.
(JSC::JSSet::remove): Deleted.

  • runtime/JSSet.h:

(JSC::JSSet::createStructure):
(JSC::JSSet::create):
(JSC::JSSet::add):
(JSC::JSSet::JSSet):
(JSC::JSSet::Entry::key): Deleted.
(JSC::JSSet::Entry::value): Deleted.
(JSC::JSSet::Entry::visitChildren): Deleted.
(JSC::JSSet::Entry::setKey): Deleted.
(JSC::JSSet::Entry::setKeyWithoutWriteBarrier): Deleted.
(JSC::JSSet::Entry::setValue): Deleted.
(JSC::JSSet::Entry::clear): Deleted.

  • runtime/JSSetIterator.cpp:

(JSC::JSSetIterator::finishCreation):
(JSC::JSSetIterator::visitChildren):
(JSC::JSSetIterator::clone):

  • runtime/JSSetIterator.h:

(JSC::JSSetIterator::advanceIter):
(JSC::JSSetIterator::next):
(JSC::JSSetIterator::JSSetIterator):
(JSC::JSSetIterator::setIterator):
(JSC::JSSetIterator::finish): Deleted.
(JSC::JSSetIterator::iteratorData): Deleted.

  • runtime/JSType.h:
  • runtime/MapBase.cpp: Added.

(JSC::MapBase<HashMapBucketType>::visitChildren):
(JSC::MapBase<HashMapBucketType>::estimatedSize):

  • runtime/MapBase.h: Added.

(JSC::MapBase::size):
(JSC::MapBase::has):
(JSC::MapBase::clear):
(JSC::MapBase::remove):
(JSC::MapBase::findBucket):
(JSC::MapBase::offsetOfHashMapImpl):
(JSC::MapBase::impl):
(JSC::MapBase::finishCreation):
(JSC::MapBase::MapBase):

  • runtime/MapConstructor.cpp:

(JSC::constructMap):

  • runtime/MapIteratorPrototype.cpp:

(JSC::MapIteratorPrototypeFuncNext):

  • runtime/MapPrototype.cpp:

(JSC::MapPrototype::finishCreation):
(JSC::getMap):
(JSC::privateFuncIsMap):
(JSC::privateFuncMapIteratorNext):

  • runtime/PropertyDescriptor.cpp:

(JSC::sameValue): Deleted.

  • runtime/PropertyDescriptor.h:
  • runtime/SetConstructor.cpp:

(JSC::constructSet):

  • runtime/SetIteratorPrototype.cpp:

(JSC::SetIteratorPrototypeFuncNext):

  • runtime/SetPrototype.cpp:

(JSC::SetPrototype::finishCreation):
(JSC::getSet):
(JSC::privateFuncSetIteratorNext):

  • runtime/VM.cpp:

(JSC::VM::VM):

  • runtime/VM.h:

Source/WebCore:

  • ForwardingHeaders/runtime/HashMapImpl.h: Added.
  • ForwardingHeaders/runtime/MapBase.h: Added.
  • bindings/js/SerializedScriptValue.cpp:

(WebCore::CloneSerializer::serialize):
(WebCore::CloneDeserializer::deserialize):

Source/WTF:

I made s_flagCount public in StringImpl since JSC's JITs now use this field.

  • wtf/text/StringImpl.h:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/jit/AssemblyHelpers.cpp

    r205507 r205520  
    627627}
    628628
     629#if USE(JSVALUE64)
     630void AssemblyHelpers::wangsInt64Hash(GPRReg inputAndResult, GPRReg scratch)
     631{
     632    GPRReg input = inputAndResult;
     633    // key += ~(key << 32);
     634    move(input, scratch);
     635    lshift64(TrustedImm32(32), scratch);
     636    not64(scratch);
     637    add64(scratch, input);
     638    // key ^= (key >> 22);
     639    move(input, scratch);
     640    urshift64(TrustedImm32(22), scratch);
     641    xor64(scratch, input);
     642    // key += ~(key << 13);
     643    move(input, scratch);
     644    lshift64(TrustedImm32(13), scratch);
     645    not64(scratch);
     646    add64(scratch, input);
     647    // key ^= (key >> 8);
     648    move(input, scratch);
     649    urshift64(TrustedImm32(8), scratch);
     650    xor64(scratch, input);
     651    // key += (key << 3);
     652    move(input, scratch);
     653    lshift64(TrustedImm32(3), scratch);
     654    add64(scratch, input);
     655    // key ^= (key >> 15);
     656    move(input, scratch);
     657    urshift64(TrustedImm32(15), scratch);
     658    xor64(scratch, input);
     659    // key += ~(key << 27);
     660    move(input, scratch);
     661    lshift64(TrustedImm32(27), scratch);
     662    not64(scratch);
     663    add64(scratch, input);
     664    // key ^= (key >> 31);
     665    move(input, scratch);
     666    urshift64(TrustedImm32(31), scratch);
     667    xor64(scratch, input);
     668
     669    // return static_cast<unsigned>(result)
     670    void* mask = bitwise_cast<void*>(static_cast<uintptr_t>(UINT_MAX));
     671    and64(TrustedImmPtr(mask), inputAndResult);
     672}
     673#endif // USE(JSVALUE64)
     674
    629675} // namespace JSC
    630676
Note: See TracChangeset for help on using the changeset viewer.