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<int>, just store those numbers in the class itself if
possible. Think of this as a "Small String Optimization" for
QVersionNumber.

QVector<int> 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 <marc.mutz@kdab.com>

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<int> QVersionNumber::segments() const
 {
+    if (m_segments.isUsingPointer())
+        return *m_segments.pointer_segments;
+
     QVector<int> result;
     result.resize(segmentCount());
     for (int i = 0; i < segmentCount(); ++i)
@@ -205,10 +208,14 @@ QVector<int> QVersionNumber::segments() const
  */
 QVersionNumber QVersionNumber::normalized() const
 {
-    QVector<int> 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<int>;
+    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<int>;
+    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<int> *pointer_segments;
+        };
+
+        // set the InlineSegmentMarker and set length to zero
+        SegmentStorage() Q_DECL_NOTHROW : dummy(1) {}
+
+        SegmentStorage(const QVector<int> &seg)
+        {
+            if (dataFitsInline(seg.begin(), seg.size()))
+                setInlineData(seg.begin(), seg.size());
+            else
+                pointer_segments = new QVector<int>(seg);
+        }
+
+        SegmentStorage(const SegmentStorage &other)
+        {
+            if (other.isUsingPointer())
+                pointer_segments = new QVector<int>(*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<int>(*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<int> &&seg)
+        {
+            if (dataFitsInline(seg.begin(), seg.size()))
+                setInlineData(seg.begin(), seg.size());
+            else
+                pointer_segments = new QVector<int>(std::move(seg));
+        }
+#endif
+#ifdef Q_COMPILER_INITIALIZER_LISTS
+        SegmentStorage(std::initializer_list<int> args)
+        {
+            if (dataFitsInline(args.begin(), int(args.size()))) {
+                setInlineData(args.begin(), int(args.size()));
+            } else {
+                pointer_segments = new QVector<int>(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<int> &seg) Q_DECL_NOTHROW
+    inline explicit QVersionNumber(const QVector<int> &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<int> &&seg) Q_DECL_NOTHROW
-        : m_segments(qMove(seg))
+    explicit QVersionNumber(QVector<int> &&seg)
+        : m_segments(std::move(seg))
     {}
 #endif
+
 #ifdef Q_COMPILER_INITIALIZER_LISTS
     inline QVersionNumber(std::initializer_list<int> 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<int> m_segments;
 };
 
 Q_DECLARE_TYPEINFO(QVersionNumber, Q_MOVABLE_TYPE);