QString: optimize multiArg()

The function used a QMap<int,int> to map the %n's to the index
in the args array.

By way of construction, the key was sorted in ascending order
while the values, initially all -1, were later reassigned to be
0...map.size()-1, ie. std::iota().

The only information this data structure stores is therefore
the sorted %n's. For that, a sorted vector is a vastly superior
data structure.

Go one step further and use QVarLengthArray to avoid
allocating any memory for the common case of just a few
placeholders.

As an artifact of the underlying refactoring, the management
of that data structure has been moved to a separate class,
ArgMapper.

Runtime for the following test from tst_qstring:

    QString str("%1 %2 %3 %4 %5 %6 %7 %8 %9 foo %10 %11 bar"); // not timed
    str = str.arg("one", "2", "3", "4", "5", "6", "7", "8", "9");
    str = str.arg("ahoy", "there");

went down from 2.2us to 1.5us.

Change-Id: Ic552615fbac646b78ba05eb4e3215e63d202fd94
Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>

1 files changed, 48 insertions, 18 deletions

diff --git a/src/corelib/tools/qstring.cpp b/src/corelib/tools/qstring.cpp
index 54d00f3e63..4589d76279 100644
--- a/src/corelib/tools/qstring.cpp
+++ b/src/corelib/tools/qstring.cpp
@@ -7600,49 +7600,79 @@ static int getEscape(const QChar *uc, int *pos, int len, int maxNumber = 999)
     return -1;
 }
 
+namespace {
+class ArgMapper {
+    QVarLengthArray<int, 16> argPosToNumberMap; // maps from argument position to number
+public:
+    void found(int n) { argPosToNumberMap.push_back(n); }
+
+    struct AssignmentResult {
+        int numArgs;
+        int lastNumber;
+    };
+
+    AssignmentResult assignArgumentNumberToEachOfTheNs(int numArgs)
+    {
+        std::sort(argPosToNumberMap.begin(), argPosToNumberMap.end());
+        argPosToNumberMap.erase(std::unique(argPosToNumberMap.begin(), argPosToNumberMap.end()),
+                                argPosToNumberMap.end());
+
+        if (argPosToNumberMap.size() > numArgs)
+            argPosToNumberMap.resize(numArgs);
+
+        int lastNumber = argPosToNumberMap.empty() ? -1 : argPosToNumberMap.back();
+        int arg = argPosToNumberMap.size();
+
+        const AssignmentResult result = {arg, lastNumber};
+        return result;
+    }
+
+    int numberToArgsIndex(int number) const
+    {
+        if (number != -1) {
+            const int * const it = std::find(argPosToNumberMap.begin(), argPosToNumberMap.end(), number);
+            return it == argPosToNumberMap.end() ? -1 : it - argPosToNumberMap.begin();
+        } else {
+            return -1;
+        }
+    }
+};
+} // unnamed namespace
+
 QString QString::multiArg(int numArgs, const QString **args) const
 {
     QString result;
-    QMap<int, int> numbersUsed;
+    ArgMapper mapper;
     const QChar *uc = (const QChar *) d->data();
     const int len = d->size;
     const int end = len - 1;
-    int lastNumber = -1;
     int i = 0;
 
-    // populate the numbersUsed map with the %n's that actually occur in the string
+    // populate the arg-mapper with the %n's that actually occur in the string
     while (i < end) {
         if (uc[i] == QLatin1Char('%')) {
             int number = getEscape(uc, &i, len);
             if (number != -1) {
-                numbersUsed.insert(number, -1);
+                mapper.found(number);
                 continue;
             }
         }
         ++i;
     }
 
-    // assign an argument number to each of the %n's
-    QMap<int, int>::iterator j = numbersUsed.begin();
-    QMap<int, int>::iterator jend = numbersUsed.end();
-    int arg = 0;
-    while (j != jend && arg < numArgs) {
-        *j = arg++;
-        lastNumber = j.key();
-        ++j;
-    }
+    const ArgMapper::AssignmentResult r = mapper.assignArgumentNumberToEachOfTheNs(numArgs);
 
     // sanity
-    if (numArgs > arg) {
-        qWarning("QString::arg: %d argument(s) missing in %s", numArgs - arg, toLocal8Bit().data());
-        numArgs = arg;
+    if (numArgs > r.numArgs) {
+        qWarning("QString::arg: %d argument(s) missing in %s", numArgs - r.numArgs, toLocal8Bit().data());
+        numArgs = r.numArgs;
     }
 
     i = 0;
     while (i < len) {
         if (uc[i] == QLatin1Char('%') && i != end) {
-            int number = getEscape(uc, &i, len, lastNumber);
-            int arg = numbersUsed[number];
+            int number = getEscape(uc, &i, len, r.lastNumber);
+            int arg = mapper.numberToArgsIndex(number);
             if (number != -1 && arg != -1) {
                 result += *args[arg];
                 continue;