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>

1 files changed, 15 insertions, 21 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;