From 6ae8e79cff25025ffa6f3c11c4aa31736cba6c03 Mon Sep 17 00:00:00 2001
From: Alexis Menard <alexis.menard@nokia.com>
Date: Thu, 7 Jan 2010 16:13:14 +0100
Subject: Fix performance regression in _q_polishItems.

QSet is a hash internally, using Iterator::begin while erasing elements
inside the set might create holes and then the complexity increase.

We now use the return value of erase (the next element) so the
complexity is linear.

For those who create/delete item in the polish event (BAD), _q_polishItem
might be slower than the normal call.

Task-number:QTBUG-6958
Reviewed-by:olivier
(cherry picked from commit 6026436f0de6020252410c021e0745a22599b159)
---
 src/gui/graphicsview/qgraphicsscene.cpp                | 17 +++++++++++------
 src/gui/graphicsview/qgraphicsscene_p.h                |  1 +
 tests/benchmarks/qgraphicsscene/tst_qgraphicsscene.cpp | 17 +++++++++++++++++
 3 files changed, 29 insertions(+), 6 deletions(-)

diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 2788a96..f60b62e 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -292,6 +292,7 @@ QGraphicsScenePrivate::QGraphicsScenePrivate()
       processDirtyItemsEmitted(false),
       selectionChanging(0),
       needSortTopLevelItems(true),
+      unpolishedItemsModified(true),
       holesInTopLevelSiblingIndex(false),
       topLevelSequentialOrdering(true),
       scenePosDescendantsUpdatePending(false),
@@ -428,12 +429,12 @@ void QGraphicsScenePrivate::unregisterTopLevelItem(QGraphicsItem *item)
 */
 void QGraphicsScenePrivate::_q_polishItems()
 {
-    QSet<QGraphicsItem *>::Iterator it;
+    QSet<QGraphicsItem *>::Iterator it = unpolishedItems.begin();
     const QVariant booleanTrueVariant(true);
     while (!unpolishedItems.isEmpty()) {
-        it = unpolishedItems.begin();
         QGraphicsItem *item = *it;
-        unpolishedItems.erase(it);
+        it = unpolishedItems.erase(it);
+        unpolishedItemsModified = false;
         if (!item->d_ptr->explicitlyHidden) {
             item->itemChange(QGraphicsItem::ItemVisibleChange, booleanTrueVariant);
             item->itemChange(QGraphicsItem::ItemVisibleHasChanged, booleanTrueVariant);
@@ -442,6 +443,8 @@ void QGraphicsScenePrivate::_q_polishItems()
             QEvent event(QEvent::Polish);
             QApplication::sendEvent((QGraphicsWidget *)item, &event);
         }
+        if (unpolishedItemsModified)
+            it = unpolishedItems.begin();
     }
 }
 
@@ -636,6 +639,7 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item)
     hoverItems.removeAll(item);
     cachedItemsUnderMouse.removeAll(item);
     unpolishedItems.remove(item);
+    unpolishedItemsModified = true;
     resetDirtyItem(item);
 
     //We remove all references of item from the sceneEventFilter arrays
@@ -2577,9 +2581,10 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
     item->d_ptr->resolveFont(d->font.resolve());
     item->d_ptr->resolvePalette(d->palette.resolve());
 
-   if (d->unpolishedItems.isEmpty())
-       QMetaObject::invokeMethod(this, "_q_polishItems", Qt::QueuedConnection);
-   d->unpolishedItems.insert(item);
+    if (d->unpolishedItems.isEmpty())
+        QMetaObject::invokeMethod(this, "_q_polishItems", Qt::QueuedConnection);
+    d->unpolishedItems.insert(item);
+    d->unpolishedItemsModified = true;
 
     // Reenable selectionChanged() for individual items
     --d->selectionChanging;
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index ff163ac..2450746 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -111,6 +111,7 @@ public:
     QSet<QGraphicsItem *> unpolishedItems;
     QList<QGraphicsItem *> topLevelItems;
     bool needSortTopLevelItems;
+    bool unpolishedItemsModified;
     bool holesInTopLevelSiblingIndex;
     bool topLevelSequentialOrdering;
 
diff --git a/tests/benchmarks/qgraphicsscene/tst_qgraphicsscene.cpp b/tests/benchmarks/qgraphicsscene/tst_qgraphicsscene.cpp
index 50d1158..93abef0 100644
--- a/tests/benchmarks/qgraphicsscene/tst_qgraphicsscene.cpp
+++ b/tests/benchmarks/qgraphicsscene/tst_qgraphicsscene.cpp
@@ -64,6 +64,7 @@ private slots:
     void addItem();
     void itemAt_data();
     void itemAt();
+    void initialShow();
 };
 
 tst_QGraphicsScene::tst_QGraphicsScene()
@@ -227,5 +228,21 @@ void tst_QGraphicsScene::itemAt()
     qApp->processEvents();
 }
 
+void tst_QGraphicsScene::initialShow()
+{
+    QGraphicsScene scene;
+
+    QBENCHMARK {
+        for (int y = 0; y < 30000; ++y) {
+            QGraphicsRectItem *item = new QGraphicsRectItem(0, 0, 50, 50);
+            item->setPos((y/2) * item->rect().width(), (y/2) * item->rect().height());
+            scene.addItem(item);
+        }
+        scene.itemAt(0, 0); // triggers indexing
+        //This call polish the items so we bench their processing too.
+        qApp->processEvents();
+    }
+}
+
 QTEST_MAIN(tst_QGraphicsScene)
 #include "tst_qgraphicsscene.moc"
-- 
cgit v0.12