Review Request 113488: Store the selected items in a more efficient way

[Frank Reininghaus]

> On Oct. 29, 2013, 3:09 p.m., Emmanuel Pescosta wrote:
> > I can't really comment on KItemSet, it's a little bit to difficult for me to review (limited time/skills),
> > but the rest looks pretty good :)
> > 
> > I did some selection tests and I haven't found any regression yet.
> > 
> > All unit tests pass.
> > 
> > So a big thank you for this improvement!
> >

Thanks! If anyone finds ways to make some of the more complicated parts of the new class simpler, I would be glad to hear about it. But a certain amount of complexity can probably not be avoided, this is the price one has to pay for saving memory and still being able to store any set of selected items. BTW, the QItemSelection* classes in Qt even need a lot more code, because they use similar ideas to store the selections using as little memory as possible, and they have to handle even more general cases (QModelIndexes, which have row/column/parent instead of just a single int to index the items).

In any case, I am pretty sure that the new code works well (I wrote lots of unit tests to make sure that it really behaves like a QSet<int> and does not cause any regressions).


- Frank


-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/113488/#review42637
-----------------------------------------------------------


On Oct. 28, 2013, 7:22 p.m., Frank Reininghaus wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/113488/
> -----------------------------------------------------------
> 
> (Updated Oct. 28, 2013, 7:22 p.m.)
> 
> 
> Review request for Dolphin.
> 
> 
> Repository: kde-baseapps
> 
> 
> Description
> -------
> 
> We currently store the selected items in a QSet<int>, which is neither space-efficient nor particularly fast when inserting many items which are in a consecutive range. A good way to see this is to watch Dolphin's memory usage with KSysGuard while pressing Ctrl+A in a really large folder - this can really be considered a bug IMHO.
> 
> I propose to replace the QSet<int> by a new class which I called "KItemSet", and which stores the items in a sorted list of ranges. For each range, we only store the first index and the length of the range, so we need a lot less memory for most common selection patterns, and we also save quite a few CPU cycles in many situations, because adding an item to the KItemSet will in many cases not need a memory allocation at all, and it's particularly easy when inserting sorted items into the KItemSet in a row.
> 
> KItemSet contains a minimal subset of QSet's API which makes it suitable as a drop-in replacement for our needs. I also added iterators, such that the items can be iterated through easily, also with foreach. One advantage of KItemSet compared to QSet<int> is that the items are always iterated through in ascending order.
> 
> Another advantate is that KItemListController::slotRubberBandChanged() can use the symmetric difference of KItemSets to calculate the new selection when doing a rubberband selection with Ctrl pressed, rather than implementing an inefficient workaround for QSet's lack of a symmetric difference function.
> 
> The diff looks fairly large, but except for the new class and the unit test, all changes are straightforward replacements.
> 
> Some more optimizations will be possible, for example, we can simply add a whole range of selected items when pressing Ctrl+A, rather than adding all items one by one. Another area where KItemSet will make it possible to improve the performance is KFileItemModel::createMimeData(). Some of the slowness of this function (which can be seen by pressing Ctrl+A and then Ctrl+C even in a folder of moderate size) is due to the fact that KDirModel::simplifiedUrlList(urls) internally sorts all URLs (which is not necessary because the URLs are sorted automatically now).
> 
> 
> Diffs
> -----
> 
>   dolphin/src/CMakeLists.txt 48ea14c 
>   dolphin/src/kitemviews/kfileitemlistview.h bdc63b0 
>   dolphin/src/kitemviews/kfileitemlistview.cpp 8950c9a 
>   dolphin/src/kitemviews/kfileitemmodel.h d005705 
>   dolphin/src/kitemviews/kfileitemmodel.cpp f21edbf 
>   dolphin/src/kitemviews/kitemlistcontroller.h bb72856 
>   dolphin/src/kitemviews/kitemlistcontroller.cpp befb097 
>   dolphin/src/kitemviews/kitemlistselectionmanager.h c89b8a4 
>   dolphin/src/kitemviews/kitemlistselectionmanager.cpp 833f7aa 
>   dolphin/src/kitemviews/kitemlistview.h 14360b0 
>   dolphin/src/kitemviews/kitemlistview.cpp b3d805a 
>   dolphin/src/kitemviews/kitemlistviewaccessible.cpp 565c215 
>   dolphin/src/kitemviews/kitemmodelbase.h c5b9a0c 
>   dolphin/src/kitemviews/kitemmodelbase.cpp edce95e 
>   dolphin/src/kitemviews/kitemset.h PRE-CREATION 
>   dolphin/src/kitemviews/kitemset.cpp PRE-CREATION 
>   dolphin/src/kitemviews/kstandarditemmodel.h 0debd6a 
>   dolphin/src/kitemviews/kstandarditemmodel.cpp 959d62c 
>   dolphin/src/panels/places/placesitemmodel.h 6938360 
>   dolphin/src/panels/places/placesitemmodel.cpp eae2095 
>   dolphin/src/tests/CMakeLists.txt dd761fc 
>   dolphin/src/tests/kitemlistcontrollertest.cpp 60e93e5 
>   dolphin/src/tests/kitemlistselectionmanagertest.cpp 302985a 
>   dolphin/src/tests/kitemsettest.cpp PRE-CREATION 
>   dolphin/src/views/dolphinview.h a6f969b 
>   dolphin/src/views/dolphinview.cpp fd149e0 
> 
> Diff: http://git.reviewboard.kde.org/r/113488/diff/
> 
> 
> Testing
> -------
> 
> All unit tests work (old+new), and I could not find any regressions when selecting items in different ways.
> 
> 
> Thanks,
> 
> Frank Reininghaus
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20131030/a7979f90/attachment.htm>