From 2d981e7e9fc2d55b1615332db7571786438158f6 Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Mon, 22 Sep 2014 15:18:38 -0700 Subject: Refactor QVersionNumber so it stores values in-class The common case of QVersionNumber is that there are few segments and each segment is a small integers. So instead of allocating a QVector, just store those numbers in the class itself if possible. Think of this as a "Small String Optimization" for QVersionNumber. QVector costs 16 + 4*N bytes, plus malloc overhead. After this change, QVersionNumber(5,4,0) will have an overhead of zero. The memory layout is explained in the header. I've coded it so big endian also works, but I have not tested it at all. Aside from the special functions for QVersionNumber and operator>>, all the rest of the algorithm could have been left unchanged. I only updated segments(), normalized(), compare(), commonPrefix() and fromString() to take advantage of the smaller implementation in a more efficient way. Note: QVersionNumber's constructors often leave half of the object or more uninitialized. That's not a problem. Change-Id: I4a2a0ce09fce2580f02d678e2f80b1dba74bac9d Reviewed-by: Marc Mutz --- src/corelib/tools/qversionnumber.cpp | 59 ++++++++++--- src/corelib/tools/qversionnumber.h | 167 ++++++++++++++++++++++++++++++++--- 2 files changed, 205 insertions(+), 21 deletions(-) diff --git a/src/corelib/tools/qversionnumber.cpp b/src/corelib/tools/qversionnumber.cpp index 4bc94c25be..4197fc47b1 100644 --- a/src/corelib/tools/qversionnumber.cpp +++ b/src/corelib/tools/qversionnumber.cpp @@ -169,6 +169,9 @@ QT_BEGIN_NAMESPACE */ QVector QVersionNumber::segments() const { + if (m_segments.isUsingPointer()) + return *m_segments.pointer_segments; + QVector result; result.resize(segmentCount()); for (int i = 0; i < segmentCount(); ++i) @@ -205,10 +208,14 @@ QVector QVersionNumber::segments() const */ QVersionNumber QVersionNumber::normalized() const { - QVector segs = m_segments; - while (segs.size() && segs.last() == 0) - segs.pop_back(); - return QVersionNumber(qMove(segs)); + int i; + for (i = m_segments.size(); i; --i) + if (m_segments.at(i - 1) != 0) + break; + + QVersionNumber result(*this); + result.m_segments.resize(i); + return result; } /*! @@ -247,10 +254,23 @@ bool QVersionNumber::isPrefixOf(const QVersionNumber &other) const Q_DECL_NOTHRO */ int QVersionNumber::compare(const QVersionNumber &v1, const QVersionNumber &v2) Q_DECL_NOTHROW { - int commonlen = qMin(v1.segmentCount(), v2.segmentCount()); - for (int i = 0; i < commonlen; ++i) { - if (v1.segmentAt(i) != v2.segmentAt(i)) - return v1.segmentAt(i) - v2.segmentAt(i); + int commonlen; + + if (Q_LIKELY(!v1.m_segments.isUsingPointer() && !v2.m_segments.isUsingPointer())) { + // we can't use memcmp because it interprets the data as unsigned bytes + const qint8 *ptr1 = v1.m_segments.inline_segments + InlineSegmentStartIdx; + const qint8 *ptr2 = v2.m_segments.inline_segments + InlineSegmentStartIdx; + commonlen = qMin(v1.m_segments.size(), + v2.m_segments.size()); + for (int i = 0; i < commonlen; ++i) + if (int x = ptr1[i] - ptr2[i]) + return x; + } else { + commonlen = qMin(v1.segmentCount(), v2.segmentCount()); + for (int i = 0; i < commonlen; ++i) { + if (v1.segmentAt(i) != v2.segmentAt(i)) + return v1.segmentAt(i) - v2.segmentAt(i); + } } // ran out of segments in v1 and/or v2 and need to check the first trailing @@ -294,8 +314,10 @@ QVersionNumber QVersionNumber::commonPrefix(const QVersionNumber &v1, if (i == 0) return QVersionNumber(); - // will use a vector - return QVersionNumber(v1.m_segments.mid(0, i)); + // try to use the one with inline segments, if there's one + QVersionNumber result(!v1.m_segments.isUsingPointer() ? v1 : v2); + result.m_segments.resize(i); + return result; } /*! @@ -419,6 +441,19 @@ QVersionNumber QVersionNumber::fromString(const QString &string, int *suffixInde return QVersionNumber(qMove(seg)); } +void QVersionNumber::SegmentStorage::setVector(int len, int maj, int min, int mic) +{ + pointer_segments = new QVector; + pointer_segments->resize(len); + pointer_segments->data()[0] = maj; + if (len > 1) { + pointer_segments->data()[1] = min; + if (len > 2) { + pointer_segments->data()[2] = mic; + } + } +} + #ifndef QT_NO_DATASTREAM /*! \fn QDataStream& operator<<(QDataStream &out, @@ -445,7 +480,9 @@ QDataStream& operator<<(QDataStream &out, const QVersionNumber &version) */ QDataStream& operator>>(QDataStream &in, QVersionNumber &version) { - in >> version.m_segments; + if (!version.m_segments.isUsingPointer()) + version.m_segments.pointer_segments = new QVector; + in >> *version.m_segments.pointer_segments; return in; } #endif diff --git a/src/corelib/tools/qversionnumber.h b/src/corelib/tools/qversionnumber.h index 050e685f03..0ea73cc842 100644 --- a/src/corelib/tools/qversionnumber.h +++ b/src/corelib/tools/qversionnumber.h @@ -53,20 +53,169 @@ Q_CORE_EXPORT QDataStream& operator>>(QDataStream &in, QVersionNumber &version); class QVersionNumber { + /* + * QVersionNumber stores small values inline, without memory allocation. + * We do that by setting the LSB in the pointer that would otherwise hold + * the longer form of the segments. + * The constants below help us deal with the permutations for 32- and 64-bit, + * little- and big-endian architectures. + */ + enum { + // in little-endian, inline_segments[0] is shared with the pointer's LSB, while + // in big-endian, it's inline_segments[7] + InlineSegmentMarker = Q_BYTE_ORDER == Q_LITTLE_ENDIAN ? 0 : sizeof(void*) - 1, + InlineSegmentStartIdx = !InlineSegmentMarker, // 0 for BE, 1 for LE + InlineSegmentCount = sizeof(void*) - 1 + }; + Q_STATIC_ASSERT(InlineSegmentCount >= 3); // at least major, minor, micro + + struct SegmentStorage { + // Note: we alias the use of dummy and inline_segments in the use of the + // union below. This is undefined behavior in C++98, but most compilers implement + // the C++11 behavior. The one known exception is older versions of Sun Studio. + union { + quintptr dummy; + qint8 inline_segments[sizeof(void*)]; + QVector *pointer_segments; + }; + + // set the InlineSegmentMarker and set length to zero + SegmentStorage() Q_DECL_NOTHROW : dummy(1) {} + + SegmentStorage(const QVector &seg) + { + if (dataFitsInline(seg.begin(), seg.size())) + setInlineData(seg.begin(), seg.size()); + else + pointer_segments = new QVector(seg); + } + + SegmentStorage(const SegmentStorage &other) + { + if (other.isUsingPointer()) + pointer_segments = new QVector(*other.pointer_segments); + else + dummy = other.dummy; + } + + SegmentStorage &operator=(const SegmentStorage &other) + { + if (isUsingPointer() && other.isUsingPointer()) { + *pointer_segments = *other.pointer_segments; + } else if (other.isUsingPointer()) { + pointer_segments = new QVector(*other.pointer_segments); + } else { + if (isUsingPointer()) + delete pointer_segments; + dummy = other.dummy; + } + return *this; + } + +#ifdef Q_COMPILER_RVALUE_REFS + SegmentStorage(SegmentStorage &&other) Q_DECL_NOTHROW + : dummy(other.dummy) + { + other.dummy = 1; + } + + SegmentStorage &operator=(SegmentStorage &&other) Q_DECL_NOTHROW + { + qSwap(dummy, other.dummy); + return *this; + } + + explicit SegmentStorage(QVector &&seg) + { + if (dataFitsInline(seg.begin(), seg.size())) + setInlineData(seg.begin(), seg.size()); + else + pointer_segments = new QVector(std::move(seg)); + } +#endif +#ifdef Q_COMPILER_INITIALIZER_LISTS + SegmentStorage(std::initializer_list args) + { + if (dataFitsInline(args.begin(), int(args.size()))) { + setInlineData(args.begin(), int(args.size())); + } else { + pointer_segments = new QVector(args); + } + } +#endif + + ~SegmentStorage() { if (isUsingPointer()) delete pointer_segments; } + + bool isUsingPointer() const Q_DECL_NOTHROW + { return (inline_segments[InlineSegmentMarker] & 1) == 0; } + + int size() const Q_DECL_NOTHROW + { return isUsingPointer() ? pointer_segments->size() : (inline_segments[InlineSegmentMarker] >> 1); } + + void setInlineSize(int len) + { inline_segments[InlineSegmentMarker] = 1 + 2 * len; } + + void resize(int len) + { + if (isUsingPointer()) + pointer_segments->resize(len); + else + setInlineSize(len); + } + + int at(int index) const + { + return isUsingPointer() ? + pointer_segments->at(index) : + inline_segments[InlineSegmentStartIdx + index]; + } + + void setSegments(int len, int maj, int min = 0, int mic = 0) + { + if (maj == qint8(maj) && min == qint8(min) && mic == qint8(mic)) { + int data[] = { maj, min, mic }; + setInlineData(data, len); + } else { + setVector(len, maj, min, mic); + } + } + + private: + static bool dataFitsInline(const int *data, int len) + { + if (len > InlineSegmentCount) + return false; + for (int i = 0; i < len; ++i) + if (data[i] != qint8(data[i])) + return false; + return true; + } + void setInlineData(const int *data, int len) + { + setInlineSize(len); + for (int i = 0; i < len; ++i) + inline_segments[InlineSegmentStartIdx + i] = qint8(data[i]); + } + + Q_CORE_EXPORT void setVector(int len, int maj, int min, int mic); + } m_segments; + public: inline QVersionNumber() Q_DECL_NOTHROW : m_segments() {} - // compiler-generated copy/move ctor/assignment operators are ok - - inline explicit QVersionNumber(const QVector &seg) Q_DECL_NOTHROW + inline explicit QVersionNumber(const QVector &seg) : m_segments(seg) {} + + // compiler-generated copy/move ctor/assignment operators and the destructor are ok + #ifdef Q_COMPILER_RVALUE_REFS - inline explicit QVersionNumber(QVector &&seg) Q_DECL_NOTHROW - : m_segments(qMove(seg)) + explicit QVersionNumber(QVector &&seg) + : m_segments(std::move(seg)) {} #endif + #ifdef Q_COMPILER_INITIALIZER_LISTS inline QVersionNumber(std::initializer_list args) : m_segments(args) @@ -74,13 +223,13 @@ public: #endif inline explicit QVersionNumber(int maj) - { m_segments.reserve(1); m_segments << maj; } + { m_segments.setSegments(1, maj); } inline explicit QVersionNumber(int maj, int min) - { m_segments.reserve(2); m_segments << maj << min; } + { m_segments.setSegments(2, maj, min); } inline explicit QVersionNumber(int maj, int min, int mic) - { m_segments.reserve(3); m_segments << maj << min << mic; } + { m_segments.setSegments(3, maj, min, mic); } inline bool isNull() const Q_DECL_NOTHROW Q_REQUIRED_RESULT { return segmentCount() == 0; } @@ -121,8 +270,6 @@ private: friend Q_CORE_EXPORT QDataStream& operator>>(QDataStream &in, QVersionNumber &version); #endif friend Q_CORE_EXPORT uint qHash(const QVersionNumber &key, uint seed); - - QVector m_segments; }; Q_DECLARE_TYPEINFO(QVersionNumber, Q_MOVABLE_TYPE); -- cgit v1.2.3