-
Igor Kushnir authored
The current algorithm iterates over project files and erases matching items from QVector m_projectFiles one by one. This is very slow, because KDevelop::forEachFile() iterates over project files in an order close to lexicographic, and m_projectFiles is sorted in lexicographic order too. So the average position of an erased item is close to QVector::begin(). The overall complexity of this algorithm is O(N*M), where N is the size of m_projectFiles before a project is closed, and M is the number of files in the project that is being closed. Simply iterating over the project files in the reverse order speeds up the erase one-by-one algorithm a lot. But there is an even faster alternative, which is implemented in this commit: instead of iterating over or collecting project files and then removing matching items from m_projectFiles, remove all items that have projectPath equal to the path of the project that is being closed. The complexity of this algorithm is O(N). Before this commit on average 3150 ms were spent in ProjectFileDataProvider::projectClosing() during KDevelop exit while a single project - kdevelop itself with a little more than 67 thousand files - was open. At this commit the time is just 14 ms. When the single project to be closed was WebKit with its almost 320 thousand files, about 196 *seconds* were spent in this function before the commit and only 56 ms at this commit. The best time I could achieve for closing kdevelop project by iterating over project files in the reverse order and applying minor heuristic optimizations was 165 ms. And such a reverse iteration could still be extremely slow when several projects were closed. This change makes BenchQuickOpen::benchProjectFileFilter_addRemoveProject() 1.5 times faster for a project with 100 files; 1.7 times faster for a project with 500 files; 2.2 times faster for a project with 1000 files; 5.9 times faster for a project with 10000 files. This commit changes behavior in case when a single file belongs to multiple projects. Previously all files belonging to the project being closed were removed. Now only the files that were added in the matching projectOpened() call are removed. Neither the previous nor the current behavior is ideal. But removing the files that were added along with the project makes a bit more sense to me. CCBUG: 427481
8e0f203a