Bug 215968 - Scheduled reparsing of all project files is too slow
Summary: Scheduled reparsing of all project files is too slow
Status: RESOLVED FIXED
Alias: None
Product: kdevelop
Classification: Applications
Component: general (show other bugs)
Version: unspecified
Platform: unspecified Linux
: NOR normal
Target Milestone: ---
Assignee: kdevelop-bugs-null
URL:
Keywords:
: 228295 (view as bug list)
Depends on:
Blocks:
 
Reported: 2009-11-24 15:46 UTC by Vadym Krevs
Modified: 2013-04-04 00:24 UTC (History)
6 users (show)

See Also:
Latest Commit:
Version Fixed In:


Attachments
Callgrind log for a 20 minute kdevelop run (392.78 KB, application/octet-stream)
2009-11-24 17:11 UTC, Vadym Krevs
Details
Callgrind trace of kdevelop.bin during a full project reparse (999.00 KB, application/octet-stream)
2010-02-20 22:28 UTC, kdezip
Details
Callgrind trace of kdevelop.bin during a full project reparse (952.67 KB, application/octet-stream)
2010-02-20 22:29 UTC, kdezip
Details
Replace recursion inside itemsForUrl with a QMultiHash lookup. (8.60 KB, patch)
2010-04-21 12:11 UTC, Brandon Ehle
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Vadym Krevs 2009-11-24 15:46:35 UTC
Version:           3.9.96 (using KDevPlatform 0.9.96) (using 4.3.3 (KDE 4.3.3) "release 3", KDE:43 / openSUSE_11.2)
Compiler:          gcc
OS:                Linux (x86_64) release 2.6.31.5-0.1-desktop

My project has ~6000 files in it (*.h, *.c, and *.cpp) files. If I go to "Settings->Configure Kdevelop->Project" and check "Schedule all project files for parsing", and restart Kdevelop, it reparses all project files on startup. 

However, reparsing takes far too long to be practical - over 45 minutes on a practically idle machine with 2.13Ghz Core2 processor, 4Gb RAM, and 2 fast 7200rpm hard drives. DUring reparse Kdevelop consumes 90-100% CPU according to top.

Is there any way to speed up reparsing? Visual Studio takes just a couple of minutes to update Intellisense data. Could you provide a standalone utility to reparse all project files outside of kdevelop (from a cron job, for example)?

 I've attached to kdevelop with gdb during the reparse - stack trace below.

0x00007ff716721513 in QUrl::operator== (this=0x28d1da8, url=...) at io/qurl.cpp:5635
5635        if (!QURL_HASFLAG(d->stateFlags, QUrlPrivate::Parsed)) d->parse();
(gdb) bt
#0  0x00007ff716721513 in QUrl::operator== (this=0x28d1da8, url=...) at io/qurl.cpp:5635
#1  0x00007ff717310408 in KDevelop::ProjectPrivate::itemsForUrlInternal(KUrl const&, KDevelop::ProjectFolderItem*) const () from /usr/lib64/libkdevplatformshell.so.1
#2  0x00007ff717310670 in KDevelop::ProjectPrivate::itemsForUrlInternal(KUrl const&, KDevelop::ProjectFolderItem*) const () from /usr/lib64/libkdevplatformshell.so.1
#3  0x00007ff717310670 in KDevelop::ProjectPrivate::itemsForUrlInternal(KUrl const&, KDevelop::ProjectFolderItem*) const () from /usr/lib64/libkdevplatformshell.so.1
#4  0x00007ff71730eb7b in KDevelop::Project::filesForUrl(KUrl const&) const () from /usr/lib64/libkdevplatformshell.so.1
#5  0x00007ff6f36b3798 in IncludePathComputer::computeForeground (this=0x7ff6ea02e040) at /usr/src/debug/kdevelop-3.9.96/languages/cpp/includepathcomputer.cpp:67
#6  0x00007ff6f36ab68f in CppLanguageSupport::findIncludePathsForJob (this=<value optimized out>, job=0x7ff6e8c6ff40) at /usr/src/debug/kdevelop-3.9.96/languages/cpp/cpplanguagesupport.cpp:368
#7  0x00007ff6f36b25ff in CppLanguageSupport::qt_metacall (this=0x55223a0, _c=InvokeMetaMethod, _id=<value optimized out>, _a=0x7ff6f74d7e90)
    at /usr/src/debug/kdevelop-3.9.96/build/languages/cpp/cpplanguagesupport.moc:130
#8  0x00007ff71676f2d9 in QObject::event (this=0x55223a0, e=0x7ff6f7253b00) at kernel/qobject.cpp:1111
#9  0x00007ff715c2b2ac in QApplicationPrivate::notify_helper (this=0x14e60d0, receiver=0x55223a0, e=0x7ff6f7253b00) at kernel/qapplication.cpp:4065
#10 0x00007ff715c3257e in QApplication::notify (this=0x7fff74effef0, receiver=0x55223a0, e=0x7ff6f7253b00) at kernel/qapplication.cpp:4030
#11 0x00007ff716c5bf26 in KApplication::notify(QObject*, QEvent*) () from /usr/lib64/libkdeui.so.5
#12 0x00007ff71675fddc in QCoreApplication::notifyInternal (this=0x7fff74effef0, receiver=0x55223a0, event=0x7ff6f7253b00) at kernel/qcoreapplication.cpp:610
#13 0x00007ff7167609ea in sendEvent (event=<value optimized out>, receiver=<value optimized out>) at kernel/qcoreapplication.h:213
#14 QCoreApplicationPrivate::sendPostedEvents (event=<value optimized out>, receiver=<value optimized out>) at kernel/qcoreapplication.cpp:1247
#15 0x00007ff716788803 in sendPostedEvents () at kernel/qcoreapplication.h:218
#16 postEventSourceDispatch () at kernel/qeventdispatcher_glib.cpp:276
#17 0x00007ff70fb55dde in g_main_context_dispatch () from /usr/lib64/libglib-2.0.so.0
#18 0x00007ff70fb597a8 in ?? () from /usr/lib64/libglib-2.0.so.0
#19 0x00007ff70fb598d0 in g_main_context_iteration () from /usr/lib64/libglib-2.0.so.0
#20 0x00007ff7167883a3 in QEventDispatcherGlib::processEvents (this=0x611070, flags=<value optimized out>) at kernel/qeventdispatcher_glib.cpp:407
#21 0x00007ff715cbe31e in QGuiEventDispatcherGlib::processEvents (this=0x28420f0, flags=<value optimized out>) at kernel/qguieventdispatcher_glib.cpp:202
#22 0x00007ff71675e712 in QEventLoop::processEvents (this=<value optimized out>, flags=DWARF-2 expression error: DW_OP_reg operations must be used either alone or in conjuction with DW_OP_piece.
) at kernel/qeventloop.cpp:149
#23 0x00007ff71675eae4 in QEventLoop::exec (this=0x7fff74effdc0, flags=DWARF-2 expression error: DW_OP_reg operations must be used either alone or in conjuction with DW_OP_piece.
) at kernel/qeventloop.cpp:201
#24 0x00007ff716760c99 in QCoreApplication::exec () at kernel/qcoreapplication.cpp:888
#25 0x0000000000405d77 in main (argc=<value optimized out>, argv=<value optimized out>) at /usr/src/debug/kdevelop-3.9.96/app/main.cpp:193
Comment 1 David Nolden 2009-11-24 16:11:28 UTC
Parsing speed is being worked on, but it should be _much_ faster already than the time you'r reporting. Your backtrace indicates a performance problem not in the parsing, but rather in the project-manager in the itemForUrlInternal(..) function. Maybe your project has a structure where the itemForUrlInternal(..) function is specifically inefficent?

There is a tool called "duchainify" in kdevplatform/utils/duchainify that can be used to test the parsing-speed under clean conditions.
Comment 2 Vadym Krevs 2009-11-24 16:16:26 UTC
According to the strace utility, many project files are stat'ed hundreds of times consecutively. 

How do you define "clean conditions"?
Comment 3 David Nolden 2009-11-24 16:22:25 UTC
By 'clean' conditions I mean that the parsing is isolated out of the IDE, without a project-manager and such.

If the parsing is slow there as well, you could supply a callgrind trace, showing up the reason why it's slow.

The info from strace is not really useful. Also, there has been work in this area, so please update to the current kdevelop from svn and check whether the situation is improved.
Comment 4 Vadym Krevs 2009-11-24 16:35:00 UTC
There is no "duchainify" in kdevplatform/utils/duchainify - at least for kdevplatform-0.9.96.
Comment 5 Vadym Krevs 2009-11-24 17:11:00 UTC
Created attachment 38542 [details]
Callgrind log for a 20 minute kdevelop run

I've started KDevelop under callgrind and let it reparse all project files for 20 minutes after which I forced a callgrind dump and aborted kdevelop.
Comment 6 Andreas Pakulat 2009-11-24 17:28:26 UTC
Looking at the log of svn I think you should retry with svn instead of beta6. There's been speedup changes specifically in the "hotspots" of that callgrind output.
Comment 7 Vadym Krevs 2009-11-24 17:44:21 UTC
kdevelop svn trunk now depends on qt4.6 (which had not been publicly release yet) while opensuse 11.2 is based on qt 4.5.3, so that is not an option for me.
Comment 8 Milian Wolff 2009-11-24 17:59:37 UTC
This is not true. KDE Libs trunk (i.e. 4.4) depends on Qt 4.6, but KDevplatform & KDevelop can be build with 4.3 (Qt 4.5.X) just fine.
Comment 9 Andreas Pakulat 2009-11-24 18:17:44 UTC
(In reply to comment #7)
> kdevelop svn trunk now depends on qt4.6 (which had not been publicly release
> yet) while opensuse 11.2 is based on qt 4.5.3, so that is not an option for me.

I'd be interested to know where you heard or read this so we can clarify that.
Comment 10 Vadym Krevs 2009-12-09 22:58:55 UTC
My mistake, I had mistaken the requirements for kde trunk for requirements for kdevelop. 

Anyhow, I've just built kdevplatform and kdevelop from svn today (revisions 1060767 and 1060770 respectively). The improvements for full scheduled reparse are quite significant - it now takes just under 15 minutes - a factor of 3 improvement over the old 45 minutes. Well done!

However, it is still almost 10 times slower than full reindexing of a makefile-based project in QtCreator 1.3.0 on the same desktop.
Comment 11 Milian Wolff 2009-12-09 23:15:14 UTC
If you can spare the time, please retry with r1060781, would be interested on what difference it makes on your project.
Comment 12 Vadym Krevs 2009-12-10 00:10:16 UTC
Cool - reparse time is down to just under 7 minutes.
Comment 13 David Nolden 2009-12-10 00:26:37 UTC
I hope what you're doing is really reparsing, not 'updating' ;-)

Did you do "rm ~/.kdevduchain -R" between your tests?

Also, there is a new option to reduce the processing-level, available under "Settings -> Language Support", there you can specify the project size until which the 'full' processing is done. I think the default value is 10000, but it may count the project-files wrongly, so maybe your project was already processed in simplified mode and thus the speedup.. however this mode is still experimental and might still cause problems in code-completion and other duchain stuff.
Comment 14 Vadym Krevs 2009-12-10 09:57:47 UTC
I've tried both 10000 (default) and 100000 for min project size - it makes no significant difference on reparse time both with and without rm -rf ~/.kdevduchain before reparsing.

FYI, some more stats about the contents of the project directory: ~6000 .h/.c/.cpp files, same number of source control metadata files, ~12000 dependency information files, and ~12000 build artifacts (the project is built twice - once in unicode mode and once in mbcs mode, hence number of dependencies and build artifacts is double the number of source files).
Comment 15 David Nolden 2009-12-10 12:27:48 UTC
You can easily check whether 'simplified' parsing was used: Type CTRL+ALT+m and check whether all functions are shown as "functionName(...)" instead of "functionName(args)"
Comment 16 Vadym Krevs 2009-12-10 22:28:43 UTC
It used "simplified" parsing even with 100000 for min project size ... Just out of curiosity I bumped it up to 500000, deleted .kdevduchain, and forced a reparse -  that resulted in "full" parsing.
Comment 17 Vadym Krevs 2009-12-10 22:30:00 UTC
I was also somewhat surprised to see kdevelop launch make and gcc many times during the reparse. At least that's what top reported.
Comment 18 kdezip 2010-02-20 14:51:15 UTC
Hi. Just upgraded to Kdevelop 4 beta 8 (tip of svn) from beta 6, and scheduled project reparsing appears to have a huge performance regression. My custom makefiles project consists of 9317 C++ files. Beta 6 took around 11 minutes. Beta 8 takes 33 minutes, even after a recursive removal of the .kdevduchain folder.   top reports ~75-80% CPU usage from kdevelop.bin, iotop reports many small (10-100K) reads/writes from kdevelop.bin.

Also noticed  numerous (hundreds if not more) gcc and make invocations my kdevelop during parsing - could this be the cause?

Just for comparison, QtCreator 1.3.1 from 2010.2 SDK takes < 2 minutes to reindex the project on same notebook (Intel Core2 2.53Ghz, 6Mb cache, 4GB RAM, 320Gb 7200rpm hdd). iotop reports qtcreator performing reads at over 500Kb - 1.5Mb per second, and virtually no writes.
Comment 19 Vadym Krevs 2010-02-20 18:39:11 UTC
Similar performance regression here as well.
Comment 20 David Nolden 2010-02-20 20:17:32 UTC
Could you create a callgrind trace of parsing the project in question?
Comment 21 kdezip 2010-02-20 21:44:15 UTC
Will do. I noticed that at least some spawned make commands look like

make -k --no-print-directory -W './path/to/file.h' -n './path/to/file.o'

Is Kdevelop spawning a make process for each .h/.cpp in the project during the reparse?
Comment 22 kdezip 2010-02-20 21:56:09 UTC
No joy. If I run "valgrind --tool=callgrind --num-callers=40 $KDEVELOP_HOME/bin/kdevelop  -s mysession", then a 0 byte callgrind log is generated on quit from kdevelop. Adding --trace-children=yes forces callgrind to trace each spawned make process as well, and the system literally freezes. Had to reboot to recover.
Comment 23 kdezip 2010-02-20 22:28:18 UTC
Created attachment 40968 [details]
Callgrind trace of kdevelop.bin during a full project reparse

First part of the attachment.
Comment 24 kdezip 2010-02-20 22:29:33 UTC
Created attachment 40969 [details]
Callgrind trace of kdevelop.bin during a full project reparse

Second part of the attachment. Use the following to recover the original file

cat callgrind.out.11625.bz2aa callgrind.out.11625.bz2ab  > callgrind.out.11625.bz2
bunzip2 callgrind.out.11625.bz2
Comment 25 kdezip 2010-02-20 22:30:50 UTC
Got it - the trick was to set the KDEV_SESSION environment variable, and then profile kdevelop.bin, and not kdevelop.
Comment 26 Milian Wolff 2010-02-20 22:51:50 UTC
Hm thanks for the effort, sadly the callgrind doesn't show the bottleneck direclty. But I also think that the includepath builder (the make runs) are to blame, we'll have to see how to improve that.
Comment 27 Vadym Krevs 2010-02-20 23:01:56 UTC
Makes sense. IMHO, Kdevelop seems like a heavily-multithreaded application, but running it under callgrind will probably have the effect of serializing all threads due to callgrind's emulation, so mutex contention will probably be significantly reduced when running kdevelop under callgrind, and won't show up in the trace. Plus callgrind is not the best tool for profiling apps doing lots of I/O like kdevelop.
Comment 28 Milian Wolff 2010-02-24 13:59:56 UTC
*** Bug 228295 has been marked as a duplicate of this bug. ***
Comment 29 Milian Wolff 2010-02-27 19:17:25 UTC
SVN commit 1096804 by mwolff:

Disable dumping of context when 'previous parameter declaration context didn't get used??'.

Speeds up parsing of boost libs:

        before    | after
real    7m49.239s | 6m30.723s 
user    6m40.697s | 6m15.995s
sys     0m23.012s | 0m9.513s

David, if you think that this should get fixed proplery, please explain what this warning means.

CCMAIL: zwabel@googlemail.com
CCBUG: 215968


 M  +3 -3      contextbuilder.cpp  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1096804
Comment 30 Milian Wolff 2010-02-28 14:43:30 UTC
SVN commit 1097117 by mwolff:

utilize new lengthFromIndex function, reduces total instr cost esp. for files like the boost/typeof/vectorXYZ.hpp files. The vector50.hpp e.g. has now a 15% lower cost

CCBUG: 215968

 M  +1 -1      lexer.cpp  
 M  +1 -1      rpp/pp-location.cpp  
 M  +3 -3      rpp/pp-stream.cpp  
 M  +1 -1      rpp/pp-stream.h  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1097117
Comment 31 Milian Wolff 2010-02-28 14:51:59 UTC
I did some more profiling, esp. with the project that bschindler provided me with. Essentially it's just a checkout of boost. To my eyes the custom include path resolver is not the bottleneck, esp. considering that it's already cached per dir. Instead I noticed that esp. files like boost/typeof/vectorXYZ.hpp are really slow at parsing. See their contents for example at:

http://sodium.resophonic.com/git/boost/tree/boost/typeof/vector200.hpp?id=6936053b064a7cef59fdbaca963d49c60708ebf2

I'm not sure how common such files are, but I fear that every project using boost might include them at one point or another, hence improving their parsing should be helpful.

You can take this profile as an example, showing that the positionAt in pp-location.cpp is really slow since it has to lookup the length of many offsets with a method marked as expensive:

http://milianw.de/files/traces/callgrind.out.4895.bz2
Comment 32 Vadym Krevs 2010-02-28 19:29:17 UTC
No boost in my project, just plain stl.
Comment 33 Milian Wolff 2010-03-01 00:32:13 UTC
Still, the root of the problem points to a very generic area that has nothing to do with the boost file. Improving the area would also increase the speed of parsing any other file.
Comment 34 David Nolden 2010-03-03 00:52:23 UTC
At least the wakeOne() at position 3 should be gone from the callgrind log now.
Comment 35 David Nolden 2010-03-03 01:02:56 UTC
There is some interesting info in the callgrind log, it also reveals a problem in CodeModel::addItem(..), which seems to be doing too much (that's where all the IndexedQualifiedIdentifier constructor- and destructor-calls come from).
Comment 36 Milian Wolff 2010-04-03 14:43:05 UTC
The bottleneck for custom make file projects is now the IncludePathResolver that runs up to 6 make calls for _each_ file :-/

I'll look into it and try to fix it.
Comment 37 Milian Wolff 2010-04-05 02:39:41 UTC
SVN commit 1111174 by mwolff:

fix implementation of operator== in ModificationRevisionSet, that was totally broken
and explains why some caches (I saw it in the includepathresolver) didn't apply at all, wonder how this could have slipped so long...

Now that the cache applies, Custom Make Manager projects are much faster to parse since the cached results per directory
apply, and make doesn't have to be called once for every file.

CCBUG: 215968

 M  +1 -1      modificationrevisionset.h  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1111174
Comment 38 Milian Wolff 2010-04-05 02:41:57 UTC
SVN commit 1111176 by mwolff:

merge make runs for different possible targets, should make parsing of some custom make file projects already 3x faster

since I have no clue about unsermake, I don't know whether it works there as well, anyone?

CCMAIL: kdevelop-devel@barney.cs.uni-potsdam.de
CCBUG: 215968

 M  +6 -12     includepathresolver.cpp  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1111176
Comment 39 Milian Wolff 2010-04-05 02:41:59 UTC
SVN commit 1111177 by mwolff:

merge make command for absolute and relative path, should make certain custom make projects
up to 2x faster to parse

CCBUG: 215968

 M  +10 -26    includepathresolver.cpp  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1111177
Comment 40 Brandon Ehle 2010-04-21 12:09:40 UTC
Running into the same problem as well, but most of my time is in itemsForUrlInternal.

I made a patch that I believe works the same but using a QMultiHash instead of recursion, the only thing I am note sure about is whether using the IndexedString is appropriate for this.
Comment 41 Brandon Ehle 2010-04-21 12:11:23 UTC
Created attachment 42936 [details]
Replace recursion inside itemsForUrl with a QMultiHash lookup.
Comment 42 David Nolden 2010-04-21 13:58:19 UTC
@Milian: If caching works, then that change alone won't make anything
3 times faster. The change should be ok though, although I'm worried
about doing this so close before the release, I hope you've tested it
intensively.

@Brandon Ehle: Your patch seems to make a lot of sense. Can someone
with a better overview of the project architecture check, and
eventually apply it?
Comment 43 Milian Wolff 2010-04-21 14:08:37 UTC
@ David: this commit was done before I found the error in the caching, the statement in the commit message is not applicable anymore. But imo the change is still approriate and I tested it as much as possible.

@Brandon: Can you share your project or at least the callgrind log files showing the bottleneck? Esp. a comparison would be nice (before <-> after).

Furthermore, I'd appreciate it, if you could put your patch on http://reviewboard.kde.org/ , I have a few comments on it and there I could comment directly on the changes.
Comment 44 David Nolden 2010-04-21 17:45:15 UTC
@Milian: Ah sorry I didn't look at the date, and thought the change was fresh. :)
Comment 45 Brandon Ehle 2010-04-21 18:36:42 UTC
Added as http://reviewboard.kde.org/r/3722/

Will do some before / after comparisons tonight after I get back from work.
Comment 46 Milian Wolff 2011-09-08 18:34:57 UTC
Git commit 5c67406cbb35012d87c2560ec74366c1701ac288 by Milian Wolff.
Committed on 08/09/2011 at 16:05.
Pushed by mwolff into branch 'master'.

optimize: only use ForegroundLock in ParseJob::readContents when really required

We now use a variant of the double-checked-initialization pattern, as the
trackerForUrl should be threadsafe according to its apidox. Only when we have
a tracker do we need to get the foreground lock.

When opening a project, the majority of files won't be opened in the editor,
and all others can thus be parsed/read without requiring a ForegroundLock

In my benchmarks (using the free non-commercial edition of VTune) this improved
the performance of a duchainify run by 25% or ~10s.

CCBUG: 215968

M  +22   -19   language/backgroundparser/parsejob.cpp

http://commits.kde.org/kdevplatform/5c67406cbb35012d87c2560ec74366c1701ac288
Comment 47 Milian Wolff 2011-09-09 16:05:31 UTC
Git commit acabbf5b22030266968bb60a3ae50109c92c00f6 by Milian Wolff.
Committed on 09/09/2011 at 18:02.
Pushed by mwolff into branch 'master'.

optimize: implement hash-based lookup for itemsForUrl

When loading big projects with lots of files, much time was spent in
Project::itemsForUrl (up to a minute in total in one of my tests).

Now we use a QHash<uint, ProjectBaseItem*> lookup table, which brings
down the total time to a mere fraction of a second.

The lookup table is saved in the ProjectModel and is updated on demand
from the ProjectBaseItem.

Introduces a new ProjectModel::itemsForUrl which will return all files
for a url without filtering by project.

CCBUG: 215968

M  +5    -0    language/duchain/indexedstring.cpp
M  +1    -0    language/duchain/indexedstring.h
M  +40   -1    project/projectmodel.cpp
M  +4    -0    project/projectmodel.h
M  +15   -6    shell/project.cpp

http://commits.kde.org/kdevplatform/acabbf5b22030266968bb60a3ae50109c92c00f6
Comment 48 Aleix Pol 2013-02-27 19:17:22 UTC
Is there any objective way to close this bug? :)
Comment 49 Aleix Pol 2013-04-04 00:24:50 UTC
Many improvements happened over time, I guess it can be closed as fixed.

Congratulations guys!!