From 5daca044cf8d185d9a09b2ec87cba10244e425e4 Mon Sep 17 00:00:00 2001 From: hjk Date: Mon, 16 Nov 2009 08:54:12 +0100 Subject: add a benchmark comparing QVector and std::vector performance This also includes a QRawVector class template mimicing a QVector without reference counting. --- tests/benchmarks/qvector/main.cpp | 426 +++++++++++++++++++ tests/benchmarks/qvector/outofline.cpp | 41 ++ tests/benchmarks/qvector/qrawvector.h | 742 +++++++++++++++++++++++++++++++++ tests/benchmarks/qvector/qvector.pro | 6 + 4 files changed, 1215 insertions(+) create mode 100644 tests/benchmarks/qvector/main.cpp create mode 100644 tests/benchmarks/qvector/outofline.cpp create mode 100644 tests/benchmarks/qvector/qrawvector.h create mode 100644 tests/benchmarks/qvector/qvector.pro diff --git a/tests/benchmarks/qvector/main.cpp b/tests/benchmarks/qvector/main.cpp new file mode 100644 index 0000000..65e7609 --- /dev/null +++ b/tests/benchmarks/qvector/main.cpp @@ -0,0 +1,426 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the test suite of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the Technology Preview License Agreement accompanying +** this package. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** If you have questions regarding the use of this file, please contact +** Nokia at qt-info@nokia.com. +** +** +** +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include +#include +#include + +#include "qrawvector.h" + +#include + +/* + +Code generated by g++ 4.3.3. The lines marked with '!' are the ones that get +executed inside the loop. Using the external 's' causes some load making the +loop resembling a 'simple inner loop' in 'real' applications. + + +qvector_mutable_read_access: + +.L166: +! movl -16(%ebp), %edx +! movl (%edx), %eax +! subl $1, %eax +! je .L165 + movl 4(%edx), %eax + movl %eax, 8(%esp) + movl 8(%edx), %eax + movl %esi, (%esp) + movl %eax, 4(%esp) + call _ZN4myns7QVectorIdE7reallocEii +.L165: +! movl -16(%ebp), %eax +! fldl s +! faddl 16(%eax,%ebx,8) +! addl $1, %ebx +! cmpl $10000, %ebx +! fstpl s +! jne .L166 + + +qvector_const_read_access: + + movl -16(%ebp), %edx + xorl %eax, %eax +.L183: +! fldl s +! faddl 16(%edx,%eax,8) +! addl $1, %eax +! cmpl $10000, %eax +! fstpl s +! jne .L183 + + +stdvector_const_read_access and stdvector_mutable_read_access and +qrawvector_const_read_access and qrawvector_mutable_read_access: + + xorl %eax, %eax +.L64: +! fldl s +! faddl (%ebx,%eax,8) +! addl $1, %eax +! cmpl $10000, %eax +! fstpl s +! jne .L64 + + + +Behaviour varies with small modifications, but total is more or +less stable: + +qrawvector_mutable_read_access, using size() instead of N: + +.L145: +! faddl (%edx,%eax,8) +! addl $1, %eax +! cmpl %ecx, %eax +! fstl s +! jne .L145 +! fstp %st(0) + + +qrawvector_mutable_read_access, counting backward: + +.L145: +! faddl (%edx,%eax,8) +! subl $1, %eax +! cmpl $-1, %eax +! fstl s +! jne .L145 + + +qrawvector_mutable_read_access, counting backward, using size(): + +.L146: +! faddl (%edx) +! addl $1, %eax +! subl $8, %edx +! cmpl %ecx, %eax +! fstl s +! jne .L146 + + + +*/ + + +/* + +//////////////////////////////////////////////////////////////////// + +time ./tst_vector qvector_const_read_access +real 0m12.912s +user 0m12.401s +sys 0m0.016s + +time ./tst_vector qvector_mutable_read_access +real 0m38.566s +user 0m36.754s +sys 0m0.008s + + +time ./tst_vector stdvector_mutable_read_access +real 0m12.736s +user 0m12.665s +sys 0m0.004s + + +//////////////////////////////////////////////////////////////////// + +time ./tst_vector qvector_fill_and_return +real 0m28.778s +user 0m28.522s +sys 0m0.012s + +time ./tst_vector stdvector_fill_and_return +real 0m26.675s +user 0m26.558s +sys 0m0.012s + +time ./tst_vector qrawvector_fill_and_return +real 0m23.370s +user 0m23.269s +sys 0m0.008s + + + +*/ + + + +#define TEST_RETURN 1 + +// For some reason, both 'plain' and '-callgrind' create strange results +// (like varying instruction count for the same assembly code) +// So replace it by a plain loop and measure wall clock time. +//#undef QBENCHMARK +//#define QBENCHMARK for (int j = 0; j != 10000; ++j) + +class tst_QVector: public QObject +{ + Q_OBJECT + +private slots: + void calibration(); + + // Pure Qt solution + void qvector_separator() { qWarning() << "QVector results: "; } + void qvector_const_read_access(); + void qvector_mutable_read_access(); + #ifdef TEST_RETURN + void qvector_fill_and_return(); + void qvector_fill_and_return2(); + #endif + + // Purre Standard solution + void stdvector() { qWarning() << "std::vector results: "; } + void stdvector_const_read_access(); + void stdvector_mutable_read_access(); + #ifdef TEST_RETURN + void stdvector_fill_and_return(); + void stdvector_fill_and_return2(); + #endif + + // Build using std, pass as QVector + void mixedvector() { qWarning() << "mixed results: "; } + #ifdef TEST_RETURN + void mixedvector_fill_and_return(); + void mixedvector_fill_and_return2(); + #endif + + // Alternative implementation + void qrawvector_separator() { qWarning() << "QRawVector results: "; } + void qrawvector_const_read_access(); + void qrawvector_mutable_read_access(); + #ifdef TEST_RETURN + void qrawvector_fill_and_return(); + void qrawvector_fill_and_return2(); + #endif +}; + +const int N = 1000000; +extern double s; + +void tst_QVector::calibration() +{ + QVector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + QBENCHMARK { + for (int i = 0; i != N; ++i) + s += i; + } +} + +///////////////////// QVector ///////////////////// + +void tst_QVector::qvector_const_read_access() +{ + QVector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + + const QVector &vc = v; + QBENCHMARK { + for (int i = 0; i != N; ++i) + s += vc[i]; + } +} + +void tst_QVector::qvector_mutable_read_access() +{ + QVector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + + QBENCHMARK { + for (int i = 0; i != N; ++i) + s += v[i]; + } +} + +#ifdef TEST_RETURN +extern QVector qvector_fill_and_return_helper(); +extern QVector qvector_fill_and_return_helper2(); + +void tst_QVector::qvector_fill_and_return() +{ + QBENCHMARK { + QVector v = qvector_fill_and_return_helper(); + s += v[1]; + } +} + +void tst_QVector::qvector_fill_and_return2() +{ + QBENCHMARK { + QVector v = qvector_fill_and_return_helper2(); + s += v[1]; + } +} +#endif + + +///////////////////// QRawVector ///////////////////// + +void tst_QVector::qrawvector_const_read_access() +{ + QRawVector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + + const QRawVector &vc = v; + QBENCHMARK { + for (int i = vc.size(); --i >= 0;) + s += vc[i]; + } +} + +void tst_QVector::qrawvector_mutable_read_access() +{ + QRawVector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + + QBENCHMARK { + for (int i = 0; i != N; ++i) + s += v[i]; + } +} + +#ifdef TEST_RETURN +extern QVector qrawvector_fill_and_return_helper(); +extern QVector qrawvector_fill_and_return_helper2(); + +void tst_QVector::qrawvector_fill_and_return() +{ + QBENCHMARK { + QVector v = qrawvector_fill_and_return_helper(); + s += v[1]; + } +} + +void tst_QVector::qrawvector_fill_and_return2() +{ + QBENCHMARK { + QVector v = qrawvector_fill_and_return_helper(); + s += v[1]; + } +} +#endif + + +///////////////////// std::vector ///////////////////// + +void tst_QVector::stdvector_const_read_access() +{ + std::vector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + + const std::vector &vc = v; + QBENCHMARK { + for (int i = 0; i != N; ++i) + s += vc[i]; + } +} + +void tst_QVector::stdvector_mutable_read_access() +{ + std::vector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + + QBENCHMARK { + for (int i = 0; i != N; ++i) + s += v[i]; + } +} + +#ifdef TEST_RETURN +extern std::vector stdvector_fill_and_return_helper(); +extern std::vector stdvector_fill_and_return_helper2(); + +void tst_QVector::stdvector_fill_and_return() +{ + QBENCHMARK { + std::vector v = stdvector_fill_and_return_helper(); + s += v[1]; + } +} + +void tst_QVector::stdvector_fill_and_return2() +{ + QBENCHMARK { + std::vector v = stdvector_fill_and_return_helper2(); + s += v[1]; + } +} +#endif + +///////////////////// mixed vector ///////////////////// + + +#ifdef TEST_RETURN +extern QVector mixedvector_fill_and_return_helper(); +extern QVector mixedvector_fill_and_return_helper2(); + +void tst_QVector::mixedvector_fill_and_return() +{ + QBENCHMARK { + std::vector v = stdvector_fill_and_return_helper(); + s += v[1]; + } +} + +void tst_QVector::mixedvector_fill_and_return2() +{ + QBENCHMARK { + std::vector v = stdvector_fill_and_return_helper2(); + s += v[1]; + } +} +#endif + +QTEST_MAIN(tst_QVector) + +#include "main.moc" diff --git a/tests/benchmarks/qvector/outofline.cpp b/tests/benchmarks/qvector/outofline.cpp new file mode 100644 index 0000000..d1d72b0 --- /dev/null +++ b/tests/benchmarks/qvector/outofline.cpp @@ -0,0 +1,41 @@ + +#include +#include +#include "qrawvector.h" + +const int N = 1000000; +double s = 0; + +QVector qvector_fill_and_return_helper() +{ + QVector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + return v; +} + +QVector qrawvector_fill_and_return_helper() +{ + QRawVector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + return v.mutateToVector(); +} + +QVector mixedvector_fill_and_return_helper() +{ + std::vector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + return QVector::fromStdVector(v); +} + + +std::vector stdvector_fill_and_return_helper() +{ + std::vector v(N); + for (int i = 0; i != N; ++i) + v[i] = i; + return v; +} + diff --git a/tests/benchmarks/qvector/qrawvector.h b/tests/benchmarks/qvector/qrawvector.h new file mode 100644 index 0000000..15421eb --- /dev/null +++ b/tests/benchmarks/qvector/qrawvector.h @@ -0,0 +1,742 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the Technology Preview License Agreement accompanying +** this package. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** If you have questions regarding the use of this file, please contact +** Nokia at qt-info@nokia.com. +** +** +** +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QRAWVECTOR_H +#define QRAWVECTOR_H + +#include +#include +#include +#include +#include + +#ifndef QT_NO_STL +#include +#include +#endif +#include +#include +#include + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Core) + + + +template +class QRawVector +{ + struct Data : QVectorData { T array[1]; }; + + T *m_begin; + int m_size; + int m_alloc; + +public: + //static Data dummy; + //int headerOffset() { return (char*)&dummy.array - (char*)&dummy; } + inline int headerOffset() const { + // gcc complains about: return offsetof(Data, array); and also + // does not like '0' in the expression below. + return (char *)&(((Data *)(1))->array) - (char *)1; + } + inline Data *toBase(T *begin) const + { return (Data*)((char*)begin - headerOffset()); } + inline T *fromBase(void *d) const + { return (T*)((char*)d + headerOffset()); } + inline QRawVector() + { m_begin = fromBase(0); m_alloc = m_size = 0; realloc(m_size, m_alloc, true); } + explicit QRawVector(int size); + QRawVector(int size, const T &t); + inline QRawVector(const QRawVector &v) + { m_begin = v.m_begin; m_alloc = v.m_alloc; m_size = v.m_size; realloc(m_size, m_alloc, true); } + inline ~QRawVector() { free(m_begin, m_size); } + QRawVector &operator=(const QRawVector &v); + bool operator==(const QRawVector &v) const; + inline bool operator!=(const QRawVector &v) const { return !(*this == v); } + + inline int size() const { return m_size; } + + inline bool isEmpty() const { return m_size == 0; } + + void resize(int size); + + inline int capacity() const { return m_alloc; } + void reserve(int size); + inline void squeeze() { realloc(m_size, m_size, false); } + + inline T *data() { return m_begin; } + inline const T *data() const { return m_begin; } + inline const T *constData() const { return m_begin; } + void clear(); + + const T &at(int i) const; + T &operator[](int i); + const T &operator[](int i) const; + void append(const T &t); + void prepend(const T &t); + void insert(int i, const T &t); + void insert(int i, int n, const T &t); + void replace(int i, const T &t); + void remove(int i); + void remove(int i, int n); + + QRawVector &fill(const T &t, int size = -1); + + int indexOf(const T &t, int from = 0) const; + int lastIndexOf(const T &t, int from = -1) const; + bool contains(const T &t) const; + int count(const T &t) const; + +#ifdef QT_STRICT_ITERATORS + class iterator { + public: + T *i; + typedef std::random_access_iterator_tag iterator_category; + typedef ptrdiff_t difference_type; + typedef T value_type; + typedef T *pointer; + typedef T &reference; + + inline iterator() : i(0) {} + inline iterator(T *n) : i(n) {} + inline iterator(const iterator &o): i(o.i){} + inline T &operator*() const { return *i; } + inline T *operator->() const { return i; } + inline T &operator[](int j) const { return *(i + j); } + inline bool operator==(const iterator &o) const { return i == o.i; } + inline bool operator!=(const iterator &o) const { return i != o.i; } + inline bool operator<(const iterator& other) const { return i < other.i; } + inline bool operator<=(const iterator& other) const { return i <= other.i; } + inline bool operator>(const iterator& other) const { return i > other.i; } + inline bool operator>=(const iterator& other) const { return i >= other.i; } + inline iterator &operator++() { ++i; return *this; } + inline iterator operator++(int) { T *n = i; ++i; return n; } + inline iterator &operator--() { i--; return *this; } + inline iterator operator--(int) { T *n = i; i--; return n; } + inline iterator &operator+=(int j) { i+=j; return *this; } + inline iterator &operator-=(int j) { i-=j; return *this; } + inline iterator operator+(int j) const { return iterator(i+j); } + inline iterator operator-(int j) const { return iterator(i-j); } + inline int operator-(iterator j) const { return i - j.i; } + }; + friend class iterator; + + class const_iterator { + public: + T *i; + typedef std::random_access_iterator_tag iterator_category; + typedef ptrdiff_t difference_type; + typedef T value_type; + typedef const T *pointer; + typedef const T &reference; + + inline const_iterator() : i(0) {} + inline const_iterator(T *n) : i(n) {} + inline const_iterator(const const_iterator &o): i(o.i) {} + inline explicit const_iterator(const iterator &o): i(o.i) {} + inline const T &operator*() const { return *i; } + inline const T *operator->() const { return i; } + inline const T &operator[](int j) const { return *(i + j); } + inline bool operator==(const const_iterator &o) const { return i == o.i; } + inline bool operator!=(const const_iterator &o) const { return i != o.i; } + inline bool operator<(const const_iterator& other) const { return i < other.i; } + inline bool operator<=(const const_iterator& other) const { return i <= other.i; } + inline bool operator>(const const_iterator& other) const { return i > other.i; } + inline bool operator>=(const const_iterator& other) const { return i >= other.i; } + inline const_iterator &operator++() { ++i; return *this; } + inline const_iterator operator++(int) { T *n = i; ++i; return n; } + inline const_iterator &operator--() { i--; return *this; } + inline const_iterator operator--(int) { T *n = i; i--; return n; } + inline const_iterator &operator+=(int j) { i+=j; return *this; } + inline const_iterator &operator-=(int j) { i+=j; return *this; } + inline const_iterator operator+(int j) const { return const_iterator(i+j); } + inline const_iterator operator-(int j) const { return const_iterator(i-j); } + inline int operator-(const_iterator j) const { return i - j.i; } + }; + friend class const_iterator; +#else + // STL-style + typedef T *iterator; + typedef const T *const_iterator; +#endif + inline iterator begin() { return m_begin; } + inline const_iterator begin() const { return m_begin; } + inline const_iterator constBegin() const { return m_begin; } + inline iterator end() { return m_begin + m_size; } + inline const_iterator end() const { return m_begin + m_size; } + inline const_iterator constEnd() const { return m_begin + m_size; } + iterator insert(iterator before, int n, const T &x); + inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); } + iterator erase(iterator begin, iterator end); + inline iterator erase(iterator pos) { return erase(pos, pos+1); } + + // more Qt + inline int count() const { return m_size; } + inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } + inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); } + inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); } + inline const T &last() const { Q_ASSERT(!isEmpty()); return *(end()-1); } + inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; } + inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } + QRawVector mid(int pos, int length = -1) const; + + T value(int i) const; + T value(int i, const T &defaultValue) const; + + // STL compatibility + typedef T value_type; + typedef value_type *pointer; + typedef const value_type *const_pointer; + typedef value_type &reference; + typedef const value_type &const_reference; + typedef ptrdiff_t difference_type; + typedef iterator Iterator; + typedef const_iterator ConstIterator; + typedef int size_type; + inline void push_back(const T &t) { append(t); } + inline void push_front(const T &t) { prepend(t); } + void pop_back() { Q_ASSERT(!isEmpty()); erase(end()-1); } + void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); } + inline bool empty() const { return m_size == 0; } + inline T &front() { return first(); } + inline const_reference front() const { return first(); } + inline reference back() { return last(); } + inline const_reference back() const { return last(); } + + // comfort + QRawVector &operator+=(const QRawVector &l); + inline QRawVector operator+(const QRawVector &l) const + { QRawVector n = *this; n += l; return n; } + inline QRawVector &operator+=(const T &t) + { append(t); return *this; } + inline QRawVector &operator<< (const T &t) + { append(t); return *this; } + inline QRawVector &operator<<(const QRawVector &l) + { *this += l; return *this; } + + QList toList() const; + + //static QRawVector fromList(const QList &list); + +#ifndef QT_NO_STL + static inline QRawVector fromStdVector(const std::vector &vector) + { QRawVector tmp; qCopy(vector.begin(), vector.end(), std::back_inserter(tmp)); return tmp; } + inline std::vector toStdVector() const + { std::vector tmp; qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; } +#endif + +private: + T *allocate(int alloc); + void realloc(int size, int alloc, bool ref); + void free(T *begin, int size); + int sizeOfTypedData() { + // this is more or less the same as sizeof(Data), except that it doesn't + // count the padding at the end + return reinterpret_cast(&(reinterpret_cast(this))->array[1]) - reinterpret_cast(this); + } + static inline int alignOfTypedData() + { +#ifdef Q_ALIGNOF + return qMax(sizeof(void*), Q_ALIGNOF(Data)); +#else + return 0; +#endif + } + +public: + QVector mutateToVector() + { + Data *d = toBase(m_begin); + d->ref = 1; + d->alloc = m_alloc; + d->size = m_size; + d->sharable = 0; + d->capacity = 0; + + QVector v; + *reinterpret_cast(&v) = d; + m_begin = fromBase(0); + m_size = m_alloc = 0; + return v; + } +}; + + +template +void QRawVector::reserve(int asize) +{ if (asize > m_alloc) realloc(m_size, asize, false); } +template +void QRawVector::resize(int asize) +{ realloc(asize, (asize > m_alloc || (asize < m_size && asize < (m_alloc >> 1))) + ? QVectorData::grow(sizeOfTypedData(), asize, sizeof(T), QTypeInfo::isStatic) + : m_alloc, false); } +template +inline void QRawVector::clear() +{ *this = QRawVector(); } +template +inline const T &QRawVector::at(int i) const +{ Q_ASSERT_X(i >= 0 && i < m_size, "QRawVector::at", "index out of range"); + return m_begin[i]; } +template +inline const T &QRawVector::operator[](int i) const +{ Q_ASSERT_X(i >= 0 && i < m_size, "QRawVector::operator[]", "index out of range"); + return m_begin[i]; } +template +inline T &QRawVector::operator[](int i) +{ Q_ASSERT_X(i >= 0 && i < m_size, "QRawVector::operator[]", "index out of range"); + return data()[i]; } +template +inline void QRawVector::insert(int i, const T &t) +{ Q_ASSERT_X(i >= 0 && i <= m_size, "QRawVector::insert", "index out of range"); + insert(begin() + i, 1, t); } +template +inline void QRawVector::insert(int i, int n, const T &t) +{ Q_ASSERT_X(i >= 0 && i <= m_size, "QRawVector::insert", "index out of range"); + insert(begin() + i, n, t); } +template +inline void QRawVector::remove(int i, int n) +{ Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= m_size, "QRawVector::remove", "index out of range"); + erase(begin() + i, begin() + i + n); } +template +inline void QRawVector::remove(int i) +{ Q_ASSERT_X(i >= 0 && i < m_size, "QRawVector::remove", "index out of range"); + erase(begin() + i, begin() + i + 1); } +template +inline void QRawVector::prepend(const T &t) +{ insert(begin(), 1, t); } + +template +inline void QRawVector::replace(int i, const T &t) +{ + Q_ASSERT_X(i >= 0 && i < m_size, "QRawVector::replace", "index out of range"); + const T copy(t); + data()[i] = copy; +} + +template +QRawVector &QRawVector::operator=(const QRawVector &v) +{ + if (this != &v) { + free(m_begin, m_size); + m_alloc = v.m_alloc; + m_size = v.m_size; + m_begin = v.m_begin; + realloc(m_size, m_alloc, true); + } + return *this; +} + +template +inline T *QRawVector::allocate(int aalloc) +{ + QVectorData *d = QVectorData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); + Q_CHECK_PTR(d); + return fromBase(d); +} + +template +QRawVector::QRawVector(int asize) +{ + m_size = m_alloc = asize; + m_begin = allocate(asize); + if (QTypeInfo::isComplex) { + T *b = m_begin; + T *i = m_begin + m_size; + while (i != b) + new (--i) T; + } else { + qMemSet(m_begin, 0, asize * sizeof(T)); + } +} + +template +QRawVector::QRawVector(int asize, const T &t) +{ + m_size = m_alloc = asize; + m_begin = allocate(asize); + T *i = m_begin + m_size; + while (i != m_begin) + new (--i) T(t); +} + +template +void QRawVector::free(T *begin, int size) +{ + if (QTypeInfo::isComplex) { + T *i = begin + size; + while (i-- != begin) + i->~T(); + } + Data *x = toBase(begin); + x->free(x, alignOfTypedData()); +} + +template +void QRawVector::realloc(int asize, int aalloc, bool ref) +{ + if (QTypeInfo::isComplex && asize < m_size && !ref) { + // call the destructor on all objects that need to be + // destroyed when shrinking + T *pOld = m_begin + m_size; + while (asize < m_size) { + (--pOld)->~T(); + --m_size; + } + } + + int xalloc = m_alloc; + int xsize = m_size; + bool changed = false; + T *xbegin = m_begin; + if (aalloc != xalloc || ref) { + // (re)allocate memory + if (QTypeInfo::isStatic) { + xbegin = allocate(aalloc); + xsize = 0; + changed = true; + } else if (ref) { + xbegin = allocate(aalloc); + if (QTypeInfo::isComplex) { + xsize = 0; + } else { + ::memcpy(xbegin, m_begin, qMin(aalloc, xalloc) * sizeof(T)); + xsize = m_size; + } + changed = true; + } else { + QT_TRY { + QVectorData *mem = QVectorData::reallocate( + toBase(m_begin), sizeOfTypedData() + (aalloc - 1) * sizeof(T), + sizeOfTypedData() ++ (xalloc - 1) * sizeof(T), alignOfTypedData()); + Q_CHECK_PTR(mem); + xbegin = fromBase(mem); + xsize = m_size; + } QT_CATCH (const std::bad_alloc &) { + if (aalloc > xalloc) // ignore the error in case we are just shrinking. + QT_RETHROW; + } + } + xalloc = aalloc; + } + + if (QTypeInfo::isComplex) { + QT_TRY { + T *pOld = m_begin + xsize; + T *pNew = xbegin + xsize; + // copy objects from the old array into the new array + while (xsize < qMin(asize, m_size)) { + new (pNew++) T(*pOld++); + ++xsize; + } + // construct all new objects when growing + while (xsize < asize) { + new (pNew++) T; + ++xsize; + } + } QT_CATCH (...) { + free(xbegin, xsize); + QT_RETHROW; + } + + } else if (asize > xsize) { + // initialize newly allocated memory to 0 + qMemSet(xbegin + xsize, 0, (asize - xsize) * sizeof(T)); + } + xsize = asize; + + if (changed) { + if (!ref) + free(m_begin, m_size); + } + m_alloc = xalloc; + m_size = xsize; + m_begin = xbegin; +} + +template +Q_OUTOFLINE_TEMPLATE T QRawVector::value(int i) const +{ + return (i < 0 || i >= m_size) ? T() : m_begin[i]; +} +template +Q_OUTOFLINE_TEMPLATE T QRawVector::value(int i, const T &defaultValue) const +{ + return (i < 0 || i >= m_size) ? defaultValue : m_begin[i]; +} + +template +void QRawVector::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::isStatic), false); + if (QTypeInfo::isComplex) + new (m_begin + m_size) T(copy); + else + m_begin[m_size] = copy; + } else { + if (QTypeInfo::isComplex) + new (m_begin + m_size) T(t); + else + m_begin[m_size] = t; + } + ++m_size; +} + +template +Q_TYPENAME QRawVector::iterator QRawVector::insert(iterator before, size_type n, const T &t) +{ + int offset = int(before - m_begin); + 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::isStatic), false); + if (QTypeInfo::isStatic) { + T *b = m_begin + m_size; + T *i = m_begin + m_size + n; + while (i != b) + new (--i) T; + i = m_begin + m_size; + T *j = i + n; + b = m_begin + offset; + while (i != b) + *--j = *--i; + i = b+n; + while (i != b) + *--i = copy; + } else { + T *b = m_begin + offset; + T *i = b + n; + memmove(i, b, (m_size - offset) * sizeof(T)); + while (i != b) + new (--i) T(copy); + } + m_size += n; + } + return m_begin + offset; +} + +template +Q_TYPENAME QRawVector::iterator QRawVector::erase(iterator abegin, iterator aend) +{ + int f = int(abegin - m_begin); + int l = int(aend - m_begin); + int n = l - f; + if (QTypeInfo::isComplex) { + qCopy(m_begin + l, m_begin + m_size, m_begin + f); + T *i = m_begin + m_size; + T *b = m_begin + m_size - n; + while (i != b) { + --i; + i->~T(); + } + } else { + memmove(m_begin + f, m_begin + l, (m_size - l) * sizeof(T)); + } + m_size -= n; + return m_begin + f; +} + +template +bool QRawVector::operator==(const QRawVector &v) const +{ + if (m_size != v.m_size) + return false; + T* b = m_begin; + T* i = b + m_size; + T* j = v.m_begin + m_size; + while (i != b) + if (!(*--i == *--j)) + return false; + return true; +} + +template +QRawVector &QRawVector::fill(const T &from, int asize) +{ + const T copy(from); + resize(asize < 0 ? m_size : asize); + if (m_size) { + T *i = m_begin + m_size; + T *b = m_begin; + while (i != b) + *--i = copy; + } + return *this; +} + +template +QRawVector &QRawVector::operator+=(const QRawVector &l) +{ + int newSize = m_size + l.m_size; + realloc(m_size, newSize, false); + + T *w = m_begin + newSize; + T *i = l.m_begin + l.m_size; + T *b = l.m_begin; + while (i != b) { + if (QTypeInfo::isComplex) + new (--w) T(*--i); + else + *--w = *--i; + } + m_size = newSize; + return *this; +} + +template +int QRawVector::indexOf(const T &t, int from) const +{ + if (from < 0) + from = qMax(from + m_size, 0); + if (from < m_size) { + T* n = m_begin + from - 1; + T* e = m_begin + m_size; + while (++n != e) + if (*n == t) + return n - m_begin; + } + return -1; +} + +template +int QRawVector::lastIndexOf(const T &t, int from) const +{ + if (from < 0) + from += m_size; + else if (from >= m_size) + from = m_size-1; + if (from >= 0) { + T* b = m_begin; + T* n = m_begin + from + 1; + while (n != b) { + if (*--n == t) + return n - b; + } + } + return -1; +} + +template +bool QRawVector::contains(const T &t) const +{ + T* b = m_begin; + T* i = m_begin + m_size; + while (i != b) + if (*--i == t) + return true; + return false; +} + +template +int QRawVector::count(const T &t) const +{ + int c = 0; + T* b = m_begin; + T* i = m_begin + m_size; + while (i != b) + if (*--i == t) + ++c; + return c; +} + +template +Q_OUTOFLINE_TEMPLATE QRawVector QRawVector::mid(int pos, int length) const +{ + if (length < 0) + length = size() - pos; + if (pos == 0 && length == size()) + return *this; + QRawVector copy; + if (pos + length > size()) + length = size() - pos; + for (int i = pos; i < pos + length; ++i) + copy += at(i); + return copy; +} + +template +Q_OUTOFLINE_TEMPLATE QList QRawVector::toList() const +{ + QList result; + for (int i = 0; i < size(); ++i) + result.append(at(i)); + return result; +} + + +/*template +Q_OUTOFLINE_TEMPLATE QRawVector QList::toVector() const +{ + QRawVector result(size()); + for (int i = 0; i < size(); ++i) + result[i] = at(i); + return result; +} + +template +QRawVector QRawVector::fromList(const QList &list) +{ + return list.toVector(); +} + +template +QList QList::fromVector(const QRawVector &vector) +{ + return vector.toList(); +} +*/ + +Q_DECLARE_SEQUENTIAL_ITERATOR(RawVector) +Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(RawVector) + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QRAWVECTOR_H diff --git a/tests/benchmarks/qvector/qvector.pro b/tests/benchmarks/qvector/qvector.pro new file mode 100644 index 0000000..adb30c9 --- /dev/null +++ b/tests/benchmarks/qvector/qvector.pro @@ -0,0 +1,6 @@ +load(qttest_p4) +TARGET = tst_vector +QT = core +INCLUDEPATH += . +SOURCES += main.cpp outofline.cpp outofline2.cpp +CONFIG += release -- cgit v0.12