Fix quadratic performance hit in Q(Multi)Map::insert() with hint

The insert() overloads that took a const_iterator started by calling
std::distance(begin(), pos) - which has a cost linear in how far pos
is from begin() - in order to, after detach()ing, obtain an iterator
at the same offset from the new begin(), using std::next() - also
linear. This leads to quadratic behavior when large numbers of entries
are added with constEnd() as the hint, which happened to be tested by
tst_bench_qmap. That wasn't running, due to some assertion failures,
but once those were fixed the hinted tests timed out after five
minutes, where their unhinted peers completed comfortably within a
second.

Check whether detach() is even needed and bypass the std::distance() /
std::next() linear delay when it isn't. This brings the hinted tests
down to running faster than their unhinted equivalents.

Task-number: QTBUG-91713
Change-Id: I6b705bf8fc34e67aed2ac4b3312a836e105ca2f2
Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
(cherry picked from commit 33c916577389fa6607b0b2f6a78da4a0eb485000)
Reviewed-by: Qt Cherry-pick Bot <cherrypick_bot@qt-project.org>

1 files changed, 19 insertions, 9 deletions

diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index b64989eadd..f71e95dd82 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -1,7 +1,7 @@
 /****************************************************************************
 **
 ** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
-** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2021 The Qt Company Ltd.
 ** Contact: https://www.qt.io/licensing/
 **
 ** This file is part of the QtCore module of the Qt Toolkit.
@@ -668,10 +668,15 @@ public:
     iterator insert(const_iterator pos, const Key &key, const T &value)
     {
         // TODO: improve. In case of assignment, why copying first?
-        auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0;
-        detach();
-        auto detachedPos = std::next(d->m.cbegin(), posDistance);
-        return iterator(d->m.insert_or_assign(detachedPos, key, value));
+        typename Map::const_iterator dpos;
+        if (!d || d.isShared()) {
+            auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0;
+            detach();
+            dpos = std::next(d->m.cbegin(), posDistance);
+        } else {
+            dpos = pos.i;
+        }
+        return iterator(d->m.insert_or_assign(dpos, key, value));
     }
 
     void insert(const QMap<Key, T> &map)
@@ -1335,10 +1340,15 @@ public:
 
     iterator insert(const_iterator pos, const Key &key, const T &value)
     {
-        auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0;
-        detach();
-        auto detachedPos = std::next(d->m.cbegin(), posDistance);
-        return iterator(d->m.insert(detachedPos, {key, value}));
+        typename Map::const_iterator dpos;
+        if (!d || d.isShared()) {
+            auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0;
+            detach();
+            dpos = std::next(d->m.cbegin(), posDistance);
+        } else {
+            dpos = pos.i;
+        }
+        return iterator(d->m.insert(dpos, {key, value}));
     }
 
 #if QT_DEPRECATED_SINCE(6, 0)