[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