let's optimize: Project::itemsForUrl

[Andreas Pakulat]

On 09.09.11 16:45:50, Milian Wolff wrote:
> 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.

Well, thats not much of a problem I think, you can easily handle that
inside itemsForUrlInternal by checking the parent of the target item
(wich is a rather efficient operation) and use that url for the
prefix-check.

Andreas