Version: (using KDE 4.2.1) Installed from: Gentoo Packages When I want open file in /usr/bin with lot of file, all reaction (selection, word typing, ...) is really slow, I new wait 10s for select file under my cursor. It change progressively the icon (preview? type mime?) Thanks to fix it.
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).