QStringBuilder: fix quadratic behavior in op+=

QByteArray and QString honor a reserve(n) faithfully, meaning that if
n > capacity(), then capacity() == n after the reserve() call.

This is expected behavior, and also what libstdc++'s std::vector does.

The problem is QStringBuilder's op+=, which calls reserve()
unconditionally to ensure capacity for its resize-after-append
magic. If a user builds up a string by repeatedly appending
string-builder expressions, these repeated minimal-progress reserve
calls destroy the string's natural geometric capacity growth, turning
it linear instead, and hence the whole construction becomes quadratic.

Fix by calling reserve() only when necessary, and for a maximum of
O(logN) times, N being the separate calls to QStringBuilder's op+=.

This guarantees amortized-linear runtime of string building again.

Need to insert an explicit detach() call in reserve()'s stead, lest a
detach() in the following data() would reset capacity() to size().

Copied a useful comment from the QByteArray case to the QString case.

[ChangeLog][QtCore][QStringBuilder] Fixed quadratic behavior when
repeatedly appending string-builder expressions (using operator+=) to
QString/QByteArray objects.

Pick-to: 6.3 6.2
Change-Id: I1c210a8d0026c227e55e5e30a46fb747660bb66e
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Anton Kudryavtsev <antkudr@mail.ru>

1 files changed, 7 insertions, 2 deletions

diff --git a/src/corelib/text/qstringbuilder.h b/src/corelib/text/qstringbuilder.h
index f3cbba26dd..2fbbb43b32 100644
--- a/src/corelib/text/qstringbuilder.h
+++ b/src/corelib/text/qstringbuilder.h
@@ -449,7 +449,9 @@ QByteArray &appendToByteArray(QByteArray &a, const QStringBuilder<A, B> &b, char
 {
     // append 8-bit data to a byte array
     qsizetype len = a.size() + QConcatenable< QStringBuilder<A, B> >::size(b);
-    a.reserve(len);
+    a.detach(); // a detach() in a.data() could reset a.capacity() to a.size()
+    if (len > a.capacity())
+        a.reserve(qMax(len, 2 * a.capacity()));
     char *it = a.data() + a.size();
     QConcatenable< QStringBuilder<A, B> >::appendTo(b, it);
     a.resize(len); //we need to resize after the appendTo for the case str+=foo+str
@@ -476,9 +478,12 @@ template <typename A, typename B>
 QString &operator+=(QString &a, const QStringBuilder<A, B> &b)
 {
     qsizetype len = a.size() + QConcatenable< QStringBuilder<A, B> >::size(b);
-    a.reserve(len);
+    a.detach(); // a detach() in a.data() could reset a.capacity() to a.size()
+    if (len > a.capacity())
+        a.reserve(qMax(len, 2 * a.capacity()));
     QChar *it = a.data() + a.size();
     QConcatenable< QStringBuilder<A, B> >::appendTo(b, it);
+    // we need to resize after the appendTo for the case str+=foo+str
     a.resize(it - a.constData()); //may be smaller than len if there was conversion from utf8
     return a;
 }