From 7eed57511a786861b513af089aef48651fed7891 Mon Sep 17 00:00:00 2001 From: Andrei Golubev Date: Thu, 29 Oct 2020 14:25:48 +0100 Subject: QArrayDataPointer: redesign (and simplify) growth policy It looks like we can drastically simplify the way QADP grows without sacrificing much: 1. append-only use cases should have the same performance as before 2. prepend-only use cases should (with the help of other commits) get additional performance speedup 3. mid-insertion is harder to reason about, but it is either unchanged or benefits a bit as there's some free space at both ends now 4. mixed prepend/append cases are weird and would keep excess free space around but this is less critical and overall less used AFAIK Now, QList would actually start to feel like a double-ended container instead of "it's QVector but with faster prepend". This commit should help close the performance gap between 6.0 and 5.15 as well As a drawback, we will most likely have more space allocated in mixed and mid-insert cases. This needs to be checked Task-number: QTBUG-86583 Change-Id: I7c6ede896144920fe01862b9fe789c8fdfc11f80 Reviewed-by: Lars Knoll Reviewed-by: Thiago Macieira --- src/corelib/text/qbytearray.cpp | 6 +++++- src/corelib/text/qstring.cpp | 6 +++++- src/corelib/tools/qarraydataops.h | 22 ++++++------------- src/corelib/tools/qarraydatapointer.h | 25 +++++++++------------- .../corelib/tools/qarraydata/tst_qarraydata.cpp | 22 +++++++++++++------ 5 files changed, 42 insertions(+), 39 deletions(-) diff --git a/src/corelib/text/qbytearray.cpp b/src/corelib/text/qbytearray.cpp index c6dbf4c7aa..e550224c4c 100644 --- a/src/corelib/text/qbytearray.cpp +++ b/src/corelib/text/qbytearray.cpp @@ -1728,7 +1728,11 @@ void QByteArray::reallocGrowData(qsizetype alloc, Data::ArrayOptions options) if (!alloc) // expected to always allocate alloc = 1; - if (d->needsDetach()) { + // when we're requested to grow backwards, it means we're in prepend-like + // case. realloc() is good, but we might actually get more free space at the + // beginning with a call to allocateGrow, so prefer that instead + const bool preferAllocateGrow = options & Data::GrowsBackwards; + if (d->needsDetach() || preferAllocateGrow) { const auto newSize = qMin(alloc, d.size); DataPointer dd(DataPointer::allocateGrow(d, alloc, newSize, options)); dd->copyAppend(d.data(), d.data() + newSize); diff --git a/src/corelib/text/qstring.cpp b/src/corelib/text/qstring.cpp index 26d0a7acc8..d77ade226e 100644 --- a/src/corelib/text/qstring.cpp +++ b/src/corelib/text/qstring.cpp @@ -2525,7 +2525,11 @@ void QString::reallocGrowData(qsizetype alloc, Data::ArrayOptions options) if (!alloc) // expected to always allocate alloc = 1; - if (d->needsDetach()) { + // when we're requested to grow backwards, it means we're in prepend-like + // case. realloc() is good, but we might actually get more free space at the + // beginning with a call to allocateGrow, so prefer that instead + const bool preferAllocateGrow = options & Data::GrowsBackwards; + if (d->needsDetach() || preferAllocateGrow) { const auto newSize = qMin(alloc, d.size); DataPointer dd(DataPointer::allocateGrow(d, alloc, newSize, options)); dd->copyAppend(d.data(), d.data() + newSize); diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 9626f4eeff..3b95d04fa8 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -1320,23 +1320,15 @@ public: const qsizetype freeAtBegin = this->freeSpaceAtBegin(); const qsizetype freeAtEnd = this->freeSpaceAtEnd(); - const qsizetype capacity = this->constAllocatedCapacity(); - if (this->size > 0 && where == this->begin()) { // prepend - // Qt5 QList in prepend: not enough space at begin && 33% full - // Now (below): - return freeAtBegin < n && (this->size >= (capacity / 3)); + // Idea: always reallocate when not enough space at the corresponding end + if (where == this->end()) { // append or size == 0 + return freeAtEnd < n; + } else if (where == this->begin()) { // prepend + return freeAtBegin < n; + } else { // general insert + return (freeAtBegin < n && freeAtEnd < n); } - - if (where == this->end()) { // append - // Qt5 QList in append: not enough space at end && less than 66% free space at front - // Now (below): - return freeAtEnd < n && !((freeAtBegin - n) >= (2 * capacity / 3)); - } - - // Qt5 QList in insert: no free space - // Now: no free space OR not enough space on either of the sides (bad perf. case) - return (freeAtBegin + freeAtEnd) < n || (freeAtBegin < n && freeAtEnd < n); } // using Base::truncate; diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index ad90b1d580..3cabeca649 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -222,21 +222,16 @@ public: if (!valid || !grows) return QArrayDataPointer(header, dataPtr); - // when growing, special rules apply to memory layout - - if (from.needsDetach()) { - // When detaching: the free space reservation is biased towards - // append as in Qt5 QList. If we're growing backwards, put the data - // in the middle instead of at the end - assuming that prepend is - // uncommon and even initial prepend will eventually be followed by - // at least some appends. - if (options & Data::GrowsBackwards) - dataPtr += (header->alloc - newSize) / 2; - } else { - // When not detaching: fake ::realloc() policy - preserve existing - // free space at beginning. - dataPtr += from.freeSpaceAtBegin(); - } + // must always hold true, as valid is the first condition we check and + // if-statement short-circuits + Q_ASSERT(valid); + + // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning + // * when growing forward, adjust by the previous data pointer offset + + // TODO: what's with CapacityReserved? + dataPtr += (options & Data::GrowsBackwards) ? (header->alloc - newSize) / 2 + : from.freeSpaceAtBegin(); return QArrayDataPointer(header, dataPtr); } diff --git a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp index 4c520d0eaa..b7d07f836e 100644 --- a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp +++ b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp @@ -2094,6 +2094,7 @@ void tst_QArrayData::dataPointerAllocate() using DataPointer = QArrayDataPointer; auto oldDataPointer = createDataPointer(capacity, initValue); + oldDataPointer->insert(oldDataPointer.begin(), 1, initValue); oldDataPointer->insert(oldDataPointer.begin(), 1, initValue); // trigger prepend QVERIFY(!oldDataPointer.needsDetach()); @@ -2105,11 +2106,14 @@ void tst_QArrayData::dataPointerAllocate() QVERIFY(newAlloc > oldDataPointer.constAllocatedCapacity()); QCOMPARE(freeAtBegin + freeAtEnd, newAlloc); - // when not detached, the behavior is the same as of ::realloc - if (allocationOptions & (QArrayData::GrowsForward | QArrayData::GrowsBackwards)) + if (allocationOptions & QArrayData::GrowsBackwards) { + // bad check, but will suffice for now, hopefully + QCOMPARE(freeAtBegin, (newAlloc - newSize) / 2); + } else if (allocationOptions & QArrayData::GrowsForward) { QCOMPARE(freeAtBegin, oldDataPointer.freeSpaceAtBegin()); - else + } else { QCOMPARE(freeAtBegin, 0); + } }; for (size_t n : {10, 512, 1000}) { @@ -2186,14 +2190,18 @@ void tst_QArrayData::dataPointerAllocateAlignedWithReallocate() QVERIFY(a.freeSpaceAtBegin() == 0); } QCOMPARE(a.freeSpaceAtBegin(), b.freeSpaceAtBegin()); + const auto oldSpaceAtBeginA = a.freeSpaceAtBegin(); a->reallocate(100, newFlags); b = QArrayDataPointer::allocateGrow(b, 100, b.size, newFlags); - // It is enough to test that the behavior of reallocate is the same as the - // behavior of allocate w.r.t. pointer adjustment in case of - // GrowsBackwards. Actual values are not that interesting - QCOMPARE(a.freeSpaceAtBegin(), b.freeSpaceAtBegin()); + // NB: when growing backwards, the behavior is not aligned + if (!(newFlags & QArrayData::GrowsBackwards)) { + QCOMPARE(a.freeSpaceAtBegin(), b.freeSpaceAtBegin()); + } else { + QCOMPARE(a.freeSpaceAtBegin(), oldSpaceAtBeginA); + QCOMPARE(b.freeSpaceAtBegin(), b.constAllocatedCapacity() / 2); + } } #ifndef QT_NO_EXCEPTIONS -- cgit v1.2.3