Better way of handling string additions

The old algorithm still had some quadratic behavior when adding
strings in a loop. This fixes is by keeping track of the longest
substring used, as well as the length of the string. If the length
is larger then twice the length of the longest substring, we
simplify the string.

Change-Id: I9d99ae1632a8046ac135e67bdbb448638d15836d
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

3 files changed, 31 insertions, 25 deletions

diff --git a/src/qml/jsruntime/qv4string.cpp b/src/qml/jsruntime/qv4string.cpp
index 016bc3878e..30b08badcd 100644
--- a/src/qml/jsruntime/qv4string.cpp
+++ b/src/qml/jsruntime/qv4string.cpp
@@ -132,7 +132,7 @@ void String::destroy(Managed *that)
 void String::markObjects(Managed *that)
 {
     String *s = static_cast<String *>(that);
-    if (s->depth) {
+    if (s->largestSubLength) {
         s->left->mark();
         s->right->mark();
     }
@@ -251,9 +251,10 @@ bool String::isEqualTo(Managed *t, Managed *o)
 String::String(ExecutionEngine *engine, const QString &text)
     : Managed(engine ? engine->emptyClass : 0), _text(const_cast<QString &>(text).data_ptr())
     , identifier(0), stringHash(UINT_MAX)
-    , depth(0)
+    , largestSubLength(0)
 {
     _text->ref.ref();
+    len = _text->size;
     vtbl = &static_vtbl;
     type = Type_String;
     subtype = StringType_Unknown;
@@ -262,14 +263,20 @@ String::String(ExecutionEngine *engine, const QString &text)
 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)
+    , stringHash(UINT_MAX), largestSubLength(qMax(l->largestSubLength, r->largestSubLength))
+    , len(l->len + r->len)
 {
     vtbl = &static_vtbl;
     type = Type_String;
     subtype = StringType_Unknown;
 
+    if (!l->largestSubLength && l->len > largestSubLength)
+        largestSubLength = l->len;
+    if (!r->largestSubLength && r->len > largestSubLength)
+        largestSubLength = r->len;
+
     // make sure we don't get excessive depth in our strings
-    if (depth >= 16)
+    if (len > 256 && len >= 2*largestSubLength)
         simplifyString();
 }
 
@@ -307,15 +314,15 @@ bool String::equals(const StringRef other) const
 
 void String::makeIdentifierImpl() const
 {
-    if (depth)
+    if (largestSubLength)
         simplifyString();
-    Q_ASSERT(!depth);
+    Q_ASSERT(!largestSubLength);
     engine()->identifierTable->identifier(this);
 }
 
 void String::simplifyString() const
 {
-    Q_ASSERT(depth);
+    Q_ASSERT(largestSubLength);
 
     int l = length();
     QString result(l, Qt::Uninitialized);
@@ -324,12 +331,12 @@ void String::simplifyString() const
     _text = result.data_ptr();
     _text->ref.ref();
     identifier = 0;
-    depth = 0;
+    largestSubLength = 0;
 }
 
 QChar *String::recursiveAppend(QChar *ch) const
 {
-    if (depth) {
+    if (largestSubLength) {
         ch = left->recursiveAppend(ch);
         ch = right->recursiveAppend(ch);
     } else {
@@ -342,9 +349,9 @@ QChar *String::recursiveAppend(QChar *ch) const
 
 void String::createHashValue() const
 {
-    if (depth)
+    if (largestSubLength)
         simplifyString();
-    Q_ASSERT(!depth);
+    Q_ASSERT(!largestSubLength);
     const QChar *ch = reinterpret_cast<const QChar *>(_text->data());
     const QChar *end = ch + _text->size;
 
diff --git a/src/qml/jsruntime/qv4string_p.h b/src/qml/jsruntime/qv4string_p.h
index ba2bc0dccd..5412371bc0 100644
--- a/src/qml/jsruntime/qv4string_p.h
+++ b/src/qml/jsruntime/qv4string_p.h
@@ -62,12 +62,12 @@ struct Q_QML_EXPORT String : public Managed {
 
     String()
         : Managed(0), _text(QStringData::sharedNull()), identifier(0)
-        , stringHash(UINT_MAX), depth(0)
+        , stringHash(UINT_MAX), largestSubLength(0), len(0)
     { vtbl = &static_vtbl; type = Type_String; subtype = StringType_Unknown; }
     String(ExecutionEngine *engine, const QString &text);
     String(ExecutionEngine *engine, String *l, String *n);
     ~String() {
-        if (!depth && !_text->ref.deref())
+        if (!largestSubLength && !_text->ref.deref())
             QStringData::deallocate(_text);
         _data = 0;
     }
@@ -78,7 +78,7 @@ struct Q_QML_EXPORT String : public Managed {
             return true;
         if (hashValue() != other->hashValue())
             return false;
-        Q_ASSERT(!depth);
+        Q_ASSERT(!largestSubLength);
         if (identifier && identifier == other->identifier)
             return true;
         if (subtype >= StringType_UInt && subtype == other->subtype)
@@ -90,9 +90,8 @@ struct Q_QML_EXPORT String : public Managed {
         return toQString() < other->toQString();
     }
 
-    inline bool isEmpty() const { return _text && !_text->size; }
     inline QString toQString() const {
-        if (depth)
+        if (largestSubLength)
             simplifyString();
         QStringDataPtr ptr = { _text };
         _text->ref.ref();
@@ -104,14 +103,14 @@ struct Q_QML_EXPORT String : public Managed {
     inline unsigned hashValue() const {
         if (subtype == StringType_Unknown)
             createHashValue();
-        Q_ASSERT(!depth);
+        Q_ASSERT(!largestSubLength);
 
         return stringHash;
     }
     uint asArrayIndex() const {
         if (subtype == StringType_Unknown)
             createHashValue();
-        Q_ASSERT(!depth);
+        Q_ASSERT(!largestSubLength);
         if (subtype == StringType_ArrayIndex)
             return stringHash;
         return UINT_MAX;
@@ -132,14 +131,13 @@ struct Q_QML_EXPORT String : public Managed {
 
     bool startsWithUpper() const {
         const String *l = this;
-        while (l->depth)
+        while (l->largestSubLength)
             l = l->left;
         return l->_text->size && QChar::isUpper(l->_text->data()[0]);
     }
     int length() const {
-        if (!depth)
-            return _text->size;
-        return left->length() + right->length();
+        Q_ASSERT((largestSubLength && (len == left->len + right->len)) || len == (uint)_text->size);
+        return len;
     }
 
     union {
@@ -151,7 +149,8 @@ struct Q_QML_EXPORT String : public Managed {
         mutable String *right;
     };
     mutable uint stringHash;
-    mutable uint depth;
+    mutable uint largestSubLength;
+    uint len;
 
 
 protected:
diff --git a/src/qml/qml/qqmllocale.cpp b/src/qml/qml/qqmllocale.cpp
index 81a6ffc590..b92b3e4c2c 100644
--- a/src/qml/qml/qqmllocale.cpp
+++ b/src/qml/qml/qqmllocale.cpp
@@ -437,7 +437,7 @@ QV4::ReturnedValue QQmlNumberExtension::method_toLocaleString(QV4::SimpleCallCon
         if (!ctx->callData->args[1].isString())
             V4THROW_ERROR("Locale: Number.toLocaleString(): Invalid arguments");
         QV4::String *fs = ctx->callData->args[1].toString(ctx);
-        if (!fs->isEmpty())
+        if (fs->length())
             format = fs->toQString().at(0).unicode();
     }
     int prec = 2;
@@ -501,7 +501,7 @@ QV4::ReturnedValue QQmlNumberExtension::method_fromLocaleString(QV4::SimpleCallC
     }
 
     QV4::String *ns = ctx->callData->args[numberIdx].toString(ctx);
-    if (ns->isEmpty())
+    if (!ns->length())
         return QV4::Encode(Q_QNAN);
 
     bool ok = false;