From 6026436f0de6020252410c021e0745a22599b159 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
---
 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 774a6d3..ceb810b 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 69e4d5b..f6ec0aa 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 1944219..53fd9b6 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