Slow QTreeViewPrivate::layout()

One of our greatest concerns with tree view performance is time-complexity of the layout algorithm in QTreeViewPrivate::layout(). The algorithm scales geometrically with the hierarchical depth of the tree. Note that even though some attempts are made to limit the range of elements this function operates, the fundamental structure of the algorithm is O(n^2).

Here is the timing data we collected as evidence of the O(n^2) performance. The "Items", "Depth" and "Top Groups" values are settings in the QSpinBoxes at the top of the window created by test program we have included with this report, and the performance statistics document what happens when the "Expand All" button is pressed. Note that as the number of items grows linearly, the number of cycles grows exponentially:

Items = 1000 Depth = 10 Top Groups = 5
cycles/1000, num. calls, function
18,690 1 expandAll()
18,420 1106 QTreeView::layout()
5,516 6505 QTreeView::viewIndex()
84 1754 QTreeView::firstVisibleItem()
269 1 QTreeView::updateGeometries()
13 1 QAbstractItemView::updateGeometries()

Items = 10000 Depth = 10 Top Groups = 5
cycles/1000, num. calls, function
979,026 1 expandAll()
978,762 11006 QTreeView::layout()
791,287 65005 QTreeView::viewIndex()
1,512 17955 QTreeView::firstVisibleItem()
264 1 QTreeView::updateGeometries()
13 1 QAbstractItemView::updateGeometries()

Items = 100000 Depth = 10 Top Groups = 5
cycles/1000, num. calls, function
252,239,221 1 expandAll()
252,238,906 110006 QTreeView::layout()
241,316,332 650005 QTreeView::viewIndex()
114,330 179955 QTreeView::firstVisibleItem()
314 1 QTreeView::updateGeometries()
15 1 QAbstractItemView::updateGeometries()

It appears to us that great improvements in the speed of the layout could be obtained by avoiding the O(n^2) pattern in the while loop that tabulates the total visible index count of a particular viewIndex. If the recursion were to just pass back the computed visible count then this expensive and geometrically scaling re-traversal back up the tree can be avoided.