Summary: | really poor performance in KFileDialog | ||
---|---|---|---|
Product: | [Frameworks and Libraries] kdelibs | Reporter: | BRULE Herman <alpha.super-one> |
Component: | general | Assignee: | Peter Penz <peter.penz19> |
Status: | RESOLVED FIXED | ||
Severity: | normal | CC: | mick22, mpyne, peter.penz19 |
Priority: | NOR | ||
Version: | unspecified | ||
Target Milestone: | --- | ||
Platform: | Gentoo Packages | ||
OS: | Unspecified | ||
Latest Commit: | Version Fixed In: |
Description
BRULE Herman
2009-03-23 20:32:24 UTC
I can confirm this. I have noticed (and reported) the slowness in dolphin, but the problem seems to be in the KFileDialog or a related class. A simple test application that displays a QFileDialog under KDE (where it is automatically replaced to a KFileDialog thanks to libkfilemodule.so) is very slow and needs almost a minute to display a folder with many items. When I run the same application under e.g. fluxbox (where it uses the QFileDialog), the directory listing is almost instant. Update: after some investigation, I found out that the long waiting time is spent in KFilePreviewGenerator::Private::orderItems. Algorithm 1 seems to cause the delays. If I switch to algorithm 2, the delay is gone, even for very large folders. Please revisit this part of the code! Algorithm 1 seems to me to be of order O(n*m) (where n = item count, m = row count). Algorithm 2 would be O(n*m) as well if one of its comments was to be believed, saying that KDirModel::itemForIndex or QList::at is O(n) (it's not clear which). However, both appear to me to be O(1). This means 2 should be of order O(n), and should definitely be faster for larger numbers of items. I'd do some testing to see if eliding algorithm 1 entirely makes things slow or not and some cases, and if not I'll get rid of it. I agree with your analysis. Even if itemForIndex in algorithm 1 is much faster than indexForItem (algo 2), the linear search loop used in algorithm 1 eats all that might have been gained. Eliminating algorithm 1 seems to me like a good short-term fix. Hopefully a fix can still go into 4.3.0. The question is, do we really need to iterate over all items just to find out which items are currently visible? If possible, I'd rather calculate min and max visible row and then put that sublist to the front. One thing worth noting is the following: there might be a problem with the value of rowCount. 1. upon the initial load of the folder: rowCount=itemCount=n (!) When you go to a new folder, the orderItems method is called with parameters such that itemCount equals rowCount. This will result in algorithm 1 being chosen and a worst-case complexity of O(n²)! No wonder that opening large folders takes such a long time. 2. when scrolling: itemCount=0 or 1, rowCount=n When scrolling in the view, the orderItems method is called multiple times, with itemCount being 0 or 1 and rowCount always n. This will choose algorithm 2. SVN commit 985445 by ppenz: Remove algorithm #1, as it slower in any case in comparison to algorithm #2. On my system opening a folder with 12000 items takes now 6 seconds instead of 30. I could pimp algorithm #1 down to 5 seconds, but it's not worth to duplicate so much code -> let's focus on improving the performance on the current algorithm if necessary. Thanks to Michael Meier and Michael Pyne for the analyses! BUG: 187943 M +15 -62 kfilepreviewgenerator.cpp WebSVN link: http://websvn.kde.org/?view=rev&revision=985445 In relation to Michael Meier's comment that rowCount == itemCount on initial load, it's because I don't think that in a list view that the model's row/column count have anything at all to do with the layout on-screen. I was working on a patch that would use QListView::indexAt() to work only on visible items until I realized that it was likely a logical disconnect. I think that row/column for a model only translates to a view for table views. I actually misunderstood the meaning of rowCount, too, until I had a closer look at the code. The rowCount just gives you the number of items in the folder (which I thought the itemCount was for). |