[Development] updating many QPersistentModelIndices

[Milian Wolff]

On Wednesday 03 June 2015 22:23:45 Olivier Goffart wrote:
> On Wednesday 3. June 2015 18:32:46 Milian Wolff wrote:
> > Hey all,
> > 
> > for a customer I looked into the performance of a model/view application
> > with many (and I mean, many!) add/remove/modify operations on a model with
> > a QSortFilterProxyModel on top. The obvious solution to speed things up is
> > batching, which works nicely paired with layout{AboutToBe,}Changed. So far
> > so good, but the issue that was now reported comes when one now *also*
> > wants to enable MultiSelection in the view, and the user "accidentally"
> > presses CTRL + A to select all items in the view. This then completely
> > kills the performance, due to bottlenecks inside QAbstractItemModel, all
> > related to QPersistentModelIndex.
> > 
> > Some questions now from my side:
> > 
> > a) Why is the hash of indexes in QAbstractItemModelPrivate::Persistent not
> > unique - i.e. why is insertMulti required? I ask, b/c the "it + 1"
> > operation in QAbstractItemModelPrivate::Persistent::insertMultiAtEnd is
> > _extremely_ slow for large lists of persistent model indices, due to the
> > cache misses> 
> > etc. pp. involved. The documentation says:
> >     "There should be only one instance QPersistentModelIndexData per
> >     index,
> > 
> > but in some intermediate state there may be severals of
> > PersistantModelIndex pointing to the same index, ..."
> > 
> > What intermediate state is that? When I look at the uses of this function,
> > they always use the pattern
> > 
> > persistent.indexes.erase(...);
> > ...
> > persistent.insertMultiAtEnd(...);
> > 
> > I fail to see how/where this intermediate state can occur.
> 
> I wrote this code a very long time ago so I will try to answer.
> 
> Imagine you have two QPersistentModelIndex pointing at the second and third
> row.
> Then you remove the first row, and the persistent model index will be moved
> in the hash. We take the third and we move it to the second.  The we take
> the second and we move it to the first.  When we take the second, there
> might be two second.
> 
> I'm pretty sure there should be a test to catch that.  Maybe
> tst_QAbstractItemModel::complexChangesWithPersistent.
> Did you run the test in release or in debug? (to catch the Q_ASSERT)

I'm pretty sure I tested it in debug mode - at least in my test app asserts do 
get hit. I'll rerun this tomorrow on my work machine with a deliberate 
Q_ASSERT(false) in the test you mentioned.

Anyhow, I can now at least phantom of where this might be required, maybe I 
can come up with a better implementation.

> I did not realize that this +1 was so expensive.  Perhaps there is a better
> way to implement that.

It really is bad, you should write a test benchmark and take a look at it. 
Just iterate over all items in a large hash and you'll see that tons of cycles 
are spent in following the internal hash structure. Hashes (at least as 
implemented in Qt) are simply not meant for that access pattern.

> > b) Changing that function to just use insert() and returning early, the
> > big
> > bottleneck above is gone, but it's still very slow, mostly due to the
> > inefficiencies built-in to QPersistentModelIndex, e.g. operator= required
> > in the merge sort step. I wonder what to do there...
> > 
> > Has anyone had similar experiences, and if so - what where the workarounds
> > applied to make this fast?
> 
> Maybe some other datastructure than a QHash could be helpful?

The part b) is not related to QHash, but to QPMI in general with its inherent 
allocations and other inefficiencies.

Bye

-- 
Milian Wolff | milian.wolff at kdab.com | Software Engineer
KDAB (Deutschland) GmbH&Co KG, a KDAB Group company
Tel: +49-30-521325470
KDAB - The Qt Experts