QMetaEnum: avoid quadratic behavior in valueToKeys()

QByteArray (thankfully) doesn't have the prepend "optimization", so
prepend() is a linear operation, calling it in a loop thus makes the
algorithm quadratic.

To fix, simply remember the parts in a QVLA (an upper bound on the
size of which is easily calculated) and then build the result by
reverse-iterating over the QVLA.

This join_reversed() function is possibly useful elsewhere, but I left
it locally in the unnamed namespace to ease cherry-picking.

The new stringDataView() function is more universally useful, too, and
will be used in a subsequent other change. It return QL1S instead of
QByteArrayView because the latter is scheduled to become a non-string
type, and already lacks certain features (e.g. qTokenize() doesn't
work on QBA, due to lack of a Qt::CaseSensitivity argument in
QBA::indexOf()). It's also a Qt 6 addition, so not available in
5.15. We can revisit this decision later, when QBAV (or, possibly,
QU8SV) has caught up.

Amends 05e0dfa0060aab80afc696161226b2ab0cddfbf9.

Results indicate a ~2x speedup:

 PASS   : tst_QMetaEnum::valueToKeys(1 bits set)
-     0.00026 msecs per iteration (total: 70, iterations: 262144)
+     0.00017 msecs per iteration (total: 90, iterations: 524288)
 PASS   : tst_QMetaEnum::valueToKeys(2 bits set)
-     0.00037 msecs per iteration (total: 98, iterations: 262144)
+     0.00019 msecs per iteration (total: 52, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(3 bits set)
-     0.00040 msecs per iteration (total: 53, iterations: 131072)
+     0.00021 msecs per iteration (total: 56, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(4 bits set)
-     0.00047 msecs per iteration (total: 62, iterations: 131072)
+     0.00022 msecs per iteration (total: 60, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(5 bits set)
-     0.00048 msecs per iteration (total: 63, iterations: 131072)
+     0.00024 msecs per iteration (total: 64, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(6 bits set)
-     0.00061 msecs per iteration (total: 80, iterations: 131072)
+     0.00027 msecs per iteration (total: 71, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(7 bits set)
-     0.00063 msecs per iteration (total: 83, iterations: 131072)
+     0.00027 msecs per iteration (total: 73, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(8 bits set)
-     0.00069 msecs per iteration (total: 91, iterations: 131072)
+     0.00030 msecs per iteration (total: 81, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(9 bits set)
-     0.00070 msecs per iteration (total: 92, iterations: 131072)
+     0.00031 msecs per iteration (total: 83, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(10 bits set)
-     0.00074 msecs per iteration (total: 98, iterations: 131072)
+     0.00034 msecs per iteration (total: 91, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(11 bits set)
-     0.000762 msecs per iteration (total: 100, iterations: 131072)
+     0.00035 msecs per iteration (total: 92, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(12 bits set)
-     0.00088 msecs per iteration (total: 58, iterations: 65536)
+     0.000381 msecs per iteration (total: 100, iterations: 262144)
 PASS   : tst_QMetaEnum::valueToKeys(13 bits set)
-     0.00094 msecs per iteration (total: 62, iterations: 65536)
+     0.00038 msecs per iteration (total: 51, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(14 bits set)
-     0.00099 msecs per iteration (total: 65, iterations: 65536)
+     0.00041 msecs per iteration (total: 55, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(15 bits set)
-     0.0010 msecs per iteration (total: 67, iterations: 65536)
+     0.00042 msecs per iteration (total: 56, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(16 bits set)
-     0.0010 msecs per iteration (total: 70, iterations: 65536)
+     0.00044 msecs per iteration (total: 58, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(17 bits set)
-     0.0011 msecs per iteration (total: 73, iterations: 65536)
+     0.00046 msecs per iteration (total: 61, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(18 bits set)
-     0.0012 msecs per iteration (total: 79, iterations: 65536)
+     0.00048 msecs per iteration (total: 63, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(19 bits set)
-     0.0012 msecs per iteration (total: 79, iterations: 65536)
+     0.00051 msecs per iteration (total: 67, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(20 bits set)
-     0.0012 msecs per iteration (total: 80, iterations: 65536)
+     0.00054 msecs per iteration (total: 71, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(21 bits set)
-     0.0012 msecs per iteration (total: 83, iterations: 65536)
+     0.00090 msecs per iteration (total: 59, iterations: 65536)
 PASS   : tst_QMetaEnum::valueToKeys(22 bits set)
-     0.0012 msecs per iteration (total: 85, iterations: 65536)
+     0.00057 msecs per iteration (total: 76, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(23 bits set)
-     0.0013 msecs per iteration (total: 87, iterations: 65536)
+     0.00059 msecs per iteration (total: 78, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(24 bits set)
-     0.0014 msecs per iteration (total: 93, iterations: 65536)
+     0.00065 msecs per iteration (total: 86, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(25 bits set)
-     0.0014 msecs per iteration (total: 94, iterations: 65536)
+     0.00063 msecs per iteration (total: 83, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(26 bits set)
-     0.00028 msecs per iteration (total: 74, iterations: 262144)
+     0.00017 msecs per iteration (total: 94, iterations: 524288)
 PASS   : tst_QMetaEnum::valueToKeys(27 bits set)
-     0.0014 msecs per iteration (total: 98, iterations: 65536)
+     0.00063 msecs per iteration (total: 83, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(28 bits set)
-     0.0014 msecs per iteration (total: 96, iterations: 65536)
+     0.00065 msecs per iteration (total: 86, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(29 bits set)
-     0.0014 msecs per iteration (total: 98, iterations: 65536)
+     0.00064 msecs per iteration (total: 84, iterations: 131072)
 PASS   : tst_QMetaEnum::valueToKeys(30 bits set)
-     0.0014 msecs per iteration (total: 97, iterations: 65536)
+     0.00064 msecs per iteration (total: 84, iterations: 131072)

Change-Id: Ie456b71b39c118001987716e30642f08f5e8dcdb
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
(cherry picked from commit bd52059eef7c96031972b5bee03067f3cb0f038d)
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>

1 files changed, 32 insertions, 3 deletions

diff --git a/src/corelib/kernel/qmetaobject.cpp b/src/corelib/kernel/qmetaobject.cpp
index 76a01f938e..40da8a3e4e 100644
--- a/src/corelib/kernel/qmetaobject.cpp
+++ b/src/corelib/kernel/qmetaobject.cpp
@@ -166,6 +166,13 @@ static inline const QByteArray stringData(const QMetaObject *mo, int index)
     return data;
 }
 
+static inline QLatin1String stringDataView(const QMetaObject *mo, int index)
+{
+    const QByteArrayData &d = mo->d.stringdata[index];
+    const char *string = reinterpret_cast<const char *>(d.data());
+    return QLatin1String(string, d.size);
+}
+
 static inline const char *rawStringData(const QMetaObject *mo, int index)
 {
     return stringData(mo, index).data();
@@ -2819,6 +2826,28 @@ int QMetaEnum::keysToValue(const char *keys, bool *ok) const
     return value;
 }
 
+namespace
+{
+template <typename String, typename Container, typename Separator>
+void join_reversed(String &s, const Container &c, Separator sep)
+{
+    if (c.empty())
+        return;
+    qsizetype len = qsizetype(c.size()) - 1; // N - 1 separators
+    for (auto &e : c)
+        len += qsizetype(e.size()); // N parts
+    s.reserve(len);
+    bool first = true;
+    for (auto rit = c.rbegin(), rend = c.rend(); rit != rend; ++rit) {
+        const auto &e = *rit;
+        if (!first)
+            s.append(sep);
+        first = false;
+        s.append(e.data(), e.size());
+    }
+}
+} // unnamed namespace
+
 /*!
     Returns a byte array of '|'-separated keys that represents the
     given \a value.
@@ -2833,17 +2862,17 @@ QByteArray QMetaEnum::valueToKeys(int value) const
     const int offset = priv(mobj->d.data)->revision >= 8 ? 3 : 2;
     int count = mobj->d.data[handle + offset];
     int data = mobj->d.data[handle + offset + 1];
+    QVarLengthArray<QLatin1String, sizeof(int) * CHAR_BIT> parts;
     int v = value;
     // reverse iterate to ensure values like Qt::Dialog=0x2|Qt::Window are processed first.
     for (int i = count - 1; i >= 0; --i) {
         int k = mobj->d.data[data + 2*i + 1];
         if ((k != 0 && (v & k) == k ) ||  (k == value))  {
             v = v & ~k;
-            if (!keys.isEmpty())
-                keys.prepend('|');
-            keys.prepend(stringData(mobj, mobj->d.data[data + 2*i]));
+            parts.push_back(stringDataView(mobj, mobj->d.data[data + 2 * i]));
         }
     }
+    join_reversed(keys, parts, '|');
     return keys;
 }