From fd96115ae8501c2baf591b821bdf6f7d90b62f55 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Jo=C3=A3o=20Abecasis?= <joao.abecasis@nokia.com>
Date: Thu, 16 Feb 2012 23:53:58 +0100
Subject: QVector: always grow exponentially

For non-movable types (QTypeInfo<T>::isStatic), QVector would grow the
array linearly, and defer to qAllocMore otherwise. That property,
however, gives no indication as to how the vector will grow.

By forcing additional allocations for growing containers of such types,
this penalized exactly those objects which are more expensive to move.

We now let qAllocMore reign in growth decisions.

Change-Id: I843a89dcdc21d09868c6b62a846a7e1e4548e399
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Lars Knoll <lars.knoll@nokia.com>
---
 src/corelib/tools/qvector.cpp                       | 4 +---
 src/corelib/tools/qvector.h                         | 9 ++++-----
 tests/benchmarks/corelib/tools/qvector/qrawvector.h | 8 +++-----
 3 files changed, 8 insertions(+), 13 deletions(-)

diff --git a/src/corelib/tools/qvector.cpp b/src/corelib/tools/qvector.cpp
index 0a15c2208c..254dd34771 100644
--- a/src/corelib/tools/qvector.cpp
+++ b/src/corelib/tools/qvector.cpp
@@ -76,10 +76,8 @@ void QVectorData::free(QVectorData *x, int alignment)
         ::free(x);
 }
 
-int QVectorData::grow(int sizeofTypedData, int size, int sizeofT, bool excessive)
+int QVectorData::grow(int sizeofTypedData, int size, int sizeofT)
 {
-    if (excessive)
-        return size + size / 2;
     return qAllocMore(size * sizeofT, sizeofTypedData - sizeofT) / sizeofT;
 }
 
diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h
index 6357c24621..4f9e1839ec 100644
--- a/src/corelib/tools/qvector.h
+++ b/src/corelib/tools/qvector.h
@@ -80,7 +80,7 @@ struct Q_CORE_EXPORT QVectorData
     static QVectorData *allocate(int size, int alignment);
     static QVectorData *reallocate(QVectorData *old, int newsize, int oldsize, int alignment);
     static void free(QVectorData *data, int alignment);
-    static int grow(int sizeofTypedData, int size, int sizeofT, bool excessive);
+    static int grow(int sizeofTypedData, int size, int sizeofT);
 };
 
 template <typename T>
@@ -355,7 +355,7 @@ void QVector<T>::reserve(int asize)
 template <typename T>
 void QVector<T>::resize(int asize)
 { realloc(asize, (asize > d->alloc || (!d->capacity && asize < d->size && asize < (d->alloc >> 1))) ?
-          QVectorData::grow(sizeOfTypedData(), asize, sizeof(T), QTypeInfo<T>::isStatic)
+          QVectorData::grow(sizeOfTypedData(), asize, sizeof(T))
           : d->alloc); }
 template <typename T>
 inline void QVector<T>::clear()
@@ -582,7 +582,7 @@ void QVector<T>::append(const T &t)
     if (!isDetached() || d->size + 1 > d->alloc) {
         const T copy(t);
         realloc(d->size, (d->size + 1 > d->alloc) ?
-                    QVectorData::grow(sizeOfTypedData(), d->size + 1, sizeof(T), QTypeInfo<T>::isStatic)
+                    QVectorData::grow(sizeOfTypedData(), d->size + 1, sizeof(T))
                     : d->alloc);
         if (QTypeInfo<T>::isComplex)
             new (p->array + d->size) T(copy);
@@ -604,8 +604,7 @@ typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, c
     if (n != 0) {
         const T copy(t);
         if (!isDetached() || d->size + n > d->alloc)
-            realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + n, sizeof(T),
-                                               QTypeInfo<T>::isStatic));
+            realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + n, sizeof(T)));
         if (QTypeInfo<T>::isStatic) {
             T *b = p->array + d->size;
             T *i = p->array + d->size + n;
diff --git a/tests/benchmarks/corelib/tools/qvector/qrawvector.h b/tests/benchmarks/corelib/tools/qvector/qrawvector.h
index 159dfbf8dc..4a4f03ee1b 100644
--- a/tests/benchmarks/corelib/tools/qvector/qrawvector.h
+++ b/tests/benchmarks/corelib/tools/qvector/qrawvector.h
@@ -308,7 +308,7 @@ void QRawVector<T>::reserve(int asize)
 template <typename T>
 void QRawVector<T>::resize(int asize)
 { realloc(asize, (asize > m_alloc || (asize < m_size && asize < (m_alloc >> 1)))
-    ? QVectorData::grow(sizeOfTypedData(), asize, sizeof(T), QTypeInfo<T>::isStatic)
+    ? QVectorData::grow(sizeOfTypedData(), asize, sizeof(T))
     : m_alloc, false); }
 template <typename T>
 inline void QRawVector<T>::clear()
@@ -510,8 +510,7 @@ void QRawVector<T>::append(const T &t)
 {
     if (m_size + 1 > m_alloc) {
         const T copy(t);
-        realloc(m_size, QVectorData::grow(sizeOfTypedData(), m_size + 1, sizeof(T),
-                                           QTypeInfo<T>::isStatic), false);
+        realloc(m_size, QVectorData::grow(sizeOfTypedData(), m_size + 1, sizeof(T)), false);
         if (QTypeInfo<T>::isComplex)
             new (m_begin + m_size) T(copy);
         else
@@ -532,8 +531,7 @@ typename QRawVector<T>::iterator QRawVector<T>::insert(iterator before, size_typ
     if (n != 0) {
         const T copy(t);
         if (m_size + n > m_alloc)
-            realloc(m_size, QVectorData::grow(sizeOfTypedData(), m_size + n, sizeof(T),
-                                               QTypeInfo<T>::isStatic), false);
+            realloc(m_size, QVectorData::grow(sizeOfTypedData(), m_size + n, sizeof(T)), false);
         if (QTypeInfo<T>::isStatic) {
             T *b = m_begin + m_size;
             T *i = m_begin + m_size + n;
-- 
cgit v1.2.3