diff options
author | Andrei Golubev <andrei.golubev@qt.io> | 2020-10-28 18:14:21 +0100 |
---|---|---|
committer | Lars Knoll <lars.knoll@qt.io> | 2020-11-04 11:22:03 +0100 |
commit | 2e8656779ac3eee8567ce2bf8eda233f4c5e3620 (patch) | |
tree | e31419d216afba652b7f6b6df11a1519c2690db4 /src | |
parent | 8f7016252a846e30efb617d2e20e929579772456 (diff) |
Introduce QADP::reallocateGrow()
Added realloc() code path to QMovableArrayOps
Implemented fast realloc() based growing for QADP and used it in
QList::emplaceBack. This gives quite a bit of speedup and shows better
results than 5.15 at 100k+ iterations of "list.append(elem)", meanwhile
also closing a gap between movable types
Task-number: QTBUG-87330
Change-Id: I42fc182ecd93c85600dac622385152fc57735da8
Reviewed-by: MÃ¥rten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Diffstat (limited to 'src')
-rw-r--r-- | src/corelib/tools/qarraydata.cpp | 3 | ||||
-rw-r--r-- | src/corelib/tools/qarraydataops.h | 11 | ||||
-rw-r--r-- | src/corelib/tools/qarraydatapointer.h | 19 | ||||
-rw-r--r-- | src/corelib/tools/qlist.h | 20 |
4 files changed, 49 insertions, 4 deletions
diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp index 3217e87cc8..2bf3e9bacc 100644 --- a/src/corelib/tools/qarraydata.cpp +++ b/src/corelib/tools/qarraydata.cpp @@ -236,6 +236,7 @@ QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer, qsizetype headerSize = sizeof(QArrayData); qsizetype allocSize = calculateBlockSize(capacity, objectSize, headerSize, option); qptrdiff offset = dataPointer ? reinterpret_cast<char *>(dataPointer) - reinterpret_cast<char *>(data) : headerSize; + Q_ASSERT(offset > 0); allocSize = reserveExtraBytes(allocSize); if (Q_UNLIKELY(allocSize < 0)) // handle overflow. cannot reallocate reliably @@ -245,6 +246,8 @@ QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer, if (header) { header->alloc = uint(capacity); dataPointer = reinterpret_cast<char *>(header) + offset; + } else { + dataPointer = nullptr; } return qMakePair(static_cast<QArrayData *>(header), dataPointer); } diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 730476c213..a864ac4c2b 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -854,6 +854,10 @@ template <class T> struct QMovableArrayOps : QGenericArrayOps<T> { +protected: + typedef QTypedArrayData<T> Data; + +public: // using QGenericArrayOps<T>::appendInitialize; // using QGenericArrayOps<T>::copyAppend; // using QGenericArrayOps<T>::moveAppend; @@ -993,6 +997,13 @@ struct QMovableArrayOps (b++)->~T(); } while (b != e); } + + void reallocate(qsizetype alloc, QArrayData::AllocationOption option) + { + auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, option); + this->d = pair.first; + this->ptr = pair.second; + } }; template <class T, class = void> diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index d483a5a5e5..20015cbadd 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -244,6 +244,25 @@ public: return lhs.data() != rhs.data() || lhs.size != rhs.size; } + static void reallocateGrow(QArrayDataPointer &from, qsizetype n) + { + Q_ASSERT(n > 0); + + if constexpr (!QTypeInfo<T>::isRelocatable || alignof(T) > alignof(std::max_align_t)) { + QArrayDataPointer dd(allocateGrow(from, n, QArrayData::AllocateAtEnd)); + dd->copyAppend(from.data(), from.data() + from.size); + from.swap(dd); + } else { + if (from.needsDetach()) { + QArrayDataPointer dd(allocateGrow(from, n, QArrayData::AllocateAtEnd)); + dd->copyAppend(from.data(), from.data() + from.size); + from.swap(dd); + } else { + from->reallocate(from.constAllocatedCapacity() - from.freeSpaceAtEnd() + n, QArrayData::Grow); // fast path + } + } + } + private: [[nodiscard]] QPair<Data *, T *> clone() const { diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h index f3e78b4cdb..3ea932c0fe 100644 --- a/src/corelib/tools/qlist.h +++ b/src/corelib/tools/qlist.h @@ -770,10 +770,22 @@ template<typename... Args> inline typename QList<T>::reference QList<T>::emplaceBack(Args &&... args) { if (d->needsDetach() || !d.freeSpaceAtEnd()) { - DataPointer detached(DataPointer::allocateGrow(d, 1, QArrayData::AllocateAtEnd)); - detached->copyAppend(constBegin(), constEnd()); - detached->emplace(detached.end(), std::forward<Args>(args)...); - d.swap(detached); + // condition below should follow the condition in QArrayDataPointer::reallocateGrow() + if constexpr (!QTypeInfo<T>::isRelocatable || alignof(T) > alignof(std::max_align_t)) { + // avoid taking a temporary copy of Args + DataPointer detached(DataPointer::allocateGrow(d, 1, QArrayData::AllocateAtEnd)); + detached->copyAppend(constBegin(), constEnd()); + detached->emplace(detached.end(), std::forward<Args>(args)...); + d.swap(detached); + } else { + // Create an element here to handle cases when a user moves the element + // from a container to the same container. This is required as we call + // reallocate, which could delete the data args points to. + // This should be optimised to only take the copy when really required. + T tmp(std::forward<Args>(args)...); + DataPointer::reallocateGrow(d, 1); + d->emplace(d.end(), std::move(tmp)); + } } else { d->emplace(d.end(), std::forward<Args>(args)...); } |