Review Request 111398: Fix O(N^2) complexity issue in KItemListView::slotItemsRemoved

[Mark Gaiser]

> On July 5, 2013, 7:10 a.m., Mark Gaiser wrote:
> > dolphin/src/kitemviews/kitemlistview.cpp, line 1095
> > <http://git.reviewboard.kde.org/r/111398/diff/1/?file=168518#file168518line1095>
> >
> >     This if doesn't seem to do anything, only the elseif.. Perhaps just remove it and end up with:
> >     
> >     if (i > lastRemovedIndex) {
> >         itemsToMove.append(i);
> >         continue;
> >     }
> 
> Frank Reininghaus wrote:
>     This 'if' check prevents that items which are *before* the removed range are removed from the view.

No issue then. Although that's only the case if the order of i (thus the order of m_visibleItems) can be "random". You probably know best if it is or isn't :)


- Mark


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


On July 4, 2013, 10:10 p.m., Frank Reininghaus wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/111398/
> -----------------------------------------------------------
> 
> (Updated July 4, 2013, 10:10 p.m.)
> 
> 
> Review request for Dolphin.
> 
> 
> Description
> -------
> 
> In a directory which is shown in Dolphin, try the following (where N is a large number > 100000):
> 
> touch {1..N}.png
> touch {1..N}.jpg
> 
> (wait until all files are shown in the view)
> 
> rm *.jpg
> 
> This will freeze Dolphin for quite some time (if not, try to increase the number of files). This is because KItemListView::slotItemsRemoved() has a loop over all removed item ranges (100000 in this case), and in each loop, it has another loop that iterates through all items and tries to find visible ones. This is bad because there is always only a small number of visible items, so we better just iterate over those (similar to the approach in KItemListView::slotItemsInserted).
> 
> 
> Diffs
> -----
> 
>   dolphin/src/kitemviews/kitemlistview.cpp 2ea6657 
> 
> Diff: http://git.reviewboard.kde.org/r/111398/diff/
> 
> 
> Testing
> -------
> 
> Dolphin takes a lot less time to remove many item ranges.
> 
> 
> Thanks,
> 
> Frank Reininghaus
> 
>

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