diff options
| author | Andrei Golubev <andrei.golubev@qt.io> | 2020-11-04 17:58:12 +0100 |
|---|---|---|
| committer | Andrei Golubev <andrei.golubev@qt.io> | 2020-11-09 17:36:31 +0100 |
| commit | 250b69ace47923b51aaeaaea39e0ffc638fa4b4a (patch) | |
| tree | bc860cd91d834b0dffcf843369f46eb965766b43 /src/corelib | |
| parent | 9ede51d2140c026c03d1328de8c2704e9ee2f678 (diff) | |
Fix QArrayDataOps generic and relocatable emplace()
Emplace() implemented with std::rotate is just awful on my system
(Ubuntu 18.04 GCC 7.5.0). Custom code is much faster, so go for
it. Cannot really use insert() code, which is also fast, because
it doesn't forward-reference values but copies them always
Changes in performance (approximately) for emplacing 100k elements
into the middle:
Complex 7600ms -> 1700ms
Movable 7600ms -> 200ms
Task-number: QTBUG-86583
Change-Id: If883c9b8498a89e757f3806aea11f8fd3aa3c709
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Diffstat (limited to 'src/corelib')
| -rw-r--r-- | src/corelib/tools/qarraydataops.h | 107 |
1 files changed, 100 insertions, 7 deletions
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 957fa9e218f..1fd7e99c42e 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -772,10 +772,31 @@ public: Q_ASSERT(where >= this->begin() && where <= this->end()); Q_ASSERT(this->freeSpaceAtEnd() >= 1); - createInPlace(this->end(), std::forward<Args>(args)...); - ++this->size; + if (where == this->end()) { + createInPlace(this->end(), std::forward<Args>(args)...); + ++this->size; + } else { + T tmp(std::forward<Args>(args)...); + + T *const end = this->end(); + T *readIter = end - 1; + T *writeIter = end; + + // Create new element at the end + new (writeIter) T(std::move(*readIter)); + ++this->size; + + // Move assign over existing elements + while (readIter != where) { + --readIter; + --writeIter; + *writeIter = std::move(*readIter); + } - std::rotate(where, this->end() - 1, this->end()); + // Assign new element + --writeIter; + *writeIter = std::move(tmp); + } } template <typename iterator, typename ...Args> @@ -785,11 +806,35 @@ public: Q_ASSERT(where >= this->begin() && where <= this->end()); Q_ASSERT(this->freeSpaceAtBegin() >= 1); - createInPlace(this->begin() - 1, std::forward<Args>(args)...); - --this->ptr; - ++this->size; + if (where == this->begin()) { + createInPlace(this->begin() - 1, std::forward<Args>(args)...); + --this->ptr; + ++this->size; + } else { + T tmp(std::forward<Args>(args)...); + + T *const begin = this->begin(); + T *readIter = begin; + T *writeIter = begin - 1; + + // Create new element at the beginning + new (writeIter) T(std::move(*readIter)); + --this->ptr; + ++this->size; + + ++readIter; + ++writeIter; + + // Move assign over existing elements + while (readIter != where) { + *writeIter = std::move(*readIter); + ++readIter; + ++writeIter; + } - std::rotate(this->begin(), this->begin() + 1, where); + // Assign new element + *writeIter = std::move(tmp); + } } void erase(T *b, T *e) @@ -998,6 +1043,54 @@ public: // use moving insert using QGenericArrayOps<T>::insert; + template<typename iterator, typename... Args> + void emplace(iterator where, Args &&... args) + { + emplace(GrowsForwardTag {}, where, std::forward<Args>(args)...); + } + + template<typename iterator, typename... Args> + void emplace(GrowsForwardTag, iterator where, Args &&... args) + { + Q_ASSERT(!this->isShared()); + Q_ASSERT(where >= this->begin() && where <= this->end()); + Q_ASSERT(this->freeSpaceAtEnd() >= 1); + + if (where == this->end()) { + this->createInPlace(where, std::forward<Args>(args)...); + } else { + T tmp(std::forward<Args>(args)...); + typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace; + ReversibleDisplace displace(where, this->end(), 1); + this->createInPlace(where, std::move(tmp)); + displace.commit(); + } + ++this->size; + } + + template<typename iterator, typename... Args> + void emplace(GrowsBackwardsTag, iterator where, Args &&... args) + { + Q_ASSERT(!this->isShared()); + Q_ASSERT(where >= this->begin() && where <= this->end()); + Q_ASSERT(this->freeSpaceAtBegin() >= 1); + + if (where == this->begin()) { + this->createInPlace(where - 1, std::forward<Args>(args)...); + } else { + T tmp(std::forward<Args>(args)...); + typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace; + ReversibleDisplace displace(this->begin(), where, -1); + this->createInPlace(where - 1, std::move(tmp)); + displace.commit(); + } + --this->ptr; + ++this->size; + } + + // use moving emplace + using QGenericArrayOps<T>::emplace; + void erase(T *b, T *e) { erase(GrowsForwardTag{}, b, e); } |