Performance issue in QGraphicsItem::addParentItem while building the

scene bottom-up.

When adding n items, the depth was computed n² times. Adding lazy computation
fixes this performance issue.

Reviewed-by: Andreas

4 files changed, 56 insertions, 12 deletions

diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index 708ba09..1d52182 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -1010,7 +1010,7 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent)
     }
 
     // Resolve depth.
-    resolveDepth(parent ? parent->d_ptr->depth : -1);
+    invalidateDepthRecursively();
     dirtySceneTransform = 1;
 
     // Restore the sub focus chain.
@@ -4401,14 +4401,42 @@ bool QGraphicsItemPrivate::discardUpdateRequest(bool ignoreClipping, bool ignore
 
 /*!
     \internal
+*/
+int QGraphicsItemPrivate::depth() const
+{
+    if (itemDepth == -1)
+        const_cast<QGraphicsItemPrivate *>(this)->resolveDepth();
+
+    return itemDepth;
+}
 
-    Resolves the stacking depth of this object and all its children.
+/*!
+    \internal
 */
-void QGraphicsItemPrivate::resolveDepth(int parentDepth)
+void QGraphicsItemPrivate::invalidateDepthRecursively()
 {
-    depth = parentDepth + 1;
+    if (itemDepth == -1)
+        return;
+
+    itemDepth = -1;
     for (int i = 0; i < children.size(); ++i)
-        children.at(i)->d_ptr->resolveDepth(depth);
+        children.at(i)->d_ptr->invalidateDepthRecursively();
+}
+
+/*!
+    \internal
+
+    Resolves the stacking depth of this object and all its ancestors.
+*/
+void QGraphicsItemPrivate::resolveDepth()
+{
+    if (!parent)
+        itemDepth = 0;
+    else {
+        if (parent->d_ptr->itemDepth == -1)
+            parent->d_ptr->resolveDepth();
+        itemDepth = parent->d_ptr->itemDepth + 1;
+    }
 }
 
 /*!
@@ -5578,8 +5606,8 @@ QGraphicsItem *QGraphicsItem::commonAncestorItem(const QGraphicsItem *other) con
         return const_cast<QGraphicsItem *>(this);
     const QGraphicsItem *thisw = this;
     const QGraphicsItem *otherw = other;
-    int thisDepth = d_ptr->depth;
-    int otherDepth = other->d_ptr->depth;
+    int thisDepth = d_ptr->depth();
+    int otherDepth = other->d_ptr->depth();
     while (thisDepth > otherDepth) {
         thisw = thisw->d_ptr->parent;
         --thisDepth;
diff --git a/src/gui/graphicsview/qgraphicsitem_p.h b/src/gui/graphicsview/qgraphicsitem_p.h
index 43d690f..ae7feb2 100644
--- a/src/gui/graphicsview/qgraphicsitem_p.h
+++ b/src/gui/graphicsview/qgraphicsitem_p.h
@@ -123,7 +123,7 @@ public:
         transformData(0),
         index(-1),
         siblingIndex(-1),
-        depth(0),
+        itemDepth(-1),
         focusProxy(0),
         subFocusItem(0),
         imHints(Qt::ImhNone),
@@ -209,7 +209,9 @@ public:
     void setEnabledHelper(bool newEnabled, bool explicitly, bool update = true);
     bool discardUpdateRequest(bool ignoreClipping = false, bool ignoreVisibleBit = false,
                               bool ignoreDirtyBit = false, bool ignoreOpacity = false) const;
-    void resolveDepth(int parentDepth);
+    int depth() const;
+    void invalidateDepthRecursively();
+    void resolveDepth();
     void addChild(QGraphicsItem *child);
     void removeChild(QGraphicsItem *child);
     void setParentItemHelper(QGraphicsItem *parent);
@@ -419,7 +421,7 @@ public:
     QTransform sceneTransform;
     int index;
     int siblingIndex;
-    int depth;
+    int itemDepth;  // Lazily calculated when calling depth().
     QGraphicsItem *focusProxy;
     QList<QGraphicsItem **> focusProxyRefs;
     QGraphicsItem *subFocusItem;
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
index d68183c..a80cdca 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
@@ -419,8 +419,8 @@ bool QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(const QGra
 
     // Find common ancestor, and each item's ancestor closest to the common
     // ancestor.
-    int item1Depth = d1->depth;
-    int item2Depth = d2->depth;
+    int item1Depth = d1->depth();
+    int item2Depth = d2->depth();
     const QGraphicsItem *p = item1;
     const QGraphicsItem *t1 = item1;
     while (item1Depth > item2Depth && (p = p->d_ptr->parent)) {
diff --git a/tests/benchmarks/qgraphicsitem/tst_qgraphicsitem.cpp b/tests/benchmarks/qgraphicsitem/tst_qgraphicsitem.cpp
index 923838a..91dd28b 100644
--- a/tests/benchmarks/qgraphicsitem/tst_qgraphicsitem.cpp
+++ b/tests/benchmarks/qgraphicsitem/tst_qgraphicsitem.cpp
@@ -61,6 +61,7 @@ public slots:
 private slots:
     void setParentItem();
     void setParentItem_deep();
+    void setParentItem_deep_reversed();
     void deleteItemWithManyChildren();
     void setPos_data();
     void setPos();
@@ -113,6 +114,19 @@ void tst_QGraphicsItem::setParentItem_deep()
     }
 }
 
+void tst_QGraphicsItem::setParentItem_deep_reversed()
+{
+    QBENCHMARK {
+        QGraphicsRectItem *lastRect = new QGraphicsRectItem;
+        for (int i = 0; i < 100; ++i) {
+            QGraphicsRectItem *parentRect = new QGraphicsRectItem;
+            lastRect->setParentItem(parentRect);
+            lastRect = parentRect;
+        }
+        delete lastRect;
+    }
+}
+
 void tst_QGraphicsItem::deleteItemWithManyChildren()
 {
     QBENCHMARK {