aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorLars Knoll <lars.knoll@digia.com>2013-09-02 14:25:15 +0200
committerThe Qt Project <gerrit-noreply@qt-project.org>2013-09-02 17:27:36 +0200
commitea0ea907edbe7dd0c65f10752d7df1de6f0fd63b (patch)
treec9e0641d43cd19dfc3ad022c34e196592e22a6cb
parent6359ab63cd9c730a168e8b8da4c275e2d03d25d5 (diff)
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 <simon.hausmann@digia.com>
-rw-r--r--src/qml/jsruntime/qv4engine.cpp15
-rw-r--r--src/qml/jsruntime/qv4engine_p.h5
-rw-r--r--src/qml/jsruntime/qv4object_p.h5
-rw-r--r--src/qml/jsruntime/qv4regexpobject.cpp19
-rw-r--r--src/qml/jsruntime/qv4regexpobject_p.h5
-rw-r--r--src/qml/jsruntime/qv4stringobject.cpp80
6 files changed, 87 insertions, 42 deletions
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<CompiledData::CompilationUnit*> compilationUnits;
QMap<quintptr, QV4::Function*> 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<uint, 16> 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<RegExpObject>();
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);
}