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

[Elvis Stansvik]

> On July 4, 2013, 10:27 p.m., Elvis Stansvik wrote:
> > dolphin/src/kitemviews/kitemlistview.cpp, line 1129
> > <http://git.reviewboard.kde.org/r/111398/diff/1/?file=168518#file168518line1129>
> >
> >     'i' could be const here I guess.
> 
> Frank Reininghaus wrote:
>     Yes, a const won't hurt here, but it is rather uncommon to add a const to POD types in function arguments and foreach loops (just look through the source of Dolphin or any other part of KDE with "grep foreach * -r | grep cpp | grep int" or "grep :: * -r | grep cpp | grep "(int"") because it doesn't have a big benefit. In other kinds of foreach loops, the const prevents that you accidentally modify the container contents, which would cause the implicitly shared copy to detach and force a rather expensive deep copy. However, POD types are copied anyway, so it doesn't matter much if you modify them.

Ah. But I wasn't thinking of copying, but of accidental modification. (E.g. same reason const is used for newIndex a few lines down). But you're right, it's not the norm to do that. I've worked on a Java code base recently where "final" is used all over the place for this reason, so I guess I was a little influenced by that :)


- Elvis


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


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