let's optimize: Project::itemsForUrl

[Milian Wolff]

Hey all,

the function Project::itemsForUrl is *really* slow when we look at the total 
amount of time spent in there when parsing a biggish project. I just did that 
(with a simple QTimer and a static elapsed counter) and the last output was:

QList<KDevelop::ProjectBaseItem*> KDevelop::ProjectPrivate::itemsForUrl(const 
KUrl&) const elapsed time: 56870 

Yes, nearly a minute was spent in that function. So I would really like to 
improve that.

The code/apaku already mentions this:

        // TODO: This is moderately efficient, but could be much faster with a
        // QHash<QString, ProjectFolderItem> member. Would it be worth it?

I'm pretty sure he meant ProjectBaseItem. The question is, how to keep that in 
sync. We could put that into the ProjectModel and update it on every call to 
setUrl (if model()) and in setModel. I'm not so sure on the memory 
requirements though. We could of course just reuse IndexedString's new 
indexForString method, so the mem requirement would be (sizeof(uint) + 
sizeof(ProjectBaseItem*)) * N_items. Which is only a bit more than a megabyte 
on my machine (64Bit) for 100k items.

What do you think? Any other ideas? I also thought about comparing the start 
of the urls: If we could expect to have a proper hierarchy in the model, that 
follows the URL path hierarchy, that could be leveraged to improve the 
performance as well, by returning early. But I'm not so sure if that could be 
done without breaking stuff, as e.g. the URLs inside targets don't follow the 
URL hierarchy.

I think I'll give my IndexedString idea a shot and see how it goes. 
Objections? Hints?

bye
-- 
Milian Wolff
mail at milianw.de
http://milianw.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kdevelop-devel/attachments/20110909/7509373b/attachment.sig>