[RQt-devel] performance of Qt's bsp tree

[Michael Lawrence]

Just a follow-up to some some concerns from the cranvas group about the poor
performance of the BSP indexing of QGraphicsScene. It looks like the index
was pretty much rewritten between Qt 4.5 (what I showed at DSC 09) and Qt
4.6. In fact, it was being rewritten during the DSC. This has resulted in
apparently much poorer performance. It now takes 4-5 seconds to index only
100,000 points. Don't even think about indexing a million.

Whatever they changed, it's now really slow to add a point one at a time to
the index. I think they might be sorting something each time. They're using
quick sort, but a binary tree would be a better idea for efficient updating.
Thus, I changed qtpaint to disable the index while populating the scene and
then re-enable the index after all objects have been added. This is
considerably faster. Now 100,000 points take 0.2 seconds and a million takes
2 seconds. Nice and linear. Not as fast as before though, because there is
still a sort.

Michael
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.r-forge.r-project.org/pipermail/qtinterfaces-devel/attachments/20110408/13eeebfa/attachment.htm>