Reduce number of allocations when constructing text nodes

In cases where you have a huge number of text elements that
can be merged, we would do a lot of reallocations (one per
node that would be merged into another). As the number of
merges grew, this seemed to converge at about 50% of the time
spent in updatePaintNode() in the text classes.

We can almost eliminate this cost by only doing one realloc
per node that will actually end up in the scene graph.

This patch does a first pass where it simply bundles together
nodes that can be merged. Then it does a second pass where it
actually merges the nodes. In this second pass it can easily
precount the required size of the arrays and we can limit
it to a single realloc.

Task-number: QTBUG-37365
Change-Id: I4e44c01cd83df39304cbbce34f3b8f773763e091
Reviewed-by: Michael Brasser <michael.brasser@live.com>

1 files changed, 61 insertions, 36 deletions

diff --git a/src/quick/items/qquicktextnodeengine.cpp b/src/quick/items/qquicktextnodeengine.cpp
index 369570f657..14d305ad50 100644
--- a/src/quick/items/qquicktextnodeengine.cpp
+++ b/src/quick/items/qquicktextnodeengine.cpp
@@ -670,61 +670,86 @@ void QQuickTextNodeEngine::addFrameDecorations(QTextDocument *document, QTextFra
     }
 }
 
-void  QQuickTextNodeEngine::addToSceneGraph(QQuickTextNode *parentNode,
-                                            QQuickText::TextStyle style,
-                                            const QColor &styleColor)
+uint qHash(const QQuickTextNodeEngine::BinaryTreeNodeKey &key)
 {
-    if (m_currentLine.isValid())
-        processCurrentLine();
+    // Just use the default hash for pairs
+    return qHash(qMakePair(key.fontEngine, qMakePair(key.clipNode,
+                                                     qMakePair(key.color, key.selectionState))));
+}
+
+void QQuickTextNodeEngine::mergeProcessedNodes(QList<BinaryTreeNode *> *regularNodes,
+                                               QList<BinaryTreeNode *> *imageNodes)
+{
+    QMultiHash<BinaryTreeNodeKey, BinaryTreeNode *> map;
 
-    // Then, go through all the nodes for all lines and combine all QGlyphRuns with a common
-    // font, selection state and clip node.
-    typedef QPair<QFontEngine *, QPair<QQuickDefaultClipNode *, QPair<QRgb, int> > > KeyType;
-    QHash<KeyType, BinaryTreeNode *> map;
-    QList<BinaryTreeNode *> nodes;
-    QList<BinaryTreeNode *> imageNodes;
     for (int i = 0; i < m_processedNodes.size(); ++i) {
         BinaryTreeNode *node = m_processedNodes.data() + i;
 
         if (node->image.isNull()) {
-            QGlyphRun glyphRun = node->glyphRun;
-            QRawFont rawFont = glyphRun.rawFont();
+            QRawFont rawFont = node->glyphRun.rawFont();
             QRawFontPrivate *rawFontD = QRawFontPrivate::get(rawFont);
-
             QFontEngine *fontEngine = rawFontD->fontEngine;
 
-            KeyType key(qMakePair(fontEngine,
-                                  qMakePair(node->clipNode,
-                                            qMakePair(node->color.rgba(), int(node->selectionState)))));
-
-            BinaryTreeNode *otherNode = map.value(key, 0);
-            if (otherNode != 0) {
-                QGlyphRun &otherGlyphRun = otherNode->glyphRun;
+            BinaryTreeNodeKey key(fontEngine,
+                                  node->clipNode,
+                                  node->color.rgba(),
+                                  int(node->selectionState));
+            map.insertMulti(key, node);
+        } else {
+            imageNodes->append(node);
+        }
+    }
 
-                QVector<quint32> otherGlyphIndexes = otherGlyphRun.glyphIndexes();
-                QVector<QPointF> otherGlyphPositions = otherGlyphRun.positions();
+    QMultiHash<BinaryTreeNodeKey, BinaryTreeNode *>::const_iterator it = map.constBegin();
+    while (it != map.constEnd()) {
+        BinaryTreeNode *primaryNode = it.value();
+        regularNodes->append(primaryNode);
 
-                otherGlyphIndexes += glyphRun.glyphIndexes();
+        int count = 0;
+        QMultiHash<BinaryTreeNodeKey, BinaryTreeNode *>::const_iterator jt;
+        for (jt = it; jt != map.constEnd() && jt.key() == it.key(); ++jt)
+            count += jt.value()->glyphRun.glyphIndexes().size();
 
-                QVector<QPointF> glyphPositions = glyphRun.positions();
-                otherGlyphPositions.reserve(otherGlyphPositions.size() + glyphPositions.size());
-                for (int j = 0; j < glyphPositions.size(); ++j) {
-                    otherGlyphPositions += glyphPositions.at(j) + (node->position - otherNode->position);
-                }
+        if (count != primaryNode->glyphRun.glyphIndexes().size()) {
+            QGlyphRun &glyphRun = primaryNode->glyphRun;
+            QVector<quint32> glyphIndexes = glyphRun.glyphIndexes();
+            glyphIndexes.reserve(count);
 
-                otherGlyphRun.setGlyphIndexes(otherGlyphIndexes);
-                otherGlyphRun.setPositions(otherGlyphPositions);
+            QVector<QPointF> glyphPositions = glyphRun.positions();
+            glyphPositions.reserve(count);
 
-                otherNode->ranges += node->ranges;
+            for (jt = it + 1; jt != map.constEnd() && jt.key() == it.key(); ++jt) {
+                BinaryTreeNode *otherNode = jt.value();
+                glyphIndexes += otherNode->glyphRun.glyphIndexes();
+                primaryNode->ranges += otherNode->ranges;
 
-            } else {
-                map.insert(key, node);
-                nodes.append(node);
+                QVector<QPointF> otherPositions = otherNode->glyphRun.positions();
+                for (int j = 0; j < otherPositions.size(); ++j)
+                    glyphPositions += otherPositions.at(j) + (otherNode->position - primaryNode->position);
             }
+            it = jt;
+
+            Q_ASSERT(glyphPositions.size() == count);
+            Q_ASSERT(glyphIndexes.size() == count);
+
+            glyphRun.setGlyphIndexes(glyphIndexes);
+            glyphRun.setPositions(glyphPositions);
         } else {
-            imageNodes.append(node);
+            ++it;
         }
     }
+}
+
+void  QQuickTextNodeEngine::addToSceneGraph(QQuickTextNode *parentNode,
+                                            QQuickText::TextStyle style,
+                                            const QColor &styleColor)
+{
+    if (m_currentLine.isValid())
+        processCurrentLine();
+
+    QList<BinaryTreeNode *> nodes;
+    QList<BinaryTreeNode *> imageNodes;
+    mergeProcessedNodes(&nodes, &imageNodes);
 
     for (int i = 0; i < m_backgrounds.size(); ++i) {
         const QRectF &rect = m_backgrounds.at(i).first;