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

[Commit Hook]

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


This review has been submitted with commit 5c5d87fec44e7c5934e4b24060200173153f0ff4 by Frank Reininghaus to branch master.

- Commit Hook


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/efad258a/attachment.htm>