From 99b89d30fa5484c5d1f3cbda828648c28af4fb7d Mon Sep 17 00:00:00 2001
From: Erik Verbruggen <erik.verbruggen@qt.io>
Date: Fri, 12 Jan 2018 12:19:20 +0100
Subject: Prevent O(n^2) behavior when calling QObject::deleteLater

When a deleteLater event is queued, a check if done if the same event
for the same receiver is queued before by scanning all pending events.
This leads to quadratic behavior, which is quite noticeable. By using
an unused bit in QObjectData, this can be prevented. Now the duplicate
event scanning in QCoreApplication is only done for the quit event.

Task-number: QTBUG-65712
Change-Id: Ie505acbbec802f91ebd0b94ac067e362c2476113
Reviewed-by: Erik Verbruggen <erik.verbruggen@qt.io>
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
---
 src/corelib/kernel/qcoreapplication.cpp | 41 ++++++++++++++++++++++-----------
 src/corelib/kernel/qobject.cpp          |  1 +
 src/corelib/kernel/qobject.h            |  3 ++-
 3 files changed, 31 insertions(+), 14 deletions(-)

diff --git a/src/corelib/kernel/qcoreapplication.cpp b/src/corelib/kernel/qcoreapplication.cpp
index c0ace26f28..ee269ef8de 100644
--- a/src/corelib/kernel/qcoreapplication.cpp
+++ b/src/corelib/kernel/qcoreapplication.cpp
@@ -1426,6 +1426,9 @@ void QCoreApplication::postEvent(QObject *receiver, QEvent *event, int priority)
         return;
     }
 
+    if (event->type() == QEvent::DeferredDelete)
+        receiver->d_ptr->deleteLaterCalled = true;
+
     if (event->type() == QEvent::DeferredDelete && data == QThreadData::current()) {
         // remember the current running eventloop for DeferredDelete
         // events posted in the receiver's thread.
@@ -1485,22 +1488,34 @@ bool QCoreApplication::compressEvent(QEvent *event, QObject *receiver, QPostEven
                 return true;
             }
         }
-    } else
-#endif
-        if ((event->type() == QEvent::DeferredDelete
-             || event->type() == QEvent::Quit)
-            && receiver->d_func()->postedEvents > 0) {
-            for (int i = 0; i < postedEvents->size(); ++i) {
-                const QPostEvent &cur = postedEvents->at(i);
-                if (cur.receiver != receiver
+        return false;
+    }
+#endif
+
+    if (event->type() == QEvent::DeferredDelete) {
+        if (receiver->d_ptr->deleteLaterCalled) {
+            // there was a previous DeferredDelete event, so we can drop the new one
+            delete event;
+            return true;
+        }
+        // deleteLaterCalled is set to true in postedEvents when queueing the very first
+        // deferred deletion event.
+        return false;
+    }
+
+    if (event->type() == QEvent::Quit && receiver->d_func()->postedEvents > 0) {
+        for (int i = 0; i < postedEvents->size(); ++i) {
+            const QPostEvent &cur = postedEvents->at(i);
+            if (cur.receiver != receiver
                     || cur.event == 0
                     || cur.event->type() != event->type())
-                    continue;
-                // found an event for this receiver
-                delete event;
-                return true;
-            }
+                continue;
+            // found an event for this receiver
+            delete event;
+            return true;
         }
+    }
+
     return false;
 }
 
diff --git a/src/corelib/kernel/qobject.cpp b/src/corelib/kernel/qobject.cpp
index 086b8a51ba..57711389c4 100644
--- a/src/corelib/kernel/qobject.cpp
+++ b/src/corelib/kernel/qobject.cpp
@@ -230,6 +230,7 @@ QObjectPrivate::QObjectPrivate(int version)
     connectedSignals[0] = connectedSignals[1] = 0;
     metaObject = 0;
     isWindow = false;
+    deleteLaterCalled = false;
 }
 
 QObjectPrivate::~QObjectPrivate()
diff --git a/src/corelib/kernel/qobject.h b/src/corelib/kernel/qobject.h
index 6941c55896..dea17ed530 100644
--- a/src/corelib/kernel/qobject.h
+++ b/src/corelib/kernel/qobject.h
@@ -106,7 +106,8 @@ public:
     uint sendChildEvents : 1;
     uint receiveChildEvents : 1;
     uint isWindow : 1; //for QWindow
-    uint unused : 25;
+    uint deleteLaterCalled : 1;
+    uint unused : 24;
     int postedEvents;
     QDynamicMetaObjectData *metaObject;
     QMetaObject *dynamicMetaObject() const;
-- 
cgit v1.2.3