JSC should infer when indexed storage is contiguous, and optimize for it
https://bugs.webkit.org/show_bug.cgi?id=97288
Reviewed by Mark Hahnenberg.
Source/JavaScriptCore:
This introduces a new kind of indexed property storage called Contiguous,
which has the following properties:
- No header bits beyond IndexedHeader. This results in a 16 byte reduction
in memory usage per array versus an ArrayStorage array. It also means
that the total memory usage for an empty array is now just 3 * 8 on both
32-bit and 64-bit. Of that, only 8 bytes are array-specific; the rest is
our standard object header overhead.
- No need for hole checks on store. This results in a ~4% speed-up on
Kraken and a ~1% speed-up on V8v7.
- publicLength <= vectorLength. This means that doing new Array(blah)
immediately allocates room for blah elements.
- No sparse map or index bias.
If you ever do things to an array that would require publicLength >
vectorLength, a sparse map, or index bias, then we switch to ArrayStorage
mode. This seems to never happen in any benchmark we track, and is unlikely
to happen very frequently on any website.
* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* Target.pri:
* assembler/AbstractMacroAssembler.h:
(JSC::AbstractMacroAssembler::JumpList::append):
* assembler/MacroAssembler.h:
(MacroAssembler):
(JSC::MacroAssembler::patchableBranchTest32):
* bytecode/ByValInfo.h: Added.
(JSC):
(JSC::isOptimizableIndexingType):
(JSC::jitArrayModeForIndexingType):
(JSC::ByValInfo::ByValInfo):
(ByValInfo):
(JSC::getByValInfoBytecodeIndex):
* bytecode/CodeBlock.h:
(CodeBlock):
(JSC::CodeBlock::getByValInfo):
(JSC::CodeBlock::setNumberOfByValInfos):
(JSC::CodeBlock::numberOfByValInfos):
(JSC::CodeBlock::byValInfo):
* bytecode/SamplingTool.h:
* dfg/DFGAbstractState.cpp:
(JSC::DFG::AbstractState::execute):
* dfg/DFGArrayMode.cpp:
(JSC::DFG::fromObserved):
(JSC::DFG::modeAlreadyChecked):
(JSC::DFG::modeToString):
* dfg/DFGArrayMode.h:
(DFG):
(JSC::DFG::modeUsesButterfly):
(JSC::DFG::modeIsJSArray):
(JSC::DFG::isInBoundsAccess):
(JSC::DFG::mayStoreToTail):
(JSC::DFG::mayStoreToHole):
(JSC::DFG::modeIsPolymorphic):
(JSC::DFG::polymorphicIncludesContiguous):
(JSC::DFG::polymorphicIncludesArrayStorage):
(JSC::DFG::canCSEStorage):
(JSC::DFG::modeSupportsLength):
(JSC::DFG::benefitsFromStructureCheck):
(JSC::DFG::isEffectful):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleIntrinsic):
* dfg/DFGCSEPhase.cpp:
(JSC::DFG::CSEPhase::getArrayLengthElimination):
(JSC::DFG::CSEPhase::getByValLoadElimination):
(JSC::DFG::CSEPhase::performNodeCSE):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::checkArray):
(JSC::DFG::FixupPhase::blessArrayOperation):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::byValIsPure):
* dfg/DFGOperations.cpp:
* dfg/DFGOperations.h:
* dfg/DFGRepatch.cpp:
(JSC::DFG::tryCacheGetByID):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::checkArray):
(JSC::DFG::SpeculativeJIT::arrayify):
(JSC::DFG::SpeculativeJIT::compileGetArrayLength):
(JSC::DFG::SpeculativeJIT::temporaryRegisterForPutByVal):
(DFG):
* dfg/DFGSpeculativeJIT.h:
(DFG):
(JSC::DFG::SpeculativeJIT::callOperation):
(SpeculativeJIT):
(JSC::DFG::SpeculativeJIT::putByValWillNeedExtraRegister):
(JSC::DFG::SpeculativeJIT::temporaryRegisterForPutByVal):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compileContiguousGetByVal):
(DFG):
(JSC::DFG::SpeculativeJIT::compileArrayStorageGetByVal):
(JSC::DFG::SpeculativeJIT::compileContiguousPutByVal):
(JSC::DFG::SpeculativeJIT::compileArrayStoragePutByVal):
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compileContiguousGetByVal):
(DFG):
(JSC::DFG::SpeculativeJIT::compileArrayStorageGetByVal):
(JSC::DFG::SpeculativeJIT::compileContiguousPutByVal):
(JSC::DFG::SpeculativeJIT::compileArrayStoragePutByVal):
(JSC::DFG::SpeculativeJIT::compile):
* interpreter/Interpreter.cpp:
(SamplingScope):
(JSC::SamplingScope::SamplingScope):
(JSC::SamplingScope::~SamplingScope):
(JSC):
(JSC::Interpreter::execute):
* jit/JIT.cpp:
(JSC::JIT::privateCompileSlowCases):
(JSC::JIT::privateCompile):
* jit/JIT.h:
(JSC::ByValCompilationInfo::ByValCompilationInfo):
(ByValCompilationInfo):
(JSC):
(JIT):
(JSC::JIT::compileGetByVal):
(JSC::JIT::compilePutByVal):
* jit/JITInlineMethods.h:
(JSC::JIT::emitAllocateJSArray):
(JSC::JIT::emitArrayProfileStoreToHoleSpecialCase):
(JSC):
(JSC::arrayProfileSaw):
(JSC::JIT::chooseArrayMode):
* jit/JITOpcodes.cpp:
(JSC::JIT::emitSlow_op_get_argument_by_val):
(JSC::JIT::emit_op_new_array):
(JSC::JIT::emitSlow_op_new_array):
* jit/JITOpcodes32_64.cpp:
(JSC::JIT::emitSlow_op_get_argument_by_val):
* jit/JITPropertyAccess.cpp:
(JSC::JIT::emit_op_get_by_val):
(JSC):
(JSC::JIT::emitContiguousGetByVal):
(JSC::JIT::emitArrayStorageGetByVal):
(JSC::JIT::emitSlow_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::emitContiguousPutByVal):
(JSC::JIT::emitArrayStoragePutByVal):
(JSC::JIT::emitSlow_op_put_by_val):
(JSC::JIT::privateCompilePatchGetArrayLength):
(JSC::JIT::privateCompileGetByVal):
(JSC::JIT::privateCompilePutByVal):
* jit/JITPropertyAccess32_64.cpp:
(JSC::JIT::emit_op_get_by_val):
(JSC):
(JSC::JIT::emitContiguousGetByVal):
(JSC::JIT::emitArrayStorageGetByVal):
(JSC::JIT::emitSlow_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::emitContiguousPutByVal):
(JSC::JIT::emitArrayStoragePutByVal):
(JSC::JIT::emitSlow_op_put_by_val):
* jit/JITStubs.cpp:
(JSC::getByVal):
(JSC):
(JSC::DEFINE_STUB_FUNCTION):
(JSC::putByVal):
* jit/JITStubs.h:
* llint/LowLevelInterpreter.asm:
* llint/LowLevelInterpreter32_64.asm:
* llint/LowLevelInterpreter64.asm:
* runtime/ArrayConventions.h:
(JSC::isDenseEnoughForVector):
* runtime/ArrayPrototype.cpp:
(JSC):
(JSC::shift):
(JSC::unshift):
(JSC::arrayProtoFuncPush):
(JSC::arrayProtoFuncShift):
(JSC::arrayProtoFuncSplice):
(JSC::arrayProtoFuncUnShift):
* runtime/Butterfly.h:
(Butterfly):
(JSC::Butterfly::fromPointer):
(JSC::Butterfly::pointer):
(JSC::Butterfly::publicLength):
(JSC::Butterfly::vectorLength):
(JSC::Butterfly::setPublicLength):
(JSC::Butterfly::setVectorLength):
(JSC::Butterfly::contiguous):
(JSC::Butterfly::fromContiguous):
* runtime/ButterflyInlineMethods.h:
(JSC::Butterfly::unshift):
(JSC::Butterfly::shift):
* runtime/IndexingHeaderInlineMethods.h:
(JSC::IndexingHeader::indexingPayloadSizeInBytes):
* runtime/IndexingType.cpp: Added.
(JSC):
(JSC::indexingTypeToString):
* runtime/IndexingType.h:
(JSC):
(JSC::hasContiguous):
* runtime/JSArray.cpp:
(JSC::JSArray::setLengthWithArrayStorage):
(JSC::JSArray::setLength):
(JSC):
(JSC::JSArray::pop):
(JSC::JSArray::push):
(JSC::JSArray::shiftCountWithArrayStorage):
(JSC::JSArray::shiftCountWithAnyIndexingType):
(JSC::JSArray::unshiftCountWithArrayStorage):
(JSC::JSArray::unshiftCountWithAnyIndexingType):
(JSC::JSArray::sortNumericVector):
(JSC::JSArray::sortNumeric):
(JSC::JSArray::sortCompactedVector):
(JSC::JSArray::sort):
(JSC::JSArray::sortVector):
(JSC::JSArray::fillArgList):
(JSC::JSArray::copyToArguments):
(JSC::JSArray::compactForSorting):
* runtime/JSArray.h:
(JSC::JSArray::shiftCountForShift):
(JSC::JSArray::shiftCountForSplice):
(JSArray):
(JSC::JSArray::shiftCount):
(JSC::JSArray::unshiftCountForShift):
(JSC::JSArray::unshiftCountForSplice):
(JSC::JSArray::unshiftCount):
(JSC::JSArray::isLengthWritable):
(JSC::createContiguousArrayButterfly):
(JSC):
(JSC::JSArray::create):
(JSC::JSArray::tryCreateUninitialized):
* runtime/JSGlobalObject.cpp:
(JSC::JSGlobalObject::reset):
(JSC):
(JSC::JSGlobalObject::haveABadTime):
(JSC::JSGlobalObject::visitChildren):
* runtime/JSGlobalObject.h:
(JSGlobalObject):
(JSC::JSGlobalObject::arrayStructureWithArrayStorage):
(JSC::JSGlobalObject::addressOfArrayStructureWithArrayStorage):
(JSC::constructEmptyArray):
* runtime/JSObject.cpp:
(JSC::JSObject::visitButterfly):
(JSC::JSObject::getOwnPropertySlotByIndex):
(JSC::JSObject::putByIndex):
(JSC::JSObject::enterDictionaryIndexingMode):
(JSC::JSObject::createInitialContiguous):
(JSC):
(JSC::JSObject::createArrayStorage):
(JSC::JSObject::convertContiguousToArrayStorage):
(JSC::JSObject::ensureContiguousSlow):
(JSC::JSObject::ensureArrayStorageSlow):
(JSC::JSObject::ensureIndexedStorageSlow):
(JSC::JSObject::ensureArrayStorageExistsAndEnterDictionaryIndexingMode):
(JSC::JSObject::switchToSlowPutArrayStorage):
(JSC::JSObject::setPrototype):
(JSC::JSObject::deletePropertyByIndex):
(JSC::JSObject::getOwnPropertyNames):
(JSC::JSObject::defineOwnIndexedProperty):
(JSC::JSObject::putByIndexBeyondVectorLengthContiguousWithoutAttributes):
(JSC::JSObject::putByIndexBeyondVectorLength):
(JSC::JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage):
(JSC::JSObject::putDirectIndexBeyondVectorLength):
(JSC::JSObject::getNewVectorLength):
(JSC::JSObject::countElementsInContiguous):
(JSC::JSObject::increaseVectorLength):
(JSC::JSObject::ensureContiguousLengthSlow):
(JSC::JSObject::getOwnPropertyDescriptor):
* runtime/JSObject.h:
(JSC::JSObject::getArrayLength):
(JSC::JSObject::getVectorLength):
(JSC::JSObject::canGetIndexQuickly):
(JSC::JSObject::getIndexQuickly):
(JSC::JSObject::tryGetIndexQuickly):
(JSC::JSObject::canSetIndexQuickly):
(JSC::JSObject::canSetIndexQuicklyForPutDirect):
(JSC::JSObject::setIndexQuickly):
(JSC::JSObject::initializeIndex):
(JSC::JSObject::hasSparseMap):
(JSC::JSObject::inSparseIndexingMode):
(JSObject):
(JSC::JSObject::ensureContiguous):
(JSC::JSObject::ensureIndexedStorage):
(JSC::JSObject::ensureContiguousLength):
(JSC::JSObject::indexingData):
(JSC::JSObject::relevantLength):
* runtime/JSValue.cpp:
(JSC::JSValue::description):
* runtime/Options.cpp:
(JSC::Options::initialize):
* runtime/Structure.cpp:
(JSC::Structure::needsSlowPutIndexing):
(JSC):
(JSC::Structure::suggestedArrayStorageTransition):
* runtime/Structure.h:
(Structure):
* runtime/StructureTransitionTable.h:
(JSC::newIndexingType):
Source/WTF:
Moved out this helpful math utility to MathExtras, since we now use it in
multiple places.
* wtf/MathExtras.h:
(timesThreePlusOneDividedByTwo):
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@130826 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/runtime/JSArray.h b/Source/JavaScriptCore/runtime/JSArray.h
index 9cacdb1..d4622aa 100644
--- a/Source/JavaScriptCore/runtime/JSArray.h
+++ b/Source/JavaScriptCore/runtime/JSArray.h
@@ -71,8 +71,60 @@
void push(ExecState*, JSValue);
JSValue pop(ExecState*);
- bool shiftCount(ExecState*, unsigned startIndex, unsigned count);
- bool unshiftCount(ExecState*, unsigned startIndex, unsigned count);
+ enum ShiftCountMode {
+ // This form of shift hints that we're doing queueing. With this assumption in hand,
+ // we convert to ArrayStorage, which has queue optimizations.
+ ShiftCountForShift,
+
+ // This form of shift hints that we're just doing care and feeding on an array that
+ // is probably typically used for ordinary accesses. With this assumption in hand,
+ // we try to preserve whatever indexing type it has already.
+ ShiftCountForSplice
+ };
+
+ bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
+ {
+ return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
+ }
+ bool shiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
+ {
+ return shiftCountWithAnyIndexingType(exec, startIndex, count);
+ }
+ template<ShiftCountMode shiftCountMode>
+ bool shiftCount(ExecState* exec, unsigned startIndex, unsigned count)
+ {
+ switch (shiftCountMode) {
+ case ShiftCountForShift:
+ return shiftCountForShift(exec, startIndex, count);
+ case ShiftCountForSplice:
+ return shiftCountForSplice(exec, startIndex, count);
+ default:
+ CRASH();
+ return false;
+ }
+ }
+
+ bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
+ {
+ return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->globalData()));
+ }
+ bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
+ {
+ return unshiftCountWithAnyIndexingType(exec, startIndex, count);
+ }
+ template<ShiftCountMode shiftCountMode>
+ bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
+ {
+ switch (shiftCountMode) {
+ case ShiftCountForShift:
+ return unshiftCountForShift(exec, startIndex, count);
+ case ShiftCountForSplice:
+ return unshiftCountForSplice(exec, startIndex, count);
+ default:
+ CRASH();
+ return false;
+ }
+ }
void fillArgList(ExecState*, MarkedArgumentBuffer&);
void copyToArguments(ExecState*, CallFrame*, uint32_t length);
@@ -94,18 +146,44 @@
{
ArrayStorage* storage = arrayStorageOrNull();
if (!storage)
- return false;
+ return true;
SparseArrayValueMap* map = storage->m_sparseMap.get();
return !map || !map->lengthIsReadOnly();
}
-
- void setLengthWritable(ExecState*, bool writable);
-
- bool unshiftCountSlowCase(JSGlobalData&, bool, unsigned);
- unsigned compactForSorting();
+ bool shiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
+ bool shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage*);
+
+ bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
+ bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
+ bool unshiftCountSlowCase(JSGlobalData&, bool, unsigned);
+
+ template<IndexingType indexingType>
+ void sortNumericVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
+ template<IndexingType indexingType>
+ void sortCompactedVector(ExecState*, WriteBarrier<Unknown>* begin, unsigned relevantLength);
+
+ template<IndexingType indexingType>
+ void sortVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
+ bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
+ void setLengthWritable(ExecState*, bool writable);
+
+ template<IndexingType indexingType>
+ void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength);
};
+ inline Butterfly* createContiguousArrayButterfly(JSGlobalData& globalData, unsigned length)
+ {
+ IndexingHeader header;
+ header.setVectorLength(std::max(length, BASE_VECTOR_LEN));
+ header.setPublicLength(length);
+ Butterfly* result = Butterfly::create(
+ globalData, 0, 0, true, header, header.vectorLength() * sizeof(EncodedJSValue));
+ return result;
+ }
+
inline Butterfly* createArrayButterfly(JSGlobalData& globalData, unsigned initialLength)
{
Butterfly* butterfly = Butterfly::create(
@@ -121,7 +199,16 @@
inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
{
- Butterfly* butterfly = createArrayButterfly(globalData, initialLength);
+ Butterfly* butterfly;
+ if (LIKELY(structure->indexingType() == ArrayWithContiguous)) {
+ butterfly = createContiguousArrayButterfly(globalData, initialLength);
+ ASSERT(initialLength < MIN_SPARSE_ARRAY_INDEX);
+ } else {
+ ASSERT(
+ structure->indexingType() == ArrayWithSlowPutArrayStorage
+ || (initialLength && structure->indexingType() == ArrayWithArrayStorage));
+ butterfly = createArrayButterfly(globalData, initialLength);
+ }
JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure, butterfly);
array->finishCreation(globalData);
return array;
@@ -133,15 +220,26 @@
if (vectorLength > MAX_STORAGE_VECTOR_LENGTH)
return 0;
- void* temp;
- if (!globalData.heap.tryAllocateStorage(Butterfly::totalSize(0, 0, true, ArrayStorage::sizeFor(vectorLength)), &temp))
- return 0;
- Butterfly* butterfly = Butterfly::fromBase(temp, 0, 0);
- *butterfly->indexingHeader() = indexingHeaderForArray(initialLength, vectorLength);
- ArrayStorage* storage = butterfly->arrayStorage();
- storage->m_indexBias = 0;
- storage->m_sparseMap.clear();
- storage->m_numValuesInVector = initialLength;
+ Butterfly* butterfly;
+ if (LIKELY(structure->indexingType() == ArrayWithContiguous)) {
+
+ void* temp;
+ if (!globalData.heap.tryAllocateStorage(Butterfly::totalSize(0, 0, true, vectorLength * sizeof(EncodedJSValue)), &temp))
+ return 0;
+ butterfly = Butterfly::fromBase(temp, 0, 0);
+ butterfly->setVectorLength(vectorLength);
+ butterfly->setPublicLength(initialLength);
+ } else {
+ void* temp;
+ if (!globalData.heap.tryAllocateStorage(Butterfly::totalSize(0, 0, true, ArrayStorage::sizeFor(vectorLength)), &temp))
+ return 0;
+ butterfly = Butterfly::fromBase(temp, 0, 0);
+ *butterfly->indexingHeader() = indexingHeaderForArray(initialLength, vectorLength);
+ ArrayStorage* storage = butterfly->arrayStorage();
+ storage->m_indexBias = 0;
+ storage->m_sparseMap.clear();
+ storage->m_numValuesInVector = initialLength;
+ }
JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure, butterfly);
array->finishCreation(globalData);
