[Development] Container refactor update
Peter Kümmel
syntheticpp at gmx.net
Tue Jun 19 00:32:37 CEST 2012
On 18.06.2012 23:58, Thiago Macieira wrote:
> Here's the current status of my endeavour:
>
> Internals:
> * the alloc member is moved to QArrayAllocatedData
> * the refcount is moved to all subclasses of QArrayData (QArrayRawData,
> QArrayAllocatedData and QArrayForeignData)
> * the base class QArrayData has exactly one 4-byte member: flags
> * that means statics (like QStringLiteral) in my current design will have 4
> bytes of overhead
> * the overhead of an allocation is 12 bytes, and we can easily pad to 16 to
> gain the advantage of aligned operations
> * since statics no longer have a refcount, QArrayData no longer uses
> QRefCount. The indication of immutable header and data are in the flags
> instead
> * The begin pointer and the size are moved out of the d pointer and into the
> main body of the container class
> * I've currently ported SimpleVector and QVector to it
> In fact, I've rewritten QVector entirely, reusing parts of SimpleVector.
> It's now using QArrayDataPointer and QArrayDataOps
> The design is entirely exception-safe.
> The QVector test passes completely, except for one test that hardcoded old
> behaviour.
>
> Performance considerations:
> * ref() does two 1-bit tests before the atomic increment
> * deref() does one 1-bit test before the atomic decrement
> * needsDetach() does one 2-bit test and a check for the refcount's value
> * begin(), data(), size() are a simple return, with no extra dereferencing
> (not counting the detach)
> * end() is simply begin() + size()
> * since the data pointer and size are out of QArrayData, we don't need a
> static struct for the data. QStringLiteral becomes the equivalent of:
> []() {
> static const QArrayData d = { QArrayData::StaticDataFlags };
> return QString(d, u"" STR, sizeof(u"" STR) / 2 - 2);
> }()
> * you may notice that the string itself is just a regular literal. As a
> consequence, this means QStringLiteral("foo") and QStringLiteral("foo")
> actually do share the string (but not the d pointer)
> * unfortunately, sizeof(QVector) == sizeof(QString) == 3 * sizeof(void*)
> - this means porting QList is a must, otherwise QStringList will be
> horrible
>
> Future considerations:
> * the d pointer for statics is always the same value, so it makes sense to
> share it.
> * another possibility is to say that d == 0 means static data. That would
> reduce the overhead of QStringLiteral to ZERO. We can also get rid of the
> lambda:
> #define QStringLiteral(STR) QString(Qt::StaticData, u"" STR)
> - if we do that, ref() will do one null-pointer check, one 1-bit test
> before the increment
> - deref() will do just the null pointer check before the decrement
> - needsDetach() will suffer more: it will do the null-pointer check, one 1-
> bit test and the refcount check
> - if we do this, then we can't do some other crazy static data, like static
> unsharable, static with a notify function, etc.
> * port QString, QByteArray and moc
> - the meta object will no longer need to keep 24 bytes per string
> * port QList
>
Do you know "folly"
https://github.com/facebook/folly
and had a look at folly's code?
https://github.com/facebook/folly/blob/master/folly/FBVector.h
Performance wise it could be interesting, because at some places
it uses lock-free code.
Peter
More information about the Development
mailing list