Review Request 109045: Big rewritte in KFileItemModel

Tue Feb 26 17:16:32 GMT 2013

> On Feb. 22, 2013, 9:37 a.m., Frank Reininghaus wrote:
> > Thanks Emmanuel for the new patch!
> > 
> > I just tried to test your patch, but it seems that your patch is not based on latest master - I just applied it, and patching master with the 'patch' command actually works, but it says that "Hunk #8 succeeded at 783 with fuzz 2", and the result of the fuzziness is that the code is in a state that does not compile.
> > 
> > The problem is in KFileItemModel::slotItemsDeleted(). Your patch contains a new, different solution to the "make sure that filtered children of removed parents are also removed" issue. There is a fix for that one in KDE/4.10 and master already - see https://git.reviewboard.kde.org/r/108976/.
> > 
> > The advantages of the existing approach are that the code to locate the filtered children is in one function only, preventing that the filtering-related complexity spreads out to too many different places, and also that its run-time complexity is at most O(N), where N is the maximum of the number of deleted items and filtered items. On the other hand, your solution to the problem has two nested foreach loops - one for the deleted items and one for the filtered items, and then another foreach loop over all (filtered) items in the function childItems(), such that we can get O(N^3) worst-case complexity. To be honest, I already find the places in the existing code where we have O(N^2) worst-case behaviour a bit worrying, and I hope it's understandable that I'm not in favour of replacing a
 n existing O(N) solution with a new O(N^3) one. If we do that, one could easily come up with a folder structure with a moderate number of files, in which filtering one part and then deleting
  another part would freeze Dolphin basically forever.
> > 
> > I can try to help with splitting this into smaller, self-contained commits, but having something that compiles as a starting point would be helpful. About "Fixed a bug, which was introduced during the rewrite of some code parts.": this is exactly why I think that making changes in smaller steps is better. At some point, the changes caused by a single patch that mixes different things get so complex that it's impossible to understand everything that's going on. If you do it in smaller steps, and you notice a regression at some point, you can at least easily find the problematic change with git bisect or something like that.
> 
> Frank Reininghaus wrote:
>     Just for the record, I've started working on splitting out the first and most important step of your patch, and I will post my results tonight or tomorrow.
>     
>     Only when going through all details it is possible to see how much work you put into this - thanks again for that! I'm sure that the class will be in a much better state when the patch is in master. However, I also found a couple of small issues like memory leaks (you never free the ItemData pointers in m_filtered items) and places where you introduced O(N^2) complexity for operations which were O(N) before, but most of that is more or less straightforward to fix.
> 
> Emmanuel Pescosta wrote:
>     > Just for the record, I've started working on splitting out the first and most important step of your patch
>     Awesome :) Thanks a lot ... I haven't had any time to work on it
>     
>     How have you fixed the O(N^2) complexity problem? 
>     
>     New idea (Just a question):
>     What if we add the "QList<ItemData*> childs" to the ItemData struct + keep the actual solution (all items in a list)? - So we will have the advantages of the tree- and list based approach combined in Dolphin. Maximum performance in all cases ;)

I uploaded my suggested changes as a new patch: https://git.reviewboard.kde.org/r/109180/

I thought this is more efficient than pointing out my suggestions here because some things require changes in multiple places, and I wanted to try first if it still works OK when these changes are done. So I had the modified patch already, and then just uploading it, rather than asking you to make the very same changes again, is easier for everyone, I suppose :-)

> How have you fixed the O(N^2) complexity problem? 

Used a hash to store the filtered ItemData*. This makes sure that we can still look up the filtered items in O(1) if we have the KFileItem.

> New idea (Just a question):
> What if we add the "QList<ItemData*> childs" to the ItemData struct + keep the actual solution (all items in a list)? - So we will have the advantages of the tree- and list based 
> approach combined in Dolphin. Maximum performance in all cases ;)

Hm, I'm not entirely sure if I understand how that is supposed to work. How can you make use of the children stored inside the ItemData struct, if those 'child' ItemData* are in the "all items" list anyway?

- Frank

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

On Feb. 21, 2013, 10:15 p.m., Emmanuel Pescosta wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/109045/
> -----------------------------------------------------------
> 
> (Updated Feb. 21, 2013, 10:15 p.m.)
> 
> 
> Review request for Dolphin and Frank Reininghaus.
> 
> 
> Description
> -------
> 
> Big rewritte in KFileItemModel: 
> + Get rid of the Url based item management 
> + Some performance improvements
> + Better handling of filtered items
> + Fix the treeview for timeline, trash, network-browser, ... (Different Url scheme)
> 
> Should fix bugs:
> + Bug 304565 - Network browser: details view breaks when expanding
> + Bug 312890 - Dolphin tries to render timeline:/ results as tree
> + Bug 311912 - After erasing a "filter", some thumbnails randomly disappear 
> 
> 
> This addresses bugs 304565, 311912 and 312890.
>     http://bugs.kde.org/show_bug.cgi?id=304565
>     http://bugs.kde.org/show_bug.cgi?id=311912
>     http://bugs.kde.org/show_bug.cgi?id=312890
> 
> 
> Diffs
> -----
> 
>   dolphin/src/kitemviews/kfileitemmodel.h a05d1f9 
>   dolphin/src/kitemviews/kfileitemmodel.cpp 60fc275 
>   dolphin/src/tests/kfileitemmodelbenchmark.cpp b1e777c 
>   dolphin/src/tests/kfileitemmodeltest.cpp c9f8a34 
> 
> Diff: http://git.reviewboard.kde.org/r/109045/diff/
> 
> 
> Testing
> -------
> 
> + Passes all tests
> + Renders timeline as a treeview without problems for files, timeline, trash (yes we can re-enable this), ...
> + Doesn't lose thumbnails anymore, when using the filterbar - Tested with 500 pictures (Also much faster response, esp. when you delete the filter string)
> 
> The bug 304565 needs some testing
> 
> 
> Thanks,
> 
> Emmanuel Pescosta
> 
>

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