QGraphicsScene sorting takes a lot of time

[f-r-o-s-t]

I have a QGraphicsScene, it contains about 200000 items(this items a added in the beginning of app). Everything works excellent until i have tried to add one more item on the scene, then app hang over ~5 minute for completing this operation.

Callstack operations, which repeat while app hangs

qt_closestLeaf qgraphicsitem_p.h
qt_notclosestLeaf qgraphicsitem_p.h
QAlgorithmsPrivate::qSortHelper<QList<QGraphicsItem*>::iterator, QGraphicsItem*, bool
(*)(QGraphicsItem const*, QGraphicsItem const*)> qalgorithms.h
qSort<QList<QGraphicsItem*>::iterator, bool (*)(QGraphicsItem const*, QGraphicsItem const*)>
qalgorithms.h
QGraphicsScenePrivate::ensureSortedTopLevelItems qgraphicsscene_p.h
QGraphicsSceneIndex::estimateTopLevelItems qgraphicssceneindex.cpp
QGraphicsScenePrivate::drawItems qgraphicsscene.cpp
QGraphicsView::paintEvent qgraphicsview.cpp
QWidget::event qwidget.cpp

I can't understand what is the problem.
What can I do to solve this problem?

Qt 4.6.2 OS Linux
Sorry for my English.

[wysota]

What is the type of items you are adding? If they are your own ones, how is boundingRect() defined for them? Also haven't you by any chance disabled indexing in the scene?

[f-r-o-s-t]

What is the type of items you are adding? If they are your own ones, how is boundingRect() defined for them? Also haven't you by any chance disabled indexing in the scene?

I'm adding QGraphicsEllipseItem, boundingRect() defined in QGraphicsElliplseItem. If index is enable app hangs when items() is called in QGraphicsScene, for example, when I hide and show window , if index is disable app hangs after I have called addItem().
QGraphicsScene always sorts items when I add item (sorting time ~5 minute), but I think this is my problem. What do you think about it?

[wysota]

If you have so many items I would strongly advise against disabling the index if you wish to have any interaction with the scene. Try avoiding calling items(), it returns all of your items, it is hard to come up with a situation when you needed to access them all. And the list needs to be sorted first. Sorting takes O(n*lgn) which for 200000 items is a huge number of comparisons to perform.

[f-r-o-s-t]

wysota Thanks for your answers, but problem is more complex.
Function items() is called from many other QGraphicsView's functions, for example when window is hid and shown again QGraphicsView::paintEvent() is called and it uses items(QRectF) and other(each function try to sort items). If I don't add item to Scene, all works good. Why addition of one more item makes so long sort, but first 200000 additions work well and without any problems.

[wysota]

If I don't add item to Scene, all works good.
Because if you add an item to the scene without the index, you break all the caches and everything has to be recalculated. Keep indexing enabled.

Why addition of one more item makes so long sort, but first 200000 additions work well and without any problems.
Maybe your machine starts swapping?

[f-r-o-s-t]

wysota, thanks for your answers.
Index was enabled always, i disable it for experiment.
Problem was in zValue which i made equal for many items, as result i had an unbalanced tree and long sorting time.
After zValue was changed my app works very fast. I'm happy!