From 7aac63a2672a4f34a243956685bc69ae00423b70 Mon Sep 17 00:00:00 2001 From: Edward Welbourne Date: Mon, 19 Jul 2021 17:17:36 +0200 Subject: 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 Reviewed-by: Andrei Golubev (cherry picked from commit 33c916577389fa6607b0b2f6a78da4a0eb485000) Reviewed-by: Qt Cherry-pick Bot --- src/corelib/tools/qmap.h | 28 +++++++++++++++++++--------- 1 file 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 -** 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 &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) -- cgit v1.2.3