From 100ea081145be48f7a091be5dee339255154b078 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B8rn=20Erik=20Nilsen?= Date: Wed, 17 Feb 2010 13:07:32 +0100 Subject: Move benchmarks/qvector to benchmarks/corelib/tools/qvector Left-over after: 020830966e08239854ac207ec28663a80c6e0647. This change was done in the 4.6 branch, however the qvector bench didn't exists in the 4.6 branch. --- tests/benchmarks/corelib/tools/qvector/main.cpp | 426 ++++++++++++ .../benchmarks/corelib/tools/qvector/outofline.cpp | 81 +++ .../benchmarks/corelib/tools/qvector/qrawvector.h | 742 +++++++++++++++++++++ tests/benchmarks/corelib/tools/qvector/qvector.pro | 6 + tests/benchmarks/corelib/tools/tools.pro | 3 +- tests/benchmarks/qvector/main.cpp | 426 ------------ tests/benchmarks/qvector/outofline.cpp | 81 --- tests/benchmarks/qvector/qrawvector.h | 742 --------------------- tests/benchmarks/qvector/qvector.pro | 6 - 9 files changed, 1257 insertions(+), 1256 deletions(-) create mode 100644 tests/benchmarks/corelib/tools/qvector/main.cpp create mode 100644 tests/benchmarks/corelib/tools/qvector/outofline.cpp create mode 100644 tests/benchmarks/corelib/tools/qvector/qrawvector.h create mode 100644 tests/benchmarks/corelib/tools/qvector/qvector.pro delete mode 100644 tests/benchmarks/qvector/main.cpp delete mode 100644 tests/benchmarks/qvector/outofline.cpp delete mode 100644 tests/benchmarks/qvector/qrawvector.h delete mode 100644 tests/benchmarks/qvector/qvector.pro diff --git a/tests/benchmarks/corelib/tools/qvector/main.cpp b/tests/benchmarks/corelib/tools/qvector/main.cpp new file mode 100644 index 0000000..65e7609 --- /dev/null +++ b/tests/benchmarks/corelib/tools/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/corelib/tools/qvector/outofline.cpp b/tests/benchmarks/corelib/tools/qvector/outofline.cpp new file mode 100644 index 0000000..e8d036e --- /dev/null +++ b/tests/benchmarks/corelib/tools/qvector/outofline.cpp @@ -0,0 +1,81 @@ +/**************************************************************************** +** +** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtTest 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$ +** +****************************************************************************/ + +#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/corelib/tools/qvector/qrawvector.h b/tests/benchmarks/corelib/tools/qvector/qrawvector.h new file mode 100644 index 0000000..15421eb --- /dev/null +++ b/tests/benchmarks/corelib/tools/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/corelib/tools/qvector/qvector.pro b/tests/benchmarks/corelib/tools/qvector/qvector.pro new file mode 100644 index 0000000..adb30c9 --- /dev/null +++ b/tests/benchmarks/corelib/tools/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 diff --git a/tests/benchmarks/corelib/tools/tools.pro b/tests/benchmarks/corelib/tools/tools.pro index 12c23fc..681a6c6 100644 --- a/tests/benchmarks/corelib/tools/tools.pro +++ b/tests/benchmarks/corelib/tools/tools.pro @@ -7,4 +7,5 @@ SUBDIRS = \ qregexp \ qstring \ qstringbuilder \ - qstringlist + qstringlist \ + qvector diff --git a/tests/benchmarks/qvector/main.cpp b/tests/benchmarks/qvector/main.cpp deleted file mode 100644 index 65e7609..0000000 --- a/tests/benchmarks/qvector/main.cpp +++ /dev/null @@ -1,426 +0,0 @@ -/**************************************************************************** -** -** 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 deleted file mode 100644 index e8d036e..0000000 --- a/tests/benchmarks/qvector/outofline.cpp +++ /dev/null @@ -1,81 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). -** All rights reserved. -** Contact: Nokia Corporation (qt-info@nokia.com) -** -** This file is part of the QtTest 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$ -** -****************************************************************************/ - -#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 deleted file mode 100644 index 15421eb..0000000 --- a/tests/benchmarks/qvector/qrawvector.h +++ /dev/null @@ -1,742 +0,0 @@ -/**************************************************************************** -** -** 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 deleted file mode 100644 index adb30c9..0000000 --- a/tests/benchmarks/qvector/qvector.pro +++ /dev/null @@ -1,6 +0,0 @@ -load(qttest_p4) -TARGET = tst_vector -QT = core -INCLUDEPATH += . -SOURCES += main.cpp outofline.cpp outofline2.cpp -CONFIG += release -- cgit v0.12