QListView: Speedup handling of hidden items

Instead iterating through all rows to get the number of hidden items,
iterate over the hidden items which are fewer items.
Also don't create a temporary vector with visible flow positions by
remembering the count of hidden items before the working index and
adjusting them appropriately which gives a significant performance
boost when working with a large data set.

[ChangeLog][QtWidgets][QListWidget] Speedup handling of hidden items
when working with large data sets

Task-number: QTBUG-68977
Change-Id: I599b6e97945c245f02229145baad8363ec2bf2f5
Reviewed-by: Richard Moe Gustavsen <richard.gustavsen@qt.io>

6 files changed, 108 insertions, 17 deletions

diff --git a/src/widgets/itemviews/qlistview.cpp b/src/widgets/itemviews/qlistview.cpp
index e5769940d4..fdac332367 100644
--- a/src/widgets/itemviews/qlistview.cpp
+++ b/src/widgets/itemviews/qlistview.cpp
@@ -2246,8 +2246,8 @@ int QListModeViewBase::verticalScrollToValue(int index, QListView::ScrollHint hi
         } else {
             int scrollBarValue = verticalScrollBar()->value();
             int numHidden = 0;
-            for (int i = 0; i < flowPositions.count() - 1 && i <= scrollBarValue; ++i)
-                if (isHidden(i))
+            for (const auto &idx : qAsConst(dd->hiddenRows))
+                if (idx.row() <= scrollBarValue)
                     ++numHidden;
             value = qBound(0, scrollValueMap.at(verticalScrollBar()->value()) - numHidden, flowPositions.count() - 1);
         }
@@ -2687,21 +2687,24 @@ int QListModeViewBase::perItemScrollToValue(int index, int scrollValue, int view
         return scrollValue;
 
     itemExtent += spacing();
-    QVector<int> visibleFlowPositions;
-    visibleFlowPositions.reserve(flowPositions.count() - 1);
-    for (int i = 0; i < flowPositions.count() - 1; i++) { // flowPositions count is +1 larger than actual row count
-        if (!isHidden(i))
-            visibleFlowPositions.append(flowPositions.at(i));
-    }
-
+    QVector<int> hiddenRows = dd->hiddenRowIds();
+    std::sort(hiddenRows.begin(), hiddenRows.end());
+    int hiddenRowsBefore = 0;
+    for (int i = 0; i < hiddenRows.size() - 1; ++i)
+        if (hiddenRows.at(i) > index + hiddenRowsBefore)
+            break;
+        else
+            ++hiddenRowsBefore;
     if (!wrap) {
         int topIndex = index;
         const int bottomIndex = topIndex;
-        const int bottomCoordinate = visibleFlowPositions.at(index);
-
+        const int bottomCoordinate = flowPositions.at(index + hiddenRowsBefore);
         while (topIndex > 0 &&
-               (bottomCoordinate - visibleFlowPositions.at(topIndex - 1) + itemExtent) <= (viewportSize)) {
+               (bottomCoordinate - flowPositions.at(topIndex + hiddenRowsBefore - 1) + itemExtent) <= (viewportSize)) {
             topIndex--;
+            // will the next one be a hidden row -> skip
+            while (hiddenRowsBefore > 0 && hiddenRows.at(hiddenRowsBefore - 1) >= topIndex + hiddenRowsBefore - 1)
+                hiddenRowsBefore--;
         }
 
         const int itemCount = bottomIndex - topIndex + 1;
@@ -2720,7 +2723,7 @@ int QListModeViewBase::perItemScrollToValue(int index, int scrollValue, int view
                                            ? Qt::Horizontal : Qt::Vertical);
         if (flowOrientation == orientation) { // scrolling in the "flow" direction
             // ### wrapped scrolling in the flow direction
-            return visibleFlowPositions.at(index); // ### always pixel based for now
+            return flowPositions.at(index + hiddenRowsBefore); // ### always pixel based for now
         } else if (!segmentStartRows.isEmpty()) { // we are scrolling in the "segment" direction
             int segment = qBinarySearch<int>(segmentStartRows, index, 0, segmentStartRows.count() - 1);
             int leftSegment = segment;
@@ -3354,9 +3357,9 @@ int QListView::visualIndex(const QModelIndex &index) const
     d->executePostedLayout();
     QListViewItem itm = d->indexToListViewItem(index);
     int visualIndex = d->commonListView->itemIndex(itm);
-    for (int row = 0; row <= index.row() && visualIndex >= 0; row++) {
-        if (d->isHidden(row))
-            visualIndex--;
+    for (const auto &idx : qAsConst(d->hiddenRows)) {
+        if (idx.row() <= index.row())
+            --visualIndex;
     }
     return visualIndex;
 }
diff --git a/src/widgets/itemviews/qlistview_p.h b/src/widgets/itemviews/qlistview_p.h
index 181386d4d0..3f997ef7e3 100644
--- a/src/widgets/itemviews/qlistview_p.h
+++ b/src/widgets/itemviews/qlistview_p.h
@@ -377,6 +377,14 @@ public:
         QModelIndex idx = model->index(row, 0, root);
         return isPersistent(idx) && hiddenRows.contains(idx);
     }
+    // helper to avoid checking for isPersistent and creating persistent indexes as above in isHidden
+    QVector<int> hiddenRowIds() const {
+        QVector<int> rowIds;
+        rowIds.reserve(hiddenRows.size());
+        for (const auto &idx : hiddenRows)
+            rowIds += idx.row();
+        return rowIds;
+    }
     inline bool isHiddenOrDisabled(int row) const { return isHidden(row) || !isIndexEnabled(modelIndex(row)); }
 
     void removeCurrentAndDisabled(QVector<QModelIndex> *indexes, const QModelIndex &current) const;
diff --git a/tests/auto/widgets/itemviews/qlistview/tst_qlistview.cpp b/tests/auto/widgets/itemviews/qlistview/tst_qlistview.cpp
index 5227db64ec..433b9e55e1 100644
--- a/tests/auto/widgets/itemviews/qlistview/tst_qlistview.cpp
+++ b/tests/auto/widgets/itemviews/qlistview/tst_qlistview.cpp
@@ -873,6 +873,10 @@ void tst_QListView::setCurrentIndex()
             }
         }
     }
+    while (model.rowCount()) {
+        view.setCurrentIndex(model.index(model.rowCount() - 1, 0));
+        model.removeRow(model.rowCount() - 1);
+    }
 }
 
 class PublicListView : public QListView
diff --git a/tests/benchmarks/widgets/itemviews/itemviews.pro b/tests/benchmarks/widgets/itemviews/itemviews.pro
index a23cdf7b97..0c3256f307 100644
--- a/tests/benchmarks/widgets/itemviews/itemviews.pro
+++ b/tests/benchmarks/widgets/itemviews/itemviews.pro
@@ -1,4 +1,5 @@
 TEMPLATE = subdirs
 SUBDIRS = \
         qtableview \
-        qheaderview
+        qheaderview \
+        qlistview
diff --git a/tests/benchmarks/widgets/itemviews/qlistview/qlistview.pro b/tests/benchmarks/widgets/itemviews/qlistview/qlistview.pro
new file mode 100644
index 0000000000..68537d09ea
--- /dev/null
+++ b/tests/benchmarks/widgets/itemviews/qlistview/qlistview.pro
@@ -0,0 +1,7 @@
+QT += widgets testlib
+
+TEMPLATE = app
+TARGET = tst_bench_qlistview
+
+SOURCES += tst_qlistview.cpp
+
diff --git a/tests/benchmarks/widgets/itemviews/qlistview/tst_qlistview.cpp b/tests/benchmarks/widgets/itemviews/qlistview/tst_qlistview.cpp
new file mode 100644
index 0000000000..01496743c2
--- /dev/null
+++ b/tests/benchmarks/widgets/itemviews/qlistview/tst_qlistview.cpp
@@ -0,0 +1,68 @@
+/****************************************************************************
+**
+** Copyright (C) 2018 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <qtest.h>
+#include <QListView>
+#include <QStandardItemModel>
+
+
+class tst_QListView : public QObject
+{
+    Q_OBJECT
+
+public:
+    tst_QListView() = default;
+    virtual ~tst_QListView() = default;
+
+private slots:
+    void benchSetCurrentIndex();
+};
+
+void tst_QListView::benchSetCurrentIndex()
+{
+    QStandardItemModel sm(50000, 1);
+    QListView lv;
+    lv.setModel(&sm);
+    const int rc = lv.model()->rowCount();
+    for (int i = 0; i < rc; i+= 100)
+        lv.setRowHidden(i, true);
+    lv.setCurrentIndex(lv.model()->index(0, 0, QModelIndex()));
+    lv.show();
+    QVERIFY(QTest::qWaitForWindowExposed(&lv));
+
+    QBENCHMARK_ONCE {
+        while (lv.currentIndex().row() < rc - 20)
+            lv.setCurrentIndex(lv.model()->index(lv.currentIndex().row() + 17,
+                                                 lv.currentIndex().column(),
+                                                 QModelIndex()));
+    }
+}
+
+
+QTEST_MAIN(tst_QListView)
+#include "tst_qlistview.moc"