From 8486a510d5fb6c9ecd03dba0a49fd4f6d55c3bca Mon Sep 17 00:00:00 2001 From: Robin Burchell Date: Sun, 2 Sep 2012 12:18:14 +0200 Subject: graphicsview: use std::sort instead of qSort MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit In almost all cases, std::sort is wildly faster than qSort - but especially in the case where the input data is already sorted. in some stress tests which ran through the index with a lot of items, this commit provides huge speedup (684ms down to 10ms for painting 15001 empty items on the provided benchmark), for me. Task-number: QTBUG-11022 Change-Id: I5551f8e320c33ba13d464bf22047a665c81f3b74 Reviewed-by: Peter Kümmel Reviewed-by: João Abecasis --- src/widgets/graphicsview/qgraphicsitem.cpp | 2 +- src/widgets/graphicsview/qgraphicsitem_p.h | 2 +- src/widgets/graphicsview/qgraphicsscene.cpp | 8 ++++---- src/widgets/graphicsview/qgraphicsscene_p.h | 2 +- src/widgets/graphicsview/qgraphicsscenebsptreeindex.cpp | 16 ++++++++-------- 5 files changed, 15 insertions(+), 15 deletions(-) diff --git a/src/widgets/graphicsview/qgraphicsitem.cpp b/src/widgets/graphicsview/qgraphicsitem.cpp index 27cd4e62ca..c4c9fff245 100644 --- a/src/widgets/graphicsview/qgraphicsitem.cpp +++ b/src/widgets/graphicsview/qgraphicsitem.cpp @@ -4578,7 +4578,7 @@ void QGraphicsItem::setZValue(qreal z) void QGraphicsItemPrivate::ensureSequentialSiblingIndex() { if (!sequentialOrdering) { - qSort(children.begin(), children.end(), insertionOrder); + std::sort(children.begin(), children.end(), insertionOrder); sequentialOrdering = 1; needSortChildren = 1; } diff --git a/src/widgets/graphicsview/qgraphicsitem_p.h b/src/widgets/graphicsview/qgraphicsitem_p.h index 77b54c1325..4344fa8097 100644 --- a/src/widgets/graphicsview/qgraphicsitem_p.h +++ b/src/widgets/graphicsview/qgraphicsitem_p.h @@ -826,7 +826,7 @@ inline void QGraphicsItemPrivate::ensureSortedChildren() sequentialOrdering = 1; if (children.isEmpty()) return; - qSort(children.begin(), children.end(), qt_notclosestLeaf); + std::sort(children.begin(), children.end(), qt_notclosestLeaf); for (int i = 0; i < children.size(); ++i) { if (children.at(i)->d_ptr->siblingIndex != i) { sequentialOrdering = 0; diff --git a/src/widgets/graphicsview/qgraphicsscene.cpp b/src/widgets/graphicsview/qgraphicsscene.cpp index 6fe619ec02..313e713946 100644 --- a/src/widgets/graphicsview/qgraphicsscene.cpp +++ b/src/widgets/graphicsview/qgraphicsscene.cpp @@ -1465,7 +1465,7 @@ void QGraphicsScenePrivate::mousePressEventHandler(QGraphicsSceneMouseEvent *mou void QGraphicsScenePrivate::ensureSequentialTopLevelSiblingIndexes() { if (!topLevelSequentialOrdering) { - qSort(topLevelItems.begin(), topLevelItems.end(), QGraphicsItemPrivate::insertionOrder); + std::sort(topLevelItems.begin(), topLevelItems.end(), QGraphicsItemPrivate::insertionOrder); topLevelSequentialOrdering = true; needSortTopLevelItems = 1; } @@ -6055,7 +6055,7 @@ void QGraphicsScenePrivate::gestureEventHandler(QGestureEvent *event) gestureTargetsAtHotSpots(startedGestures, Qt::GestureFlag(0), &cachedItemGestures, 0, &normalGestures, &conflictedGestures); cachedTargetItems = cachedItemGestures.keys(); - qSort(cachedTargetItems.begin(), cachedTargetItems.end(), qt_closestItemFirst); + std::sort(cachedTargetItems.begin(), cachedTargetItems.end(), qt_closestItemFirst); DEBUG() << "QGraphicsScenePrivate::gestureEventHandler:" << "Normal gestures:" << normalGestures << "Conflicting gestures:" << conflictedGestures; @@ -6148,7 +6148,7 @@ void QGraphicsScenePrivate::gestureEventHandler(QGestureEvent *event) << gesture->hotSpot() << gesture->d_func()->sceneHotSpot; } } - qSort(cachedTargetItems.begin(), cachedTargetItems.end(), qt_closestItemFirst); + std::sort(cachedTargetItems.begin(), cachedTargetItems.end(), qt_closestItemFirst); for (int i = 0; i < cachedTargetItems.size(); ++i) { QPointer receiver = cachedTargetItems.at(i); QSet gestures = @@ -6228,7 +6228,7 @@ void QGraphicsScenePrivate::gestureEventHandler(QGestureEvent *event) &cachedItemGestures, &targetsSet, 0, 0); cachedTargetItems = targetsSet.toList(); - qSort(cachedTargetItems.begin(), cachedTargetItems.end(), qt_closestItemFirst); + std::sort(cachedTargetItems.begin(), cachedTargetItems.end(), qt_closestItemFirst); DEBUG() << "QGraphicsScenePrivate::gestureEventHandler:" << "new targets:" << cachedTargetItems; i = -1; // start delivery again diff --git a/src/widgets/graphicsview/qgraphicsscene_p.h b/src/widgets/graphicsview/qgraphicsscene_p.h index 0f5a0a6fc1..c120f0df7a 100644 --- a/src/widgets/graphicsview/qgraphicsscene_p.h +++ b/src/widgets/graphicsview/qgraphicsscene_p.h @@ -271,7 +271,7 @@ public: inline void ensureSortedTopLevelItems() { if (needSortTopLevelItems) { - qSort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf); + std::sort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf); topLevelSequentialOrdering = false; needSortTopLevelItems = false; } diff --git a/src/widgets/graphicsview/qgraphicsscenebsptreeindex.cpp b/src/widgets/graphicsview/qgraphicsscenebsptreeindex.cpp index 2880a8aeaa..da288e802a 100644 --- a/src/widgets/graphicsview/qgraphicsscenebsptreeindex.cpp +++ b/src/widgets/graphicsview/qgraphicsscenebsptreeindex.cpp @@ -243,7 +243,7 @@ void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stac { if (!item->d_ptr->children.isEmpty()) { QList childList = item->d_ptr->children; - qSort(childList.begin(), childList.end(), qt_closestLeaf); + std::sort(childList.begin(), childList.end(), qt_closestLeaf); for (int i = 0; i < childList.size(); ++i) { QGraphicsItem *item = childList.at(i); if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent)) @@ -282,7 +282,7 @@ void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache() topLevels << item; } - qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf); + std::sort(topLevels.begin(), topLevels.end(), qt_closestLeaf); for (int i = 0; i < topLevels.size(); ++i) climbTree(topLevels.at(i), &stackingOrder); } @@ -417,23 +417,23 @@ void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList *itemLi if (onlyTopLevelItems) { if (order == Qt::DescendingOrder) - qSort(itemList->begin(), itemList->end(), qt_closestLeaf); + std::sort(itemList->begin(), itemList->end(), qt_closestLeaf); else if (order == Qt::AscendingOrder) - qSort(itemList->begin(), itemList->end(), qt_notclosestLeaf); + std::sort(itemList->begin(), itemList->end(), qt_notclosestLeaf); return; } if (sortCacheEnabled) { if (order == Qt::DescendingOrder) { - qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache); + std::sort(itemList->begin(), itemList->end(), closestItemFirst_withCache); } else if (order == Qt::AscendingOrder) { - qSort(itemList->begin(), itemList->end(), closestItemLast_withCache); + std::sort(itemList->begin(), itemList->end(), closestItemLast_withCache); } } else { if (order == Qt::DescendingOrder) { - qSort(itemList->begin(), itemList->end(), qt_closestItemFirst); + std::sort(itemList->begin(), itemList->end(), qt_closestItemFirst); } else if (order == Qt::AscendingOrder) { - qSort(itemList->begin(), itemList->end(), qt_closestItemLast); + std::sort(itemList->begin(), itemList->end(), qt_closestItemLast); } } } -- cgit v1.2.3