Improve performance on touch event delivery.

We continuously constructed and sorted the paint ordered items for every
touch event (and paint), even though the list in most cases is identical
to the childItems list, and when it is different it rarely changes.

Detect when we can just use the childItems list directly, and otherwise
cache the ordered items list.

Change-Id: I5db0f19fc021d0c95aa6f8372ae47e6ce138d5ad
Reviewed-by: Michael Brasser <michael.brasser@nokia.com>

6 files changed, 188 insertions, 8 deletions

diff --git a/src/declarative/items/qquickitem.cpp b/src/declarative/items/qquickitem.cpp
index 294edad842..e020a0088c 100644
--- a/src/declarative/items/qquickitem.cpp
+++ b/src/declarative/items/qquickitem.cpp
@@ -1903,6 +1903,7 @@ void QQuickItem::stackBefore(const QQuickItem *sibling)
     parentPrivate->childItems.insert(siblingIndex, this);
 
     parentPrivate->dirty(QQuickItemPrivate::ChildrenStackingChanged);
+    parentPrivate->markSortedChildrenDirty(this);
 
     for (int ii = qMin(siblingIndex, myIndex); ii < parentPrivate->childItems.count(); ++ii)
         QQuickItemPrivate::get(parentPrivate->childItems.at(ii))->siblingOrderChanged();
@@ -1933,6 +1934,7 @@ void QQuickItem::stackAfter(const QQuickItem *sibling)
     parentPrivate->childItems.insert(siblingIndex + 1, this);
 
     parentPrivate->dirty(QQuickItemPrivate::ChildrenStackingChanged);
+    parentPrivate->markSortedChildrenDirty(this);
 
     for (int ii = qMin(myIndex, siblingIndex + 1); ii < parentPrivate->childItems.count(); ++ii)
         QQuickItemPrivate::get(parentPrivate->childItems.at(ii))->siblingOrderChanged();
@@ -1965,11 +1967,27 @@ static bool itemZOrder_sort(QQuickItem *lhs, QQuickItem *rhs)
 
 QList<QQuickItem *> QQuickItemPrivate::paintOrderChildItems() const
 {
-    // XXX todo - optimize, don't sort and return items that are
-    // ignored anyway, like invisible or disabled items.
-    QList<QQuickItem *> items = childItems;
-    qStableSort(items.begin(), items.end(), itemZOrder_sort);
-    return items;
+    if (sortedChildItems)
+        return *sortedChildItems;
+
+    // If none of the items have set Z then the paint order list is the same as
+    // the childItems list.  This is by far the most common case.
+    bool haveZ = false;
+    for (int i = 0; i < childItems.count(); ++i) {
+        if (QQuickItemPrivate::get(childItems.at(i))->z != 0.) {
+            haveZ = true;
+            break;
+        }
+    }
+    if (haveZ) {
+        sortedChildItems = new QList<QQuickItem*>(childItems);
+        qStableSort(sortedChildItems->begin(), sortedChildItems->end(), itemZOrder_sort);
+        return *sortedChildItems;
+    }
+
+    sortedChildItems = const_cast<QList<QQuickItem*>*>(&childItems);
+
+    return childItems;
 }
 
 void QQuickItemPrivate::addChild(QQuickItem *child)
@@ -1980,6 +1998,7 @@ void QQuickItemPrivate::addChild(QQuickItem *child)
 
     childItems.append(child);
 
+    markSortedChildrenDirty(child);
     dirty(QQuickItemPrivate::ChildrenChanged);
 
     itemChange(QQuickItem::ItemChildAddedChange, child);
@@ -1996,6 +2015,7 @@ void QQuickItemPrivate::removeChild(QQuickItem *child)
     childItems.removeOne(child);
     Q_ASSERT(!childItems.contains(child));
 
+    markSortedChildrenDirty(child);
     dirty(QQuickItemPrivate::ChildrenChanged);
 
     itemChange(QQuickItem::ItemChildRemovedChange, child);
@@ -2191,7 +2211,7 @@ QQuickItemPrivate::QQuickItemPrivate()
   inheritedLayoutMirror(false), effectiveLayoutMirror(false), isMirrorImplicit(true),
   inheritMirrorFromParent(false), inheritMirrorFromItem(false), childrenDoNotOverlap(false),
 
-  canvas(0), parentItem(0),
+  canvas(0), parentItem(0), sortedChildItems(&childItems),
 
   subFocusItem(0),
 
@@ -2210,6 +2230,12 @@ QQuickItemPrivate::QQuickItemPrivate()
 {
 }
 
+QQuickItemPrivate::~QQuickItemPrivate()
+{
+    if (sortedChildItems != &childItems)
+        delete sortedChildItems;
+}
+
 void QQuickItemPrivate::init(QQuickItem *parent)
 {
 #ifndef QT_NO_DEBUG
@@ -3518,8 +3544,10 @@ void QQuickItem::setZ(qreal v)
     d->z = v;
 
     d->dirty(QQuickItemPrivate::ZValue);
-    if (d->parentItem)
+    if (d->parentItem) {
         QQuickItemPrivate::get(d->parentItem)->dirty(QQuickItemPrivate::ChildrenStackingChanged);
+        QQuickItemPrivate::get(d->parentItem)->markSortedChildrenDirty(this);
+    }
 
     emit zChanged();
 }
diff --git a/src/declarative/items/qquickitem_p.h b/src/declarative/items/qquickitem_p.h
index 47f86c48aa..38e5d154f8 100644
--- a/src/declarative/items/qquickitem_p.h
+++ b/src/declarative/items/qquickitem_p.h
@@ -139,6 +139,7 @@ public:
     static const QQuickItemPrivate* get(const QQuickItem *item) { return item->d_func(); }
 
     QQuickItemPrivate();
+    ~QQuickItemPrivate();
     void init(QQuickItem *parent);
 
     QDeclarativeListProperty<QObject> data();
@@ -262,11 +263,22 @@ public:
 
     QQuickItem *parentItem;
     QList<QQuickItem *> childItems;
+    mutable QList<QQuickItem *> *sortedChildItems;
     QList<QQuickItem *> paintOrderChildItems() const;
     void addChild(QQuickItem *);
     void removeChild(QQuickItem *);
     void siblingOrderChanged();
 
+    inline void markSortedChildrenDirty(QQuickItem *child) {
+        // If sortedChildItems == &childItems then all in childItems have z == 0
+        // and we don't need to invalidate if the changed item also has z == 0.
+        if (child->z() != 0. || sortedChildItems != &childItems) {
+            if (sortedChildItems != &childItems)
+                delete sortedChildItems;
+            sortedChildItems = 0;
+        }
+    }
+
     class InitializationState {
     public:
         QQuickItem *getFocusScope(QQuickItem *item);
diff --git a/tests/auto/declarative/qquickitem/data/order.1.qml b/tests/auto/declarative/qquickitem/data/order.1.qml
new file mode 100644
index 0000000000..963288b257
--- /dev/null
+++ b/tests/auto/declarative/qquickitem/data/order.1.qml
@@ -0,0 +1,7 @@
+import QtQuick 2.0
+
+Item {
+    Item { objectName: "1" }
+    Item { objectName: "2" }
+    Item { objectName: "3" }
+}
diff --git a/tests/auto/declarative/qquickitem/data/order.2.qml b/tests/auto/declarative/qquickitem/data/order.2.qml
new file mode 100644
index 0000000000..5609c77e28
--- /dev/null
+++ b/tests/auto/declarative/qquickitem/data/order.2.qml
@@ -0,0 +1,7 @@
+import QtQuick 2.0
+
+Item {
+    Item { objectName: "1" }
+    Item { objectName: "2"; z: 1.0 }
+    Item { objectName: "3" }
+}
diff --git a/tests/auto/declarative/qquickitem/qquickitem.pro b/tests/auto/declarative/qquickitem/qquickitem.pro
index c1c7b825f9..f484bae014 100644
--- a/tests/auto/declarative/qquickitem/qquickitem.pro
+++ b/tests/auto/declarative/qquickitem/qquickitem.pro
@@ -4,5 +4,9 @@ SOURCES += tst_qquickitem.cpp
 
 macx:CONFIG -= app_bundle
 
+testDataFiles.files = data
+testDataFiles.path = .
+DEPLOYMENT += testDataFiles
+
 CONFIG += parallel_test
-QT += core-private gui-private declarative-private widgets testlib
+QT += core-private gui-private v8-private declarative-private widgets testlib
diff --git a/tests/auto/declarative/qquickitem/tst_qquickitem.cpp b/tests/auto/declarative/qquickitem/tst_qquickitem.cpp
index a5f908ce86..01f9240016 100644
--- a/tests/auto/declarative/qquickitem/tst_qquickitem.cpp
+++ b/tests/auto/declarative/qquickitem/tst_qquickitem.cpp
@@ -43,10 +43,13 @@
 
 #include "qquickitem.h"
 #include "qquickcanvas.h"
+#include "qquickview.h"
 #include <QtWidgets/QGraphicsSceneMouseEvent>
 #include "private/qquickfocusscope_p.h"
+#include "private/qquickitem_p.h"
 #include <QDebug>
 #include <QTimer>
+#include "../shared/util.h"
 
 class TestItem : public QQuickItem
 {
@@ -131,8 +134,15 @@ private slots:
     void hoverEvent();
     void hoverEventInParent();
 
+    void paintOrder_data();
+    void paintOrder();
+
 private:
 
+    enum PaintOrderOp {
+        NoOp, Append, Remove, StackBefore, StackAfter, SetZ
+    };
+
     void ensureFocus(QWindow *w) {
         w->show();
         w->requestActivateWindow();
@@ -1064,6 +1074,118 @@ void tst_qquickitem::hoverEventInParent()
     delete canvas;
 }
 
+void tst_qquickitem::paintOrder_data()
+{
+    QTest::addColumn<QUrl>("source");
+    QTest::addColumn<int>("op");
+    QTest::addColumn<QVariant>("param1");
+    QTest::addColumn<QVariant>("param2");
+    QTest::addColumn<QStringList>("expected");
+
+    QTest::newRow("test 1 noop") << QUrl::fromLocalFile(TESTDATA("order.1.qml"))
+        << int(NoOp) << QVariant() << QVariant()
+        << (QStringList() << "1" << "2" << "3");
+    QTest::newRow("test 1 add") << QUrl::fromLocalFile(TESTDATA("order.1.qml"))
+        << int(Append) << QVariant("new") << QVariant()
+        << (QStringList() << "1" << "2" << "3" << "new");
+    QTest::newRow("test 1 remove") << QUrl::fromLocalFile(TESTDATA("order.1.qml"))
+        << int(Remove) << QVariant(1) << QVariant()
+        << (QStringList() << "1" << "3");
+    QTest::newRow("test 1 stack before") << QUrl::fromLocalFile(TESTDATA("order.1.qml"))
+        << int(StackBefore) << QVariant(2) << QVariant(1)
+        << (QStringList() << "1" << "3" << "2");
+    QTest::newRow("test 1 stack after") << QUrl::fromLocalFile(TESTDATA("order.1.qml"))
+        << int(StackAfter) << QVariant(0) << QVariant(1)
+        << (QStringList() << "2" << "1" << "3");
+    QTest::newRow("test 1 set z") << QUrl::fromLocalFile(TESTDATA("order.1.qml"))
+        << int(SetZ) << QVariant(1) << QVariant(qreal(1.))
+        << (QStringList() << "1" << "3" << "2");
+
+    QTest::newRow("test 2 noop") << QUrl::fromLocalFile(TESTDATA("order.2.qml"))
+        << int(NoOp) << QVariant() << QVariant()
+        << (QStringList() << "1" << "3" << "2");
+    QTest::newRow("test 2 add") << QUrl::fromLocalFile(TESTDATA("order.2.qml"))
+        << int(Append) << QVariant("new") << QVariant()
+        << (QStringList() << "1" << "3" << "new" << "2");
+    QTest::newRow("test 2 remove 1") << QUrl::fromLocalFile(TESTDATA("order.2.qml"))
+        << int(Remove) << QVariant(1) << QVariant()
+        << (QStringList() << "1" << "3");
+    QTest::newRow("test 2 remove 2") << QUrl::fromLocalFile(TESTDATA("order.2.qml"))
+        << int(Remove) << QVariant(2) << QVariant()
+        << (QStringList() << "1" << "2");
+    QTest::newRow("test 2 stack before 1") << QUrl::fromLocalFile(TESTDATA("order.2.qml"))
+        << int(StackBefore) << QVariant(1) << QVariant(0)
+        << (QStringList() << "1" << "3" << "2");
+    QTest::newRow("test 2 stack before 2") << QUrl::fromLocalFile(TESTDATA("order.2.qml"))
+        << int(StackBefore) << QVariant(2) << QVariant(0)
+        << (QStringList() << "3" << "1" << "2");
+    QTest::newRow("test 2 stack after 1") << QUrl::fromLocalFile(TESTDATA("order.2.qml"))
+        << int(StackAfter) << QVariant(0) << QVariant(1)
+        << (QStringList() << "1" << "3" << "2");
+    QTest::newRow("test 2 stack after 2") << QUrl::fromLocalFile(TESTDATA("order.2.qml"))
+        << int(StackAfter) << QVariant(0) << QVariant(2)
+        << (QStringList() << "3" << "1" << "2");
+    QTest::newRow("test 1 set z") << QUrl::fromLocalFile(TESTDATA("order.1.qml"))
+        << int(SetZ) << QVariant(2) << QVariant(qreal(2.))
+        << (QStringList() << "1" << "2" << "3");
+}
+
+void tst_qquickitem::paintOrder()
+{
+    QFETCH(QUrl, source);
+    QFETCH(int, op);
+    QFETCH(QVariant, param1);
+    QFETCH(QVariant, param2);
+    QFETCH(QStringList, expected);
+
+    QQuickView view;
+    view.setSource(source);
+
+    QQuickItem *root = qobject_cast<QQuickItem*>(view.rootObject());
+    QVERIFY(root);
+
+    switch (op) {
+        case Append: {
+                QQuickItem *item = new QQuickItem(root);
+                item->setObjectName(param1.toString());
+            }
+            break;
+        case Remove: {
+                QQuickItem *item = root->childItems().at(param1.toInt());
+                delete item;
+            }
+            break;
+        case StackBefore: {
+                QQuickItem *item1 = root->childItems().at(param1.toInt());
+                QQuickItem *item2 = root->childItems().at(param2.toInt());
+                item1->stackBefore(item2);
+            }
+            break;
+        case StackAfter: {
+                QQuickItem *item1 = root->childItems().at(param1.toInt());
+                QQuickItem *item2 = root->childItems().at(param2.toInt());
+                item1->stackAfter(item2);
+            }
+            break;
+        case SetZ: {
+                QQuickItem *item = root->childItems().at(param1.toInt());
+                item->setZ(param2.toReal());
+            }
+            break;
+        default:
+            break;
+    }
+
+    QList<QQuickItem*> list = QQuickItemPrivate::get(root)->paintOrderChildItems();
+
+    QStringList items;
+    for (int i = 0; i < list.count(); ++i)
+        items << list.at(i)->objectName();
+
+    QCOMPARE(items, expected);
+}
+
+
 QTEST_MAIN(tst_qquickitem)
 
 #include "tst_qquickitem.moc"