[Development] updating many QPersistentModelIndices

[Olivier Goffart]

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 did not realize that this +1 was so expensive.  Perhaps there is a better 
way to implement that.


> 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?

-- 
Olivier 

Woboq - Qt services and support - http://woboq.com - http://code.woboq.org