diff options
author | Andrei Golubev <andrei.golubev@qt.io> | 2020-08-17 09:48:20 +0200 |
---|---|---|
committer | Andrei Golubev <andrei.golubev@qt.io> | 2020-08-29 14:20:06 +0200 |
commit | a2b1b0292d3d9909a690ba701f0a447cdf1a66fa (patch) | |
tree | 5dfa51a1e6a7e37c59acef510c83331968fb5941 | |
parent | 4b9ec005340ac0d8aa103009c0f8ceda623de8cc (diff) |
Prepend optimize QString
Added prepend optimization to QString
Task-number: QTBUG-84320
Change-Id: Iaa8df790a10c56ecceb06f7143718fb94874ce76
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
-rw-r--r-- | src/corelib/text/qstring.cpp | 142 | ||||
-rw-r--r-- | src/corelib/text/qstring.h | 17 | ||||
-rw-r--r-- | tests/auto/corelib/text/qstring/tst_qstring.cpp | 103 |
3 files changed, 203 insertions, 59 deletions
diff --git a/src/corelib/text/qstring.cpp b/src/corelib/text/qstring.cpp index d0fc3e071f..68b7011f15 100644 --- a/src/corelib/text/qstring.cpp +++ b/src/corelib/text/qstring.cpp @@ -2316,8 +2316,9 @@ void QString::resize(qsizetype size) if (size < 0) size = 0; - if (d->needsDetach() || size > capacity()) - reallocData(size_t(size) + 1u, true); + const auto capacityAtEnd = capacity() - d.freeSpaceAtBegin(); + if (d->needsDetach() || size > capacityAtEnd) + reallocData(size_t(size) + 1u, d->detachFlags() | Data::GrowsForward); d.size = size; if (d->allocatedCapacity()) d.data()[size] = 0; @@ -2395,13 +2396,14 @@ void QString::resize(qsizetype size, QChar fillChar) \sa reserve(), capacity() */ -void QString::reallocData(size_t alloc, bool grow) +void QString::reallocData(size_t alloc, Data::ArrayOptions allocOptions) { - auto allocOptions = d->detachFlags(); - if (grow) - allocOptions |= QArrayData::GrowsForward; + // there's a case of slow reallocate path where we need to memmove the data + // before a call to ::realloc(), meaning that there's an extra "heavy" + // operation. just prefer ::malloc() branch in this case + const bool slowReallocatePath = d.freeSpaceAtBegin() > 0; - if (d->needsDetach()) { + if (d->needsDetach() || slowReallocatePath) { DataPointer dd(Data::allocate(alloc, allocOptions), qMin(qsizetype(alloc) - 1, d.size)); if (dd.size > 0) ::memcpy(dd.data(), d.data(), dd.size * sizeof(QChar)); @@ -2412,6 +2414,19 @@ void QString::reallocData(size_t alloc, bool grow) } } +void QString::reallocGrowData(size_t alloc, Data::ArrayOptions options) +{ + if (d->needsDetach()) { + const auto newSize = qMin(qsizetype(alloc) - 1, d.size); + DataPointer dd(DataPointer::allocateGrow(d, alloc, newSize, options)); + dd->copyAppend(d.data(), d.data() + newSize); + dd.data()[dd.size] = 0; + d = dd; + } else { + d->reallocate(alloc, options); + } +} + /*! \fn void QString::clear() Clears the contents of the string and makes it null. @@ -2447,7 +2462,8 @@ QString &QString::operator=(const QString &other) noexcept */ QString &QString::operator=(QLatin1String other) { - if (isDetached() && other.size() <= capacity()) { // assumes d->alloc == 0 -> !isDetached() (sharedNull) + const qsizetype capacityAtEnd = capacity() - d.freeSpaceAtBegin(); + if (isDetached() && other.size() <= capacityAtEnd) { // assumes d->alloc == 0 -> !isDetached() (sharedNull) d.size = other.size(); d.data()[other.size()] = 0; qt_from_latin1(d.data(), other.latin1(), other.size()); @@ -2495,7 +2511,8 @@ QString &QString::operator=(QLatin1String other) */ QString &QString::operator=(QChar ch) { - if (isDetached() && capacity() >= 1) { // assumes d->alloc == 0 -> !isDetached() (sharedNull) + const qsizetype capacityAtEnd = capacity() - d.freeSpaceAtBegin(); + if (isDetached() && capacityAtEnd >= 1) { // assumes d->alloc == 0 -> !isDetached() (sharedNull) // re-use existing capacity: d.data()[0] = ch.unicode(); d.data()[1] = 0; @@ -2516,8 +2533,7 @@ QString &QString::operator=(QChar ch) \snippet qstring/main.cpp 26 - If the given \a position is greater than size(), the array is - first extended using resize(). + If the given \a position is greater than size(), this string is extended. \sa append(), prepend(), replace(), remove() */ @@ -2530,8 +2546,7 @@ QString &QString::operator=(QChar ch) Inserts the string view \a str at the given index \a position and returns a reference to this string. - If the given \a position is greater than size(), the array is - first extended using resize(). + If the given \a position is greater than size(), this string is extended. */ @@ -2543,8 +2558,7 @@ QString &QString::operator=(QChar ch) Inserts the C string \a str at the given index \a position and returns a reference to this string. - If the given \a position is greater than size(), the array is - first extended using resize(). + If the given \a position is greater than size(), this string is extended. This function is not available when \c QT_NO_CAST_FROM_ASCII is defined. @@ -2561,8 +2575,7 @@ QString &QString::operator=(QChar ch) Inserts the byte array \a str at the given index \a position and returns a reference to this string. - If the given \a position is greater than size(), the array is - first extended using resize(). + If the given \a position is greater than size(), this string is extended. This function is not available when \c QT_NO_CAST_FROM_ASCII is defined. @@ -2610,13 +2623,23 @@ QString& QString::insert(qsizetype i, const QChar *unicode, qsizetype size) if (points_into_range(s, d.data(), d.data() + d.size)) return insert(i, QStringView{QVarLengthArray(s, s + size)}); - if (Q_UNLIKELY(i > d.size)) - resize(i + size, QLatin1Char(' ')); - else - resize(d.size + size); + const auto oldSize = this->size(); + const auto newSize = qMax(i, oldSize) + size; + const bool shouldGrow = d->shouldGrowBeforeInsert(d.begin() + qMin(i, oldSize), size); + + auto flags = d->detachFlags() | Data::GrowsForward; + if (i <= newSize / 4) + flags |= Data::GrowsBackwards; + + // ### optimize me + if (d->needsDetach() || newSize > capacity() || shouldGrow) + reallocGrowData(newSize + 1, flags); - ::memmove(d.data() + i + size, d.data() + i, (d.size - i - size) * sizeof(QChar)); - memcpy(d.data() + i, s, size * sizeof(QChar)); + if (i > oldSize) // set spaces in the uninitialized gap + d->copyAppend(i - oldSize, u' '); + + d->insert(d.begin() + i, s, s + size); + d.data()[d.size] = '\0'; return *this; } @@ -2633,12 +2656,24 @@ QString& QString::insert(qsizetype i, QChar ch) i += d.size; if (i < 0) return *this; - if (Q_UNLIKELY(i > size())) - resize(i + 1, QLatin1Char(' ')); - else - resize(d.size + 1); - ::memmove(d.data() + i + 1, d.data() + i, (d.size - i - 1) * sizeof(QChar)); - d.data()[i] = ch.unicode(); + + const auto oldSize = size(); + const auto newSize = qMax(i, oldSize) + 1; + const bool shouldGrow = d->shouldGrowBeforeInsert(d.begin() + qMin(i, oldSize), 1); + + auto flags = d->detachFlags() | Data::GrowsForward; + if (i <= newSize / 4) + flags |= Data::GrowsBackwards; + + // ### optimize me + if (d->needsDetach() || newSize > capacity() || shouldGrow) + reallocGrowData(newSize + 1, flags); + + if (i > oldSize) // set spaces in the uninitialized gap + d->copyAppend(i - oldSize, u' '); + + d->insert(d.begin() + i, 1, ch.unicode()); + d.data()[d.size] = '\0'; return *this; } @@ -2666,10 +2701,11 @@ QString &QString::append(const QString &str) if (isNull()) { operator=(str); } else { - if (d->needsDetach() || size() + str.size() > capacity()) - reallocData(size_t(size() + str.size()) + 1u, true); - memcpy(d.data() + d.size, str.d.data(), str.d.size * sizeof(QChar)); - d.size += str.d.size; + const bool shouldGrow = d->shouldGrowBeforeInsert(d.end(), str.d.size); + if (d->needsDetach() || size() + str.size() > capacity() || shouldGrow) + reallocGrowData(uint(size() + str.size()) + 1u, + d->detachFlags() | Data::GrowsForward); + d->copyAppend(str.d.data(), str.d.data() + str.d.size); d.data()[d.size] = '\0'; } } @@ -2685,10 +2721,13 @@ QString &QString::append(const QString &str) QString &QString::append(const QChar *str, qsizetype len) { if (str && len > 0) { - if (d->needsDetach() || size() + len > capacity()) - reallocData(size_t(size() + len) + 1u, true); - memcpy(d.data() + d.size, str, len * sizeof(QChar)); - d.size += len; + const bool shouldGrow = d->shouldGrowBeforeInsert(d.end(), len); + if (d->needsDetach() || size() + len > capacity() || shouldGrow) + reallocGrowData(uint(size() + len) + 1u, d->detachFlags() | Data::GrowsForward); + static_assert(sizeof(QChar) == sizeof(char16_t), "Unexpected difference in sizes"); + // the following should be safe as QChar uses char16_t as underlying data + const char16_t *char16String = reinterpret_cast<const char16_t *>(str); + d->copyAppend(char16String, char16String + len); d.data()[d.size] = '\0'; } return *this; @@ -2704,12 +2743,18 @@ QString &QString::append(QLatin1String str) const char *s = str.latin1(); if (s) { qsizetype len = str.size(); - if (d->needsDetach() || size() + len > capacity()) - reallocData(size_t(size() + len) + 1u, true); - char16_t *i = d.data() + d.size; - qt_from_latin1(i, s, size_t(len)); - i[len] = '\0'; - d.size += len; + const bool shouldGrow = d->shouldGrowBeforeInsert(d.end(), len); + if (d->needsDetach() || size() + len > capacity() || shouldGrow) + reallocGrowData(size_t(size() + len) + 1u, d->detachFlags() | Data::GrowsForward); + + if (d.freeSpaceAtBegin() == 0) { // fast path + char16_t *i = d.data() + d.size; + qt_from_latin1(i, s, size_t(len)); + d.size += len; + } else { // slow path + d->copyAppend(s, s + len); + } + d.data()[d.size] = '\0'; } return *this; } @@ -2751,9 +2796,10 @@ QString &QString::append(QLatin1String str) */ QString &QString::append(QChar ch) { - if (d->needsDetach() || size() + 1 > capacity()) - reallocData(d.size + 2u, true); - d.data()[d.size++] = ch.unicode(); + const bool shouldGrow = d->shouldGrowBeforeInsert(d.end(), 1); + if (d->needsDetach() || size() + 1 > capacity() || shouldGrow) + reallocGrowData(d.size + 2u, d->detachFlags() | Data::GrowsForward); + d->copyAppend(1, ch.unicode()); d.data()[d.size] = '\0'; return *this; } @@ -3890,7 +3936,7 @@ QString &QString::replace(const QRegularExpression &re, const QString &after) if (!iterator.hasNext()) // no matches at all return *this; - reallocData(size_t(d.size) + 1u); + reallocData(size_t(d.size) + 1u, d->detachFlags()); qsizetype numCaptures = re.captureCount(); @@ -5966,7 +6012,7 @@ const ushort *QString::utf16() const { if (!d->isMutable()) { // ensure '\0'-termination for ::fromRawData strings - const_cast<QString*>(this)->reallocData(size_t(d.size) + 1u); + const_cast<QString*>(this)->reallocData(size_t(d.size) + 1u, d->detachFlags()); } return reinterpret_cast<const ushort *>(d.data()); } diff --git a/src/corelib/text/qstring.h b/src/corelib/text/qstring.h index 04a333aefa..7fd5f86e25 100644 --- a/src/corelib/text/qstring.h +++ b/src/corelib/text/qstring.h @@ -538,13 +538,7 @@ public: inline QString &prepend(QStringView v) { return prepend(v.data(), v.length()); } inline QString &prepend(QLatin1String s) { return insert(0, s); } - inline QString &operator+=(QChar c) { - if (d->needsDetach() || int(d.size + 1) > capacity()) - reallocData(uint(d.size) + 2u, true); - d->data()[d.size++] = c.unicode(); - d->data()[d.size] = '\0'; - return *this; - } + inline QString &operator+=(QChar c) { return append(c); } #if QT_STRINGVIEW_LEVEL < 2 inline QString &operator+=(const QString &s) { return append(s); } @@ -913,7 +907,8 @@ private: friend inline bool operator< (QChar, QLatin1String) noexcept; friend inline bool operator> (QChar, QLatin1String) noexcept; - void reallocData(size_t alloc, bool grow = false); + void reallocData(size_t alloc, Data::ArrayOptions options); + void reallocGrowData(size_t alloc, Data::ArrayOptions options); static int compare_helper(const QChar *data1, qsizetype length1, const QChar *data2, qsizetype length2, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; @@ -1031,7 +1026,7 @@ inline QChar *QString::data() inline const QChar *QString::constData() const { return data(); } inline void QString::detach() -{ if (d->needsDetach()) reallocData(d.size + 1u); } +{ if (d->needsDetach()) reallocData(d.size + 1u, d->detachFlags()); } inline bool QString::isDetached() const { return !d->isShared(); } inline void QString::clear() @@ -1105,7 +1100,7 @@ inline QString::~QString() {} inline void QString::reserve(qsizetype asize) { if (d->needsDetach() || asize >= capacity()) - reallocData(uint(qMax(asize, size())) + 1u); + reallocData(uint(qMax(asize, size())) + 1u, d->detachFlags()); // we're not shared anymore, for sure d->setFlag(Data::CapacityReserved); @@ -1116,7 +1111,7 @@ inline void QString::squeeze() if ((d->flags() & Data::CapacityReserved) == 0) return; if (d->needsDetach() || int(d.size) < capacity()) - reallocData(uint(d.size) + 1u); + reallocData(uint(d.size) + 1u, d->detachFlags()); // we're not shared anymore, for sure d->clearFlag(Data::CapacityReserved); diff --git a/tests/auto/corelib/text/qstring/tst_qstring.cpp b/tests/auto/corelib/text/qstring/tst_qstring.cpp index 172e8c41af..126bc08903 100644 --- a/tests/auto/corelib/text/qstring/tst_qstring.cpp +++ b/tests/auto/corelib/text/qstring/tst_qstring.cpp @@ -360,11 +360,14 @@ private slots: void replace_qchar_qstring(); void replace_uint_uint_data(); void replace_uint_uint(); + void replace_uint_uint_extra(); void replace_extra(); void replace_string_data(); void replace_string(); + void replace_string_extra(); void replace_regexp_data(); void replace_regexp(); + void replace_regexp_extra(); void remove_uint_uint_data(); void remove_uint_uint(); void remove_string_data(); @@ -2367,6 +2370,15 @@ void tst_QString::insert_special_cases() QCOMPARE(a.insert(3, QLatin1String(0)), montreal); QCOMPARE(a.insert(3, static_cast<const char *>(0)), montreal); QCOMPARE(a.insert(0, QLatin1String("a")), QLatin1String("aMontreal")); + + a = "Mont"; + QCOMPARE(a.insert(a.size(), QLatin1String("real")), montreal); + QCOMPARE(a.insert(a.size() + 1, QLatin1String("ABC")), QString("Montreal ABC")); + + a = "AEF"; + QCOMPARE(a.insert(1, QLatin1String("BCD")), QString("ABCDEF")); + QCOMPARE(a.insert(3, QLatin1String("-")), QString("ABC-DEF")); + QCOMPARE(a.insert(a.size() + 1, QLatin1String("XYZ")), QString("ABC-DEF XYZ")); } void tst_QString::append_data(bool emptyIsNoop) @@ -2417,6 +2429,14 @@ void tst_QString::append_special_cases() a.append(0, 1); // no-op QCOMPARE(a, QLatin1String("Hello, World!\nHello, World!")); } + + { + QString a; + a.insert(0, QChar(u'A')); + QVERIFY(a.capacity() >= 3); + a.append(QLatin1String("BC")); + QCOMPARE(a, QLatin1String("ABC")); + } } void tst_QString::append_bytearray_special_cases_data() @@ -2670,6 +2690,29 @@ void tst_QString::replace_uint_uint() } } +void tst_QString::replace_uint_uint_extra() +{ + { + QString s; + s.insert(0, QChar('A')); + + auto bigReplacement = QString("B").repeated(s.capacity() * 3); + + s.replace( 0, 1, bigReplacement ); + QCOMPARE( s, bigReplacement ); + } + + { + QString s; + s.insert(0, QLatin1String("BBB")); + + auto smallReplacement = QString("C"); + + s.replace( 0, 3, smallReplacement ); + QCOMPARE( s, smallReplacement ); + } +} + void tst_QString::replace_extra() { /* @@ -2775,6 +2818,29 @@ void tst_QString::replace_string() QTEST( s3, "result" ); } +void tst_QString::replace_string_extra() +{ + { + QString s; + s.insert(0, QChar('A')); + + auto bigReplacement = QString("B").repeated(s.capacity() * 3); + + s.replace( QString("A"), bigReplacement ); + QCOMPARE( s, bigReplacement ); + } + + { + QString s; + s.insert(0, QLatin1String("BBB")); + + auto smallReplacement = QString("C"); + + s.replace( QString("BBB"), smallReplacement ); + QCOMPARE( s, smallReplacement ); + } +} + void tst_QString::replace_regexp() { QFETCH( QString, string ); @@ -2789,6 +2855,35 @@ void tst_QString::replace_regexp() QTEST( s2, "result" ); } +void tst_QString::replace_regexp_extra() +{ + { + QString s; + s.insert(0, QChar('A')); + + auto bigReplacement = QString("B").repeated(s.capacity() * 3); + + QRegularExpression regularExpression(QString("A")); + QVERIFY(regularExpression.isValid()); + + s.replace( regularExpression, bigReplacement ); + QCOMPARE( s, bigReplacement ); + } + + { + QString s; + s.insert(0, QLatin1String("BBB")); + + auto smallReplacement = QString("C"); + + QRegularExpression regularExpression(QString("BBB")); + QVERIFY(regularExpression.isValid()); + + s.replace( regularExpression, smallReplacement ); + QCOMPARE( s, smallReplacement ); + } +} + void tst_QString::remove_uint_uint() { QFETCH( QString, string ); @@ -2864,6 +2959,14 @@ void tst_QString::remove_extra() "The lazy dog jumps over the quick brown fox."; s.remove(s); } + + { + QString s = "BCDEFGHJK"; + QString s1 = s; + s1.insert(0, u'A'); // detaches + s1.remove(0, 1); + QCOMPARE(s1, s); + } } void tst_QString::toNum() |