Optimize string additions

QV4::String can now either hold a pointer to a QStringData, or a pair of pointers to a left and right string. This reduces the overhead of an addition to allocating a new GC'ed object. To avoid huge chains of linked strings, we use a depth counter, and flatten the string once the depth reaches 16. Change-Id: If7192b8a9f67f0e36a9a8ea34a156c5222f127f4 Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>
author: Lars Knoll <lars.knoll@digia.com> 2013-10-31 13:22:07 +0100
committer: The Qt Project <gerrit-noreply@qt-project.org> 2013-10-31 20:16:11 +0100
commit: 02a8fc62491fbdee1913c2c20c939308e05f8d6f (patch)
tree: 5aa9117fd27491f74574fd2c0e21ab7da73fb236
parent: a02863c6cea9cd9dac5cff5c92f64c05de513675 (diff)
4 files changed, 116 insertions, 33 deletions
diff --git a/src/qml/jsruntime/qv4runtime.cpp b/src/qml/jsruntime/qv4runtime.cpp
index e227178042..6fe2c15f9a 100644
--- a/src/qml/jsruntime/qv4runtime.cpp
+++ b/src/qml/jsruntime/qv4runtime.cpp
@@ -308,7 +308,13 @@ QV4::ReturnedValue __qmljs_add_helper(ExecutionContext *ctx, const ValueRef left
             pleft = __qmljs_to_string(pleft, ctx);
         if (!pright->isString())
             pright = __qmljs_to_string(pright, ctx);
-        return __qmljs_string_concat(ctx, pleft->stringValue(), pright->stringValue())->asReturnedValue();
+        if (scope.engine->hasException)
+            return Encode::undefined();
+        if (!pleft->stringValue()->length())
+            return right->asReturnedValue();
+        if (!pright->stringValue()->length())
+            return pleft->asReturnedValue();
+        return (new (ctx->engine->memoryManager) String(ctx->engine, pleft->stringValue(), pright->stringValue()))->asReturnedValue();
     }
     double x = __qmljs_to_number(pleft);
     double y = __qmljs_to_number(pright);
@@ -365,19 +371,6 @@ Returned<String> *__qmljs_string_from_number(ExecutionContext *ctx, double numbe
     return ctx->engine->newString(qstr);
 }
 
-Returned<String> *__qmljs_string_concat(ExecutionContext *ctx, String *first, String *second)
-{
-    const QString &a = first->toQString();
-    const QString &b = second->toQString();
-    QString newStr(a.length() + b.length(), Qt::Uninitialized);
-    QChar *data = newStr.data();
-    memcpy(data, a.constData(), a.length()*sizeof(QChar));
-    data += a.length();
-    memcpy(data, b.constData(), b.length()*sizeof(QChar));
-
-    return ctx->engine->newString(newStr);
-}
-
 ReturnedValue __qmljs_object_default_value(Object *object, int typeHint)
 {
     if (typeHint == PREFERREDTYPE_HINT) {
diff --git a/src/qml/jsruntime/qv4runtime_p.h b/src/qml/jsruntime/qv4runtime_p.h
index 7315258b5e..0a5e18568a 100644
--- a/src/qml/jsruntime/qv4runtime_p.h
+++ b/src/qml/jsruntime/qv4runtime_p.h
@@ -148,7 +148,6 @@ QV4::ReturnedValue __qmljs_init_closure(QV4::ExecutionContext *ctx, int function
 // strings
 Q_QML_EXPORT double __qmljs_string_to_number(const QString &s);
 Returned<String> *__qmljs_string_from_number(QV4::ExecutionContext *ctx, double number);
-Returned<String> *__qmljs_string_concat(QV4::ExecutionContext *ctx, QV4::String *first, QV4::String *second);
 
 // objects
 Q_QML_EXPORT ReturnedValue __qmljs_object_default_value(QV4::Object *object, int typeHint);
diff --git a/src/qml/jsruntime/qv4string.cpp b/src/qml/jsruntime/qv4string.cpp
index bd4e2b16b0..01d76c48bd 100644
--- a/src/qml/jsruntime/qv4string.cpp
+++ b/src/qml/jsruntime/qv4string.cpp
@@ -105,7 +105,7 @@ const ManagedVTable String::static_vtbl =
 {
     call,
     construct,
-    0 /*markObjects*/,
+    markObjects,
     destroy,
     0 /*collectDeletables*/,
     hasInstance,
@@ -129,6 +129,15 @@ void String::destroy(Managed *that)
     static_cast<String*>(that)->~String();
 }
 
+void String::markObjects(Managed *that)
+{
+    String *s = static_cast<String *>(that);
+    if (s->depth) {
+        s->left->mark();
+        s->right->mark();
+    }
+}
+
 ReturnedValue String::get(Managed *m, const StringRef name, bool *hasProperty)
 {
     ExecutionEngine *v4 = m->engine();
@@ -138,7 +147,7 @@ ReturnedValue String::get(Managed *m, const StringRef name, bool *hasProperty)
     if (name->equals(v4->id_length)) {
         if (hasProperty)
             *hasProperty = true;
-        return Primitive::fromInt32(that->_text.length()).asReturnedValue();
+        return Primitive::fromInt32(that->_text->size).asReturnedValue();
     }
     PropertyAttributes attrs;
     Property *pd = v4->stringClass->prototype->__getPropertyDescriptor__(name, &attrs);
@@ -158,7 +167,7 @@ ReturnedValue String::getIndexed(Managed *m, uint index, bool *hasProperty)
     Scope scope(engine);
     ScopedString that(scope, static_cast<String *>(m));
 
-    if (index < that->_text.length()) {
+    if (index < (uint)that->_text->size) {
         if (hasProperty)
             *hasProperty = true;
         return Encode(engine->newString(that->toQString().mid(index, 1)));
@@ -207,7 +216,7 @@ PropertyAttributes String::query(const Managed *m, StringRef name)
 PropertyAttributes String::queryIndexed(const Managed *m, uint index)
 {
     const String *that = static_cast<const String *>(m);
-    return (index < that->_text.length()) ? Attr_NotConfigurable|Attr_NotWritable : Attr_Invalid;
+    return (index < (uint)that->_text->size) ? Attr_NotConfigurable|Attr_NotWritable : Attr_Invalid;
 }
 
 bool String::deleteProperty(Managed *, const StringRef)
@@ -215,7 +224,7 @@ bool String::deleteProperty(Managed *, const StringRef)
     return false;
 }
 
-bool String::deleteIndexedProperty(Managed *m, uint index)
+bool String::deleteIndexedProperty(Managed *, uint)
 {
     return false;
 }
@@ -240,13 +249,30 @@ bool String::isEqualTo(Managed *t, Managed *o)
 
 
 String::String(ExecutionEngine *engine, const QString &text)
-    : Managed(engine ? engine->emptyClass : 0), _text(text), identifier(0), stringHash(UINT_MAX)
+    : Managed(engine ? engine->emptyClass : 0), _text(const_cast<QString &>(text).data_ptr())
+    , identifier(0), stringHash(UINT_MAX)
+    , depth(0)
 {
+    _text->ref.ref();
     vtbl = &static_vtbl;
     type = Type_String;
     subtype = StringType_Unknown;
 }
 
+String::String(ExecutionEngine *engine, String *l, String *r)
+    : Managed(engine ? engine->emptyClass : 0)
+    , left(l), right(r)
+    , stringHash(UINT_MAX), depth(qMax(l->depth, r->depth) + 1)
+{
+    vtbl = &static_vtbl;
+    type = Type_String;
+    subtype = StringType_Unknown;
+
+    // make sure we don't get excessive depth in our strings
+    if (depth >= 16)
+        simplifyString();
+}
+
 uint String::toUInt(bool *ok) const
 {
     *ok = true;
@@ -281,13 +307,46 @@ bool String::equals(const StringRef other) const
 
 void String::makeIdentifierImpl() const
 {
+    if (depth)
+        simplifyString();
+    Q_ASSERT(!depth);
     engine()->identifierTable->identifier(this);
 }
 
+void String::simplifyString() const
+{
+    Q_ASSERT(depth);
+
+    int l = length();
+    QString result(l, Qt::Uninitialized);
+    QChar *ch = const_cast<QChar *>(result.constData());
+    recursiveAppend(ch);
+    _text = result.data_ptr();
+    _text->ref.ref();
+    identifier = 0;
+    depth = 0;
+}
+
+QChar *String::recursiveAppend(QChar *ch) const
+{
+    if (depth) {
+        ch = left->recursiveAppend(ch);
+        ch = right->recursiveAppend(ch);
+    } else {
+        memcpy(ch, _text->data(), _text->size*sizeof(QChar));
+        ch += _text->size;
+    }
+    return ch;
+}
+
+
 void String::createHashValue() const
 {
-    const QChar *ch = _text.constData();
-    const QChar *end = ch + _text.length();
+    if (depth)
+        simplifyString();
+    Q_ASSERT(!depth);
+    const QChar *ch = reinterpret_cast<const QChar *>(_text->data());
+    const QChar *end = ch + _text->size;
 
     // array indices get their number as hash value
     bool ok;
@@ -338,7 +397,7 @@ uint String::createHashValue(const char *ch, int length)
 
     uint h = 0xffffffff;
     while (ch < end) {
-        if (*ch >= 0x80)
+        if ((uchar)(*ch) >= 0x80)
             return UINT_MAX;
         h = 31 * h + *ch;
         ++ch;
diff --git a/src/qml/jsruntime/qv4string_p.h b/src/qml/jsruntime/qv4string_p.h
index 1e2aba32a9..ba2bc0dccd 100644
--- a/src/qml/jsruntime/qv4string_p.h
+++ b/src/qml/jsruntime/qv4string_p.h
@@ -60,10 +60,17 @@ struct Q_QML_EXPORT String : public Managed {
         StringType_ArrayIndex
     };
 
-    String() : Managed(0), identifier(0), stringHash(UINT_MAX)
+    String()
+        : Managed(0), _text(QStringData::sharedNull()), identifier(0)
+        , stringHash(UINT_MAX), depth(0)
     { vtbl = &static_vtbl; type = Type_String; subtype = StringType_Unknown; }
     String(ExecutionEngine *engine, const QString &text);
-    ~String() { _data = 0; }
+    String(ExecutionEngine *engine, String *l, String *n);
+    ~String() {
+        if (!depth && !_text->ref.deref())
+            QStringData::deallocate(_text);
+        _data = 0;
+    }
 
     bool equals(const StringRef other) const;
     inline bool isEqualTo(const String *other) const {
@@ -71,6 +78,7 @@ struct Q_QML_EXPORT String : public Managed {
             return true;
         if (hashValue() != other->hashValue())
             return false;
+        Q_ASSERT(!depth);
         if (identifier && identifier == other->identifier)
             return true;
         if (subtype >= StringType_UInt && subtype == other->subtype)
@@ -82,20 +90,28 @@ struct Q_QML_EXPORT String : public Managed {
         return toQString() < other->toQString();
     }
 
-    inline bool isEmpty() const { return _text.isEmpty(); }
-    inline const QString &toQString() const {
-        return _text;
+    inline bool isEmpty() const { return _text && !_text->size; }
+    inline QString toQString() const {
+        if (depth)
+            simplifyString();
+        QStringDataPtr ptr = { _text };
+        _text->ref.ref();
+        return QString(ptr);
     }
 
+    void simplifyString() const;
+
     inline unsigned hashValue() const {
         if (subtype == StringType_Unknown)
             createHashValue();
+        Q_ASSERT(!depth);
 
         return stringHash;
     }
     uint asArrayIndex() const {
         if (subtype == StringType_Unknown)
             createHashValue();
+        Q_ASSERT(!depth);
         if (subtype == StringType_ArrayIndex)
             return stringHash;
         return UINT_MAX;
@@ -115,19 +131,32 @@ struct Q_QML_EXPORT String : public Managed {
     static uint createHashValue(const char *ch, int length);
 
     bool startsWithUpper() const {
-        return _text.length() && _text.at(0).isUpper();
+        const String *l = this;
+        while (l->depth)
+            l = l->left;
+        return l->_text->size && QChar::isUpper(l->_text->data()[0]);
     }
     int length() const {
-        return _text.length();
+        if (!depth)
+            return _text->size;
+        return left->length() + right->length();
     }
 
-    QString _text;
-    mutable Identifier *identifier;
+    union {
+        mutable QStringData *_text;
+        mutable String *left;
+    };
+    union {
+        mutable Identifier *identifier;
+        mutable String *right;
+    };
     mutable uint stringHash;
+    mutable uint depth;
 
 
 protected:
     static void destroy(Managed *);
+    static void markObjects(Managed *that);
     static ReturnedValue get(Managed *m, const StringRef name, bool *hasProperty);
     static ReturnedValue getIndexed(Managed *m, uint index, bool *hasProperty);
     static void put(Managed *m, const StringRef name, const ValueRef value);
@@ -137,6 +166,9 @@ protected:
     static bool deleteProperty(Managed *, const StringRef);
     static bool deleteIndexedProperty(Managed *m, uint index);
     static bool isEqualTo(Managed *that, Managed *o);
+
+private:
+    QChar *recursiveAppend(QChar *ch) const;
 };
 
 template<>
author	Lars Knoll <lars.knoll@digia.com>	2013-10-31 13:22:07 +0100
committer	The Qt Project <gerrit-noreply@qt-project.org>	2013-10-31 20:16:11 +0100
commit	02a8fc62491fbdee1913c2c20c939308e05f8d6f (patch)
tree	5aa9117fd27491f74574fd2c0e21ab7da73fb236
parent	a02863c6cea9cd9dac5cff5c92f64c05de513675 (diff)