From ea0ea907edbe7dd0c65f10752d7df1de6f0fd63b Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Mon, 2 Sep 2013 14:25:15 +0200 Subject: Optimize String.replace and RegExp.exec This speeds up the v8 regexp benchmark by a factor 2.5 :) Change-Id: Ibd6b18ee28181aa712429cbec4598984e0c69820 Reviewed-by: Simon Hausmann --- src/qml/jsruntime/qv4engine.cpp | 15 +++++++ src/qml/jsruntime/qv4engine_p.h | 5 +++ src/qml/jsruntime/qv4object_p.h | 5 +-- src/qml/jsruntime/qv4regexpobject.cpp | 19 +++++---- src/qml/jsruntime/qv4regexpobject_p.h | 5 +++ src/qml/jsruntime/qv4stringobject.cpp | 80 ++++++++++++++++++++++------------- 6 files changed, 87 insertions(+), 42 deletions(-) (limited to 'src/qml') diff --git a/src/qml/jsruntime/qv4engine.cpp b/src/qml/jsruntime/qv4engine.cpp index af87ee2a45..ae444ab938 100644 --- a/src/qml/jsruntime/qv4engine.cpp +++ b/src/qml/jsruntime/qv4engine.cpp @@ -135,6 +135,8 @@ ExecutionEngine::ExecutionEngine(QQmlJS::EvalISelFactory *factory) id_eval = newIdentifier(QStringLiteral("eval")); id_uintMax = newIdentifier(QStringLiteral("4294967295")); id_name = newIdentifier(QStringLiteral("name")); + id_index = newIdentifier(QStringLiteral("index")); + id_input = newIdentifier(QStringLiteral("input")); ObjectPrototype *objectPrototype = new (memoryManager) ObjectPrototype(emptyClass); objectClass = emptyClass->changePrototype(objectPrototype); @@ -171,6 +173,10 @@ ExecutionEngine::ExecutionEngine(QQmlJS::EvalISelFactory *factory) RegExpPrototype *regExpPrototype = new (memoryManager) RegExpPrototype(objectClass); regExpClass = emptyClass->changePrototype(regExpPrototype); + regExpExecArrayClass = arrayClass->addMember(id_index, Attr_Data, &index); + Q_ASSERT(index == RegExpObject::Index_ArrayIndex); + regExpExecArrayClass = regExpExecArrayClass->addMember(id_input, Attr_Data, &index); + Q_ASSERT(index == RegExpObject::Index_ArrayInput); ErrorPrototype *errorPrototype = new (memoryManager) ErrorPrototype(objectClass); errorClass = emptyClass->changePrototype(errorPrototype); @@ -392,6 +398,13 @@ ArrayObject *ExecutionEngine::newArrayObject(const QStringList &list) return object; } +ArrayObject *ExecutionEngine::newArrayObject(InternalClass *ic) +{ + ArrayObject *object = new (memoryManager) ArrayObject(ic); + return object; +} + + DateObject *ExecutionEngine::newDateObject(const Value &value) { DateObject *object = new (memoryManager) DateObject(this, value); @@ -661,6 +674,8 @@ void ExecutionEngine::markObjects() id_eval->mark(); id_uintMax->mark(); id_name->mark(); + id_index->mark(); + id_input->mark(); objectCtor.mark(); stringCtor.mark(); diff --git a/src/qml/jsruntime/qv4engine_p.h b/src/qml/jsruntime/qv4engine_p.h index 857079a48f..b7b27a48f9 100644 --- a/src/qml/jsruntime/qv4engine_p.h +++ b/src/qml/jsruntime/qv4engine_p.h @@ -163,6 +163,8 @@ struct Q_QML_EXPORT ExecutionEngine InternalClass *protoClass; InternalClass *regExpClass; + InternalClass *regExpExecArrayClass; + InternalClass *errorClass; InternalClass *evalErrorClass; InternalClass *rangeErrorClass; @@ -206,6 +208,8 @@ struct Q_QML_EXPORT ExecutionEngine String *id_eval; String *id_uintMax; String *id_name; + String *id_index; + String *id_input; QSet compilationUnits; QMap allFunctions; @@ -257,6 +261,7 @@ struct Q_QML_EXPORT ExecutionEngine ArrayObject *newArrayObject(int count = 0); ArrayObject *newArrayObject(const QStringList &list); + ArrayObject *newArrayObject(InternalClass *ic); DateObject *newDateObject(const Value &value); DateObject *newDateObject(const QDateTime &dt); diff --git a/src/qml/jsruntime/qv4object_p.h b/src/qml/jsruntime/qv4object_p.h index 09476c9009..995749ff74 100644 --- a/src/qml/jsruntime/qv4object_p.h +++ b/src/qml/jsruntime/qv4object_p.h @@ -371,12 +371,11 @@ struct ArrayObject: Object { ArrayObject(ExecutionEngine *engine) : Object(engine->arrayClass) { init(engine); } ArrayObject(ExecutionEngine *engine, const QStringList &list); + ArrayObject(InternalClass *ic) : Object(ic) { init(ic->engine); } + void init(ExecutionEngine *engine); QStringList toQStringList() const; - -protected: - ArrayObject(InternalClass *ic) : Object(ic) { init(ic->engine); } }; inline uint Object::arrayLength() const diff --git a/src/qml/jsruntime/qv4regexpobject.cpp b/src/qml/jsruntime/qv4regexpobject.cpp index cd104c0a71..c213c78aeb 100644 --- a/src/qml/jsruntime/qv4regexpobject.cpp +++ b/src/qml/jsruntime/qv4regexpobject.cpp @@ -177,7 +177,7 @@ void RegExpObject::markObjects(Managed *that) Property *RegExpObject::lastIndexProperty(ExecutionContext *ctx) { - assert(0 == internalClass->find(ctx->engine->newIdentifier(QStringLiteral("lastIndex")))); + Q_ASSERT(0 == internalClass->find(ctx->engine->newIdentifier(QStringLiteral("lastIndex")))); return &memberData[0]; } @@ -317,18 +317,19 @@ Value RegExpPrototype::method_exec(SimpleCallContext *ctx) } // fill in result data - ArrayObject *array = ctx->engine->newArrayObject(); - for (int i = 0; i < r->value->captureCount(); ++i) { + ArrayObject *array = ctx->engine->newArrayObject(ctx->engine->regExpExecArrayClass); + int len = r->value->captureCount(); + array->arrayReserve(len); + for (int i = 0; i < len; ++i) { int start = matchOffsets[i * 2]; int end = matchOffsets[i * 2 + 1]; - Value entry = Value::undefinedValue(); - if (start != -1 && end != -1) - entry = Value::fromString(ctx, s.mid(start, end - start)); - array->push_back(entry); + array->arrayData[i].value = (start != -1 && end != -1) ? Value::fromString(ctx, s.mid(start, end - start)) : Value::undefinedValue(); } + array->arrayDataLen = len; + array->setArrayLengthUnchecked(len); - array->put(ctx, QLatin1String("index"), Value::fromInt32(result)); - array->put(ctx, QLatin1String("input"), arg); + array->memberData[Index_ArrayIndex].value = Value::fromInt32(result); + array->memberData[Index_ArrayInput].value = arg; if (r->global) r->lastIndexProperty(ctx)->value = Value::fromInt32(matchOffsets[1]); diff --git a/src/qml/jsruntime/qv4regexpobject_p.h b/src/qml/jsruntime/qv4regexpobject_p.h index c95c00bbf6..80868d90db 100644 --- a/src/qml/jsruntime/qv4regexpobject_p.h +++ b/src/qml/jsruntime/qv4regexpobject_p.h @@ -74,6 +74,11 @@ struct RegExpObject: Object { RegExp_Multiline = 0x04 }; + enum { + Index_ArrayIndex = ArrayObject::LengthPropertyIndex + 1, + Index_ArrayInput = Index_ArrayIndex + 1 + }; + RegExp* value; Property *lastIndexProperty(ExecutionContext *ctx); bool global; diff --git a/src/qml/jsruntime/qv4stringobject.cpp b/src/qml/jsruntime/qv4stringobject.cpp index 442297ffe0..52d98502a3 100644 --- a/src/qml/jsruntime/qv4stringobject.cpp +++ b/src/qml/jsruntime/qv4stringobject.cpp @@ -401,17 +401,16 @@ Value StringPrototype::method_match(SimpleCallContext *context) } -static QString makeReplacementString(const QString &input, const QString& replaceValue, uint* matchOffsets, int captureCount) +static void appendReplacementString(QString *result, const QString &input, const QString& replaceValue, uint* matchOffsets, int captureCount) { - QString result; - result.reserve(replaceValue.length()); + result->reserve(result->length() + replaceValue.length()); for (int i = 0; i < replaceValue.length(); ++i) { if (replaceValue.at(i) == QLatin1Char('$') && i < replaceValue.length() - 1) { - char ch = replaceValue.at(++i).toLatin1(); + ushort ch = replaceValue.at(++i).unicode(); uint substStart = JSC::Yarr::offsetNoMatch; uint substEnd = JSC::Yarr::offsetNoMatch; if (ch == '$') { - result += ch; + *result += ch; continue; } else if (ch == '&') { substStart = matchOffsets[0]; @@ -423,27 +422,28 @@ static QString makeReplacementString(const QString &input, const QString& replac substStart = matchOffsets[1]; substEnd = input.length(); } else if (ch >= '1' && ch <= '9') { - char capture = ch - '0'; + uint capture = ch - '0'; if (capture > 0 && capture < captureCount) { substStart = matchOffsets[capture * 2]; substEnd = matchOffsets[capture * 2 + 1]; } } else if (ch == '0' && i < replaceValue.length() - 1) { int capture = (ch - '0') * 10; - ch = replaceValue.at(++i).toLatin1(); - capture += ch - '0'; - if (capture > 0 && capture < captureCount) { - substStart = matchOffsets[capture * 2]; - substEnd = matchOffsets[capture * 2 + 1]; + ch = replaceValue.at(++i).unicode(); + if (ch >= '0' && ch <= '9') { + capture += ch - '0'; + if (capture > 0 && capture < captureCount) { + substStart = matchOffsets[capture * 2]; + substEnd = matchOffsets[capture * 2 + 1]; + } } } if (substStart != JSC::Yarr::offsetNoMatch && substEnd != JSC::Yarr::offsetNoMatch) - result += input.midRef(substStart, substEnd - substStart); + *result += input.midRef(substStart, substEnd - substStart); } else { - result += replaceValue.at(i); + *result += replaceValue.at(i); } } - return result; } Value StringPrototype::method_replace(SimpleCallContext *ctx) @@ -455,27 +455,39 @@ Value StringPrototype::method_replace(SimpleCallContext *ctx) string = ctx->thisObject.toString(ctx)->toQString(); int numCaptures = 0; - QVarLengthArray matchOffsets; int numStringMatches = 0; + uint allocatedMatchOffsets = 32; + uint _matchOffsets[32]; + uint *matchOffsets = _matchOffsets; + uint nMatchOffsets = 0; + Value searchValue = ctx->argument(0); RegExpObject *regExp = searchValue.as(); if (regExp) { uint offset = 0; while (true) { - int oldSize = matchOffsets.size(); - matchOffsets.resize(matchOffsets.size() + regExp->value->captureCount() * 2); - if (regExp->value->match(string, offset, matchOffsets.data() + oldSize) == JSC::Yarr::offsetNoMatch) { - matchOffsets.resize(oldSize); + int oldSize = nMatchOffsets; + if (allocatedMatchOffsets < nMatchOffsets + regExp->value->captureCount() * 2) { + allocatedMatchOffsets = qMax(allocatedMatchOffsets * 2, nMatchOffsets + regExp->value->captureCount() * 2); + uint *newOffsets = (uint *)malloc(allocatedMatchOffsets*sizeof(uint)); + memcpy(newOffsets, matchOffsets, nMatchOffsets*sizeof(uint)); + if (matchOffsets != _matchOffsets) + free(matchOffsets); + matchOffsets = newOffsets; + } + if (regExp->value->match(string, offset, matchOffsets + oldSize) == JSC::Yarr::offsetNoMatch) { + nMatchOffsets = oldSize; break; } + nMatchOffsets += regExp->value->captureCount() * 2; if (!regExp->global) break; offset = qMax(offset + 1, matchOffsets[oldSize + 1]); } if (regExp->global) regExp->lastIndexProperty(ctx)->value = Value::fromUInt32(0); - numStringMatches = matchOffsets.size() / (regExp->value->captureCount() * 2); + numStringMatches = nMatchOffsets / (regExp->value->captureCount() * 2); numCaptures = regExp->value->captureCount(); } else { numCaptures = 1; @@ -483,18 +495,19 @@ Value StringPrototype::method_replace(SimpleCallContext *ctx) int idx = string.indexOf(searchString); if (idx != -1) { numStringMatches = 1; - matchOffsets.resize(2); + nMatchOffsets = 2; matchOffsets[0] = idx; matchOffsets[1] = idx + searchString.length(); } } - QString result = string; + QString result; Value replaceValue = ctx->argument(1); if (FunctionObject* searchCallback = replaceValue.asFunctionObject()) { - int replacementDelta = 0; + result.reserve(string.length() + 10*numStringMatches); CALLDATA(numCaptures + 2); d.thisObject = Value::undefinedValue(); + int lastEnd = 0; for (int i = 0; i < numStringMatches; ++i) { for (int k = 0; k < numCaptures; ++k) { int idx = (i * numCaptures + k) * 2; @@ -506,19 +519,22 @@ Value StringPrototype::method_replace(SimpleCallContext *ctx) d.args[k] = entry; } uint matchStart = matchOffsets[i * numCaptures * 2]; + Q_ASSERT(matchStart >= lastEnd); uint matchEnd = matchOffsets[i * numCaptures * 2 + 1]; d.args[numCaptures] = Value::fromUInt32(matchStart); d.args[numCaptures + 1] = Value::fromString(ctx, string); Value replacement = searchCallback->call(d); - QString replacementString = replacement.toString(ctx)->toQString(); - result.replace(replacementDelta + matchStart, matchEnd - matchStart, replacementString); - replacementDelta += replacementString.length() - matchEnd + matchStart; + result += string.midRef(lastEnd, matchStart - lastEnd); + result += replacement.toString(ctx)->toQString(); + lastEnd = matchEnd; } + result += string.midRef(lastEnd); } else { QString newString = replaceValue.toString(ctx)->toQString(); - int replacementDelta = 0; + result.reserve(string.length() + numStringMatches*newString.size()); + int lastEnd = 0; for (int i = 0; i < numStringMatches; ++i) { int baseIndex = i * numCaptures * 2; uint matchStart = matchOffsets[baseIndex]; @@ -526,12 +542,16 @@ Value StringPrototype::method_replace(SimpleCallContext *ctx) if (matchStart == JSC::Yarr::offsetNoMatch) continue; - QString replacement = makeReplacementString(string, newString, matchOffsets.data() + baseIndex, numCaptures); - result.replace(replacementDelta + matchStart, matchEnd - matchStart, replacement); - replacementDelta += replacement.length() - matchEnd + matchStart; + result += string.midRef(lastEnd, matchStart - lastEnd); + appendReplacementString(&result, string, newString, matchOffsets + baseIndex, numCaptures); + lastEnd = matchEnd; } + result += string.midRef(lastEnd); } + if (matchOffsets != _matchOffsets) + free(matchOffsets); + return Value::fromString(ctx, result); } -- cgit v1.2.3