Store the selected items in a more efficient way

Review Request #113488 - Created Oct. 28, 2013 and submitted

Frank Reininghaus
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).
All unit tests work (old+new), and I could not find any regressions when selecting items in different ways.


  • 1
  • 0
  • 0
  • 1
Description From Last Updated
Wrong year ;) Emmanuel Pescosta Emmanuel Pescosta
Emmanuel Pescosta
Commit Hook
Frank Reininghaus
Review request changed

Status: Closed (submitted)