diff options
author | Igor Kushnir <igorkuo@gmail.com> | 2021-03-29 18:58:19 +0300 |
---|---|---|
committer | Igor Kushnir <igorkuo@gmail.com> | 2021-04-24 15:37:08 +0300 |
commit | 7d92ef63d7c2d9d017d89905a2ee0d1e9226b15c (patch) | |
tree | 9604cc85a68a4addf7b6a5cb3586d0e088344a88 /src/corelib/global/qglobal.cpp | |
parent | 885eff053797d56f2e295558d0a71b030fbb1a69 (diff) |
Optimize quadratic-time insertion in QSortFilterProxyModel
Let N = proxy_to_source.size() before the code modified in this commit.
Let M = (N - proxy_start). Let K = source_items.size(). The algorithmic
complexity of the removed loop is O(N+K+K*M), assuming the number of
O(N+K) reallocations is a constant. The complexity of the QList::insert
and std::copy implementation is O(N+K). This is much faster in practice
when K and M are of the same order of magnitude as N.
For example, this quadratic complexity issue results in noticeable
slowdown in the following scenario:
* a QSortFilterProxyModel is used only for filtering, not sorting;
* first set a filter that matches a single item in the middle of a
huge number of items (about one million) - this is reasonably fast
(takes about a second);
* then clear the filter (i.e. set an empty filter so that no item is
filtered out) and watch your application's UI freeze for a minute.
The "Add QSortFilterProxyModel clear-filter benchmark" commit (with
Change-Id I419a5521dd0be7676fbb09b34b4069d4a76423b1) adds a benchmark
that runs much faster with this performance fix.
Pick-to: 6.0 6.1
Change-Id: Ieaec173e6910f5d21eaee49402087f7711abbedf
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
Diffstat (limited to 'src/corelib/global/qglobal.cpp')
0 files changed, 0 insertions, 0 deletions