From 31012df705c37503be00f0ddc2c323e73fd28067 Mon Sep 17 00:00:00 2001
From: Andre de la Rocha <andre.rocha@qt.io>
Date: Mon, 2 Sep 2019 16:46:07 +0200
Subject: Fix QGraphicsScene::update() performance

A previous fix has caused a performance degradation while adding a
check for avoiding adding duplicated rectangles to the update list.
This patch fixes it by using a std::set instead of a QList, avoiding
duplication while using an O(log N) operation, instead of the O(N)
used before.

Fixes: QTBUG-77952
Change-Id: Ifa9fbf110e0bad60ee02a42d91281981fd98ceab
Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
---
 src/widgets/graphicsview/qgraphicsscene.cpp             | 13 ++++++++++---
 src/widgets/graphicsview/qgraphicsscene_p.h             | 17 ++++++++++++++++-
 .../graphicsview/qgraphicsscene/tst_qgraphicsscene.cpp  |  2 --
 3 files changed, 26 insertions(+), 6 deletions(-)

diff --git a/src/widgets/graphicsview/qgraphicsscene.cpp b/src/widgets/graphicsview/qgraphicsscene.cpp
index 5238ea2f5c..03717d5d1a 100644
--- a/src/widgets/graphicsview/qgraphicsscene.cpp
+++ b/src/widgets/graphicsview/qgraphicsscene.cpp
@@ -386,7 +386,15 @@ void QGraphicsScenePrivate::_q_emitUpdated()
 
     // Notify the changes to anybody interested.
     QList<QRectF> oldUpdatedRects;
-    oldUpdatedRects = updateAll ? (QList<QRectF>() << q->sceneRect()) : updatedRects;
+    if (updateAll) {
+        oldUpdatedRects << q->sceneRect();
+    } else {
+        // Switch to a ranged constructor in Qt 6...
+        oldUpdatedRects.reserve(int(updatedRects.size()));
+        std::copy(updatedRects.cbegin(), updatedRects.cend(),
+                  std::back_inserter(oldUpdatedRects));
+    }
+
     updateAll = false;
     updatedRects.clear();
     emit q->changed(oldUpdatedRects);
@@ -3219,8 +3227,7 @@ void QGraphicsScene::update(const QRectF &rect)
                     view->d_func()->updateRectF(rect);
             }
         } else {
-            if (!d->updatedRects.contains(rect))
-                d->updatedRects << rect;
+            d->updatedRects.insert(rect);
         }
     }
 
diff --git a/src/widgets/graphicsview/qgraphicsscene_p.h b/src/widgets/graphicsview/qgraphicsscene_p.h
index a2d13436fc..14bafe6678 100644
--- a/src/widgets/graphicsview/qgraphicsscene_p.h
+++ b/src/widgets/graphicsview/qgraphicsscene_p.h
@@ -69,6 +69,9 @@
 #include <QtWidgets/qstyle.h>
 #include <QtWidgets/qstyleoption.h>
 
+#include <set>
+#include <tuple>
+
 QT_REQUIRE_CONFIG(graphicsview);
 
 QT_BEGIN_NAMESPACE
@@ -122,7 +125,19 @@ public:
     QRectF growingItemsBoundingRect;
 
     void _q_emitUpdated();
-    QList<QRectF> updatedRects;
+
+    struct UpdatedRectsCmp
+    {
+        bool operator() (const QRectF &a, const QRectF &b) const noexcept
+        {
+            return std::make_tuple(a.y(), a.x(), a.height(), a.width())
+                    < std::make_tuple(b.y(), b.x(), b.height(), b.width());
+        }
+    };
+
+    // std::set was used here instead of std::unordered_set due to requiring only a comparator and
+    // showing equivalent performance in empirical measurements within the ranges of interest...
+    std::set<QRectF, UpdatedRectsCmp> updatedRects;
 
     QPainterPath selectionArea;
     int selectionChanging;
diff --git a/tests/auto/widgets/graphicsview/qgraphicsscene/tst_qgraphicsscene.cpp b/tests/auto/widgets/graphicsview/qgraphicsscene/tst_qgraphicsscene.cpp
index 46f1d5df5c..4f8741a5aa 100644
--- a/tests/auto/widgets/graphicsview/qgraphicsscene/tst_qgraphicsscene.cpp
+++ b/tests/auto/widgets/graphicsview/qgraphicsscene/tst_qgraphicsscene.cpp
@@ -3685,8 +3685,6 @@ void tst_QGraphicsScene::changedSignal()
     qApp->processEvents();
     QCOMPARE(cl.changes.size(), 2);
     QCOMPARE(cl.changes.at(1).size(), 2);
-    QCOMPARE(cl.changes.at(1).first(), QRectF(0, 0, 10, 10));
-    QCOMPARE(cl.changes.at(1).last(), QRectF(20, 0, 10, 10));
 
     QCOMPARE(scene.sceneRect(), QRectF(0, 0, 30, 10));
 
-- 
cgit v1.2.3