diff options
author | Thiago Macieira <thiago.macieira@intel.com> | 2023-08-22 12:34:43 -0700 |
---|---|---|
committer | Thiago Macieira <thiago.macieira@intel.com> | 2023-09-03 17:43:24 -0700 |
commit | 961620824ca0ae764b3c6ce98b16ecce951168c8 (patch) | |
tree | 90009ec3cab0693a68a29a4f6a3e63ba306d29af | |
parent | d752da1857358726b89027ac039c20c1cd696b36 (diff) |
QArrayData: make calculateBlockSize() account for the extra null element
Instead of adding it after the block size was calculated. This makes no
difference for non-growing (exact) blocks. For growing blocks, this
means we take that extra element into account before rounding to the
next power of two, instead of after. That results in a change of the
thresholds of when a block grows and also what capacity it will
contain.
For example, for a QString growing to 22-25 elements:
Request | Previously | Now |
elements | bytes | malloc()ed | capacity() | malloc()ed | capacity() |
22 | 44 | 66 | 24 | 64 | 23 |
23 | 46 | 66 | 24 | 64 | 23 |
24 | 48 | 66 | 24 | 128 | 55 |
25 | 50 | 130 | 56 | 128 | 55 |
To avoid wasting elementSize - 2 bytes in this footer, we only include
this footer if elementSize <= 2. Thus, for a QList<int> growing to 11-13
elements:
Request | Previously | Now |
elements | bytes | malloc()ed | capacity() | malloc()ed | capacity() |
11 | 44 | 66 | 12 | 64 | 12 |
12 | 48 | 66 | 12 | 128 | 28 |
13 | 52 | 130 | 28 | 128 | 28 |
In both cases, we now only allocate powers of two while growing, which
may be beneficial to some allocators.
Pick-to: 6.6
Change-Id: Ifa1111900d6945ea8e05fffd177dcb96e251d0a1
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
-rw-r--r-- | src/corelib/tools/qarraydata.cpp | 36 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp | 2 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qlist/tst_qlist.cpp | 3 |
3 files changed, 18 insertions, 23 deletions
diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp index 4306e00442..56f1461644 100644 --- a/src/corelib/tools/qarraydata.cpp +++ b/src/corelib/tools/qarraydata.cpp @@ -107,26 +107,24 @@ qCalculateGrowingBlockSize(qsizetype elementCount, qsizetype elementSize, qsizet return result; } -/*! - \internal - - Returns \a allocSize plus extra reserved bytes necessary to store '\0'. - */ -static inline qsizetype reserveExtraBytes(qsizetype allocSize) -{ - // We deal with QByteArray and QString only - constexpr qsizetype extra = qMax(sizeof(QByteArray::value_type), sizeof(QString::value_type)); - if (Q_UNLIKELY(allocSize < 0)) - return -1; - if (Q_UNLIKELY(qAddOverflow(allocSize, extra, &allocSize))) - return -1; - return allocSize; -} +/* + Calculate the byte size for a block of \a capacity objects of size \a + objectSize, with a header of size \a headerSize. If the \a option is + QArrayData::Grow, the capacity itself adjusted up, preallocating room for + more elements to be added later; otherwise, it is an exact calculation. + Returns a structure containing the size in bytes and elements available. +*/ static inline CalculateGrowingBlockSizeResult calculateBlockSize(qsizetype capacity, qsizetype objectSize, qsizetype headerSize, QArrayData::AllocationOption option) { - // Calculate the byte size + // Adjust the header size up to account for the trailing null for QString + // and QByteArray. This is not checked for overflow because headers sizes + // should not be anywhere near the overflow limit. + constexpr qsizetype FooterSize = qMax(sizeof(QString::value_type), sizeof(QByteArray::value_type)); + if (objectSize <= FooterSize) + headerSize += FooterSize; + // allocSize = objectSize * capacity + headerSize, but checked for overflow // plus padded to grow in size if (option == QArrayData::Grow) { @@ -182,7 +180,7 @@ void *QArrayData::allocate(QArrayData **dptr, qsizetype objectSize, qsizetype al auto blockSize = calculateBlockSize(capacity, objectSize, headerSize, option); capacity = blockSize.elementCount; - qsizetype allocSize = reserveExtraBytes(blockSize.size); + qsizetype allocSize = blockSize.size; if (Q_UNLIKELY(allocSize < 0)) { // handle overflow. cannot allocate reliably *dptr = nullptr; return nullptr; @@ -219,10 +217,6 @@ QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer, Q_ASSERT(offset > 0); Q_ASSERT(offset <= allocSize); // equals when all free space is at the beginning - allocSize = reserveExtraBytes(allocSize); - if (Q_UNLIKELY(allocSize < 0)) // handle overflow. cannot reallocate reliably - return qMakePair(data, dataPointer); - QArrayData *header = static_cast<QArrayData *>(::realloc(data, size_t(allocSize))); if (header) { header->alloc = capacity; diff --git a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp index c435ab0d9d..20f1a3ab13 100644 --- a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp +++ b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp @@ -484,7 +484,7 @@ void tst_QArrayData::allocate() keeper.headers.append(data); if (grow) - QVERIFY(data->allocatedCapacity() > capacity); + QCOMPARE_GE(data->allocatedCapacity(), capacity); else QCOMPARE(data->allocatedCapacity(), capacity); diff --git a/tests/auto/corelib/tools/qlist/tst_qlist.cpp b/tests/auto/corelib/tools/qlist/tst_qlist.cpp index 1d86c0a1f2..06ae1c4fb8 100644 --- a/tests/auto/corelib/tools/qlist/tst_qlist.cpp +++ b/tests/auto/corelib/tools/qlist/tst_qlist.cpp @@ -1087,6 +1087,7 @@ void tst_QList::appendList() const // Using operators // << QList<ConstructionCounted> v6; + v6.reserve(4); v6 << (QList<ConstructionCounted>() << 1 << 2); v6 << (QList<ConstructionCounted>() << 3 << 4); QCOMPARE(v6, expectedFour); @@ -3759,7 +3760,7 @@ void tst_QList::stability_append() const std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); QList<T> src(1, SimpleValue<T>::at(0)); v.append(src.begin(), src.end()); - QVERIFY(v.size() < v.capacity()); + QCOMPARE_LE(v.size(), v.capacity()); for (int i = 0; i < v.capacity() - v.size(); ++i) { auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); |