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

[Frank Reininghaus]

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

(Updated Oct. 30, 2013, 10:39 p.m.)


Status
------

This change has been marked as submitted.


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