QHash: Return void from QHashPrivate::Data::erase()

This removes some calculations that are not required in
80% of the cases where d->erase() is being called (as
the return value is ignored). When removing lots of
elements from the hash, the ++it could loop quite a
bit until it found the next valid item in the hash.

This chain of changes combined improve the overall performance of
QHash by 10-50% depending on the operation. Deletes are twice
as fast, reads around 20% faster, inserts around 10% faster.

Task-number: QTBUG-91739
Fixes: QTBUG-98436
Change-Id: I2d82a7c9dd1dd0a4da8402e6d95bfd620caeff3a
Reviewed-by: Marc Mutz <marc.mutz@qt.io>

1 files changed, 11 insertions, 9 deletions

diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 1ad28b6d23..c4b4098c0f 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -746,21 +746,19 @@ struct Data
         return { it.toIterator(this), false };
     }
 
-    iterator erase(Bucket bucket) noexcept(std::is_nothrow_destructible<Node>::value)
+    void erase(Bucket bucket) noexcept(std::is_nothrow_destructible<Node>::value)
     {
         Q_ASSERT(bucket.span->hasNode(bucket.index));
         bucket.span->erase(bucket.index);
         --size;
 
-        Bucket originalBucket = bucket;
-
         // re-insert the following entries to avoid holes
         Bucket next = bucket;
         while (true) {
             next.advanceWrapped(this);
             size_t offset = next.offset();
             if (offset == SpanConstants::UnusedEntry)
-                break;
+                return;
             size_t hash = QHashPrivate::calculateHash(next.nodeAtOffset(offset).key, seed);
             Bucket newBucket(this, GrowthPolicy::bucketForHash(numBuckets, hash));
             while (true) {
@@ -781,9 +779,6 @@ struct Data
                 newBucket.advanceWrapped(this);
             }
         }
-        if (originalBucket.toBucketIndex(this) == numBuckets - 1 || originalBucket.isUnused())
-            return ++(originalBucket.toIterator(this));
-        return originalBucket.toIterator(this);
     }
 
     ~Data()
@@ -1242,7 +1237,10 @@ public:
         iterator i = iterator{d->detachedIterator(it.i)};
         typename Data::Bucket bucket(i.i);
 
-        return iterator(d->erase(bucket));
+        d->erase(bucket);
+        if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
+            ++i;
+        return i;
     }
 
     QPair<iterator, iterator> equal_range(const Key &key)
@@ -1880,7 +1878,11 @@ public:
             if (i.e == &i.i.node()->value) {
                 // last remaining entry, erase
                 typename Data::Bucket bucket(i.i);
-                i = iterator(d->erase(bucket));
+                d->erase(bucket);
+                if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
+                    i = iterator(++iter.i);
+                else // 'i' currently has a nullptr chain. So, we must recreate it
+                    i = iterator(bucket.toIterator(d));
             } else {
                 i = iterator(++iter.i);
             }