diff options
author | Thorbjørn Lund Martsum <tmartsum@gmail.com> | 2012-09-27 14:56:43 +0200 |
---|---|---|
committer | The Qt Project <gerrit-noreply@qt-project.org> | 2012-10-27 07:35:57 +0200 |
commit | 6e4d7bbb0baeff2362e3d25be6aedcb68e7909b0 (patch) | |
tree | 40c0cc4ecaaa9db45205d83bfbfac93f99f993b0 | |
parent | cfc3eeea1b3fbf31998deef65fb01214d44d36fd (diff) |
QMap 5.0 - keep track of leftmost node (BIC)
This suggestion keeps track of the most left node.
The point is that constBegin() becomes a lot faster.
That speeds up iteration a bit, and makes it O(1) to get the
first element. The penalty in insert and remove is very small.
On large trees it seems to be less than 1%.
It should be noticed that constBegin() is a very common hint
on my planned change to 5.1, and this opperation will without
this patch cost 2 x log N. One when the user calls the hint
with begin - and one where it is compared with begin.
Other std::maps has a very fast begin(). E.g
http://www.cplusplus.com/reference/stl/map/begin/
(begin with constant time)
Change-Id: I221f6755aa8bd16a5189771c5bc8ae56c8ee0fb4
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
-rw-r--r-- | src/corelib/tools/qmap.cpp | 18 | ||||
-rw-r--r-- | src/corelib/tools/qmap.h | 8 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qmap/tst_qmap.cpp | 94 | ||||
-rw-r--r-- | tests/benchmarks/corelib/tools/qmap/main.cpp | 17 |
4 files changed, 133 insertions, 4 deletions
diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp index dea87c6b63..7c33d60750 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.cpp @@ -50,7 +50,7 @@ QT_BEGIN_NAMESPACE -const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, 0, 0 } }; +const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, 0, 0 }, 0 }; const QMapNodeBase *QMapNodeBase::nextNode() const { @@ -177,6 +177,12 @@ void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z) QMapNodeBase *x_parent; if (y->left == 0) { x = y->right; + if (y == mostLeftNode) { + if (x) + mostLeftNode = x; // It cannot have (left) children due the red black invariant. + else + mostLeftNode = y->parent(); + } } else { if (y->right == 0) { x = y->left; @@ -290,6 +296,13 @@ void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z) --size; } +void QMapDataBase::recalcMostLeftNode() +{ + mostLeftNode = &header; + while (mostLeftNode->left) + mostLeftNode = mostLeftNode->left; +} + static inline int qMapAlignmentThreshold() { // malloc on 32-bit platforms should return pointers that are 8-byte @@ -324,6 +337,8 @@ QMapNodeBase *QMapDataBase::createNode(int alloc, int alignment, QMapNodeBase *p if (parent) { if (left) { parent->left = node; + if (parent == mostLeftNode) + mostLeftNode = node; } else { parent->right = node; } @@ -352,6 +367,7 @@ QMapDataBase *QMapDataBase::createData() d->header.p = 0; d->header.left = 0; d->header.right = 0; + d->mostLeftNode = &(d->header); return d; } diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index 0e726e8394..e0b267ce20 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -173,11 +173,13 @@ struct Q_CORE_EXPORT QMapDataBase QtPrivate::RefCount ref; int size; QMapNodeBase header; + QMapNodeBase *mostLeftNode; void rotateLeft(QMapNodeBase *x); void rotateRight(QMapNodeBase *x); void rebalance(QMapNodeBase *x); void freeNodeAndRebalance(QMapNodeBase *z); + void recalcMostLeftNode(); QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left); void freeTree(QMapNodeBase *root, int alignment); @@ -197,8 +199,8 @@ struct QMapData : public QMapDataBase const Node *end() const { return static_cast<const Node *>(&header); } Node *end() { return static_cast<Node *>(&header); } - const Node *begin() const { if (root()) return root()->minimumNode(); return end(); } - Node *begin() { if (root()) return root()->minimumNode(); return end(); } + const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); } + Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); } void deleteNode(Node *z); Node *findNode(const Key &akey) const; @@ -555,6 +557,7 @@ inline QMap<Key, T>::QMap(const QMap<Key, T> &other) if (other.d->header.left) { d->header.left = static_cast<Node *>(other.d->header.left)->copy(d); d->header.left->setParent(&d->header); + d->recalcMostLeftNode(); } } } @@ -780,6 +783,7 @@ Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper() if (!d->ref.deref()) d->destroy(); d = x; + d->recalcMostLeftNode(); } template <class Key, class T> diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp index e07b3fc81e..9c53563a5c 100644 --- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp +++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp @@ -49,6 +49,9 @@ class tst_QMap : public QObject { Q_OBJECT +protected: + template <class KEY, class VALUE> + void sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine); public slots: void init(); private slots: @@ -79,6 +82,7 @@ private slots: void setSharable(); void insert(); + void checkMostLeftNode(); }; typedef QMap<QString, QString> StringMap; @@ -115,6 +119,28 @@ QDebug operator << (QDebug d, const MyClass &c) { return d; } +template <class KEY, class VALUE> +void tst_QMap::sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine) +{ + QString possibleFrom; + possibleFrom.setNum(calledFromLine); + possibleFrom = "Called from line: " + possibleFrom; + int count = 0; + typename QMap<KEY, VALUE>::const_iterator oldite = m.constBegin(); + for (typename QMap<KEY, VALUE>::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) { + count++; + bool oldIteratorIsLarger = i.key() < oldite.key(); + QVERIFY2(!oldIteratorIsLarger, possibleFrom.toUtf8()); + oldite = i; + } + if (m.size() != count) { // Fail + qDebug() << possibleFrom; + QCOMPARE(m.size(), count); + } + if (m.size() == 0) + QVERIFY(m.constBegin() == m.constEnd()); +} + void tst_QMap::init() { MyClass::count = 0; @@ -280,6 +306,7 @@ void tst_QMap::clear() map.insert( "key0", MyClass( "value1" ) ); map.insert( "key1", MyClass( "value2" ) ); map.clear(); + sanityCheckTree(map, __LINE__); QVERIFY( map.isEmpty() ); } QCOMPARE( MyClass::count, int(0) ); @@ -400,6 +427,8 @@ void tst_QMap::swap() m1.swap(m2); QCOMPARE(m1.value(1),QLatin1String("m2[1]")); QCOMPARE(m2.value(0),QLatin1String("m1[0]")); + sanityCheckTree(m1, __LINE__); + sanityCheckTree(m2, __LINE__); } void tst_QMap::operator_eq() @@ -631,7 +660,7 @@ void tst_QMap::lowerUpperBound() void tst_QMap::mergeCompare() { - QMap<int, QString> map1, map2, map3; + QMap<int, QString> map1, map2, map3, map1b, map2b; map1.insert(1,"ett"); map1.insert(3,"tre"); @@ -641,6 +670,13 @@ void tst_QMap::mergeCompare() map2.insert(4,"fyra"); map1.unite(map2); + sanityCheckTree(map1, __LINE__); + + map1b = map1; + map2b = map2; + map2b.insert(0, "nul"); + map1b.unite(map2b); + sanityCheckTree(map1b, __LINE__); QVERIFY(map1.value(1) == "ett"); QVERIFY(map1.value(2) == "tvo"); @@ -958,9 +994,11 @@ void tst_QMap::setSharable() QVERIFY(!map.isDetached()); QVERIFY(copy.isSharedWith(map)); + sanityCheckTree(copy, __LINE__); } map.setSharable(false); + sanityCheckTree(map, __LINE__); QVERIFY(map.isDetached()); QCOMPARE(map.size(), 4); QCOMPARE(const_(map)[4], QString("quatro")); @@ -975,6 +1013,8 @@ void tst_QMap::setSharable() QCOMPARE(const_(copy)[4], QString("quatro")); QCOMPARE(map, copy); + sanityCheckTree(map, __LINE__); + sanityCheckTree(copy, __LINE__); } map.setSharable(true); @@ -1012,5 +1052,57 @@ void tst_QMap::insert() } } +void tst_QMap::checkMostLeftNode() +{ + QMap<int, int> map; + + map.insert(100, 1); + sanityCheckTree(map, __LINE__); + + // insert + map.insert(99, 1); + sanityCheckTree(map, __LINE__); + map.insert(98, 1); + sanityCheckTree(map, __LINE__); + map.insert(97, 1); + sanityCheckTree(map, __LINE__); + map.insert(96, 1); + sanityCheckTree(map, __LINE__); + map.insert(95, 1); + + // remove + sanityCheckTree(map, __LINE__); + map.take(95); + sanityCheckTree(map, __LINE__); + map.remove(96); + sanityCheckTree(map, __LINE__); + map.erase(map.begin()); + sanityCheckTree(map, __LINE__); + map.remove(97); + sanityCheckTree(map, __LINE__); + map.remove(98); + sanityCheckTree(map, __LINE__); + map.remove(99); + sanityCheckTree(map, __LINE__); + map.remove(100); + sanityCheckTree(map, __LINE__); + map.insert(200, 1); + QCOMPARE(map.constBegin().key(), 200); + sanityCheckTree(map, __LINE__); + // remove the non left most node + map.insert(202, 2); + map.insert(203, 3); + map.insert(204, 4); + map.remove(202); + sanityCheckTree(map, __LINE__); + map.remove(203); + sanityCheckTree(map, __LINE__); + map.remove(204); + sanityCheckTree(map, __LINE__); + // erase last item + map.erase(map.begin()); + sanityCheckTree(map, __LINE__); +} + QTEST_APPLESS_MAIN(tst_QMap) #include "tst_qmap.moc" diff --git a/tests/benchmarks/corelib/tools/qmap/main.cpp b/tests/benchmarks/corelib/tools/qmap/main.cpp index c3b9c18cd2..4d9833b7a1 100644 --- a/tests/benchmarks/corelib/tools/qmap/main.cpp +++ b/tests/benchmarks/corelib/tools/qmap/main.cpp @@ -61,6 +61,7 @@ private slots: void iteration(); void toStdMap(); + void iterator_begin(); }; @@ -172,6 +173,22 @@ void tst_QMap::toStdMap() } } +void tst_QMap::iterator_begin() +{ + QMap<int, int> map; + for (int i = 0; i < 100000; ++i) + map.insert(i, i); + + QBENCHMARK { + for (int i = 0; i < 100000; ++i) { + QMap<int, int>::const_iterator it = map.constBegin(); + QMap<int, int>::const_iterator end = map.constEnd(); + if (it == end) // same as if (false) + ++it; + } + } +} + QTEST_MAIN(tst_QMap) #include "main.moc" |