[Development] Notes from the Containers session from QtCS

[Thiago Macieira]

We discussed the containers, including performance issues and why the design 
was going to where it was going.

QList
~~~

Since QList is the most used container in Qt and by Qt users, it's probably 
being used in unexpected ways. We preferred not to break compatibility. QList 
will continue to have a hybrid behaviour.

But we decided to remove the size restriction. Any type that is explicitly 
marked movable will make QList<T> be actually a QVector<T>. Otherwise, it will 
use Qt 4 behaviour of a QVector<void *>.

André's 16-byte container proposal
~~~~~~~

André suggested a container main class as:
class QString
{
    ushort *data;
    int size;
    int d_offset;
};

so that d = reinterpret_cast<char *>(data) + d_offset.

That class has 16 bytes in size. However, it breaks for fromRawData, since the 
heap and mmap'ed areas might be more than 2^31 apart. In fact, on Linux 64-
bit, they'll be in the order of 2^46 apart.

Inlining of size and data pointer
~~~~

We discussed the benefits of having a body like:
class QString
{
    QArrayData *d;
    ushort *b;
    int size;
};

The most important benefits are:
 - accessing the data and the size (including isEmpty()) are by far the most 
   common operations -> that's what we should optimise for
 - the current implementation requires an extra load and an addition, which 
   introduces a data dependency -> the CPU stalls
 - having them inlined as above permit the cheap substrings solution
   (will not be in 5.0, but can be done in 5.1)
 - allows for the character literal (char for QByteArray or char16_t for 
   QString) to be a regular "here's some text" literal, which the compiler can 
   understand and merge identicals

We discussed whether 3x size of the QString, QVector, QList and QByteArray 
objects would be acceptable. The arguments for the change, besides the those 
above, were that the data was present anyway for any non-empty strings, so 
there's no actual growth, just moving it around.

It does impact in the case of empty containers (200% growth) and the fact that 
structures like QObjectPrivate (in qt4, not in 5) grow in size too. A quick 
check of Qt Creator showed that it had 79850 empty QStrings created, so the 
marginal impact of this would be an additional 160k of heap. At the time of 
the test, Qt Creator's heap was at 240 MB RSS, so the increase would be of 
0.066%.

Sharing of the d pointer
~~~~~
For all static data, the d pointer contains the same value of the flags. We've 
decided to just share it among all statics (QStringLiteral, 
QByteArrayLiteral). We'll also figure out a way to make the empty vs null 
distinction continue to work.

In fact, with this, QStringLiteral will not require a lambda.

More optimisations
~~~~
We discussed the optimisations of the ref() and deref() operations, which 
should be fast. The needsDetach() operation does not need to be as fast, since 
it is always followed by a slow operation.

We did not reach a full conclusion on whether using specific values in the 
refcounter or bits in the flags is more efficient.

isSharedWith
~~~~
We spent too much time (around 5 minutes) discussing this function. It does 
not make sense in the new architecture. We'll just mark it \internal and write 
an implementation that might be acceptable.

Getting it in
~~~~
Thiago and João will discuss the implementation details and will include 
others as necessary.

Still in Qt 5? To be honest, the benefits are great, so we'd like it in. We're 
also reasonably sure that there will be no regressions in any of the main API, 
as this code is tested extensively and any mistakes would show up somewhere 
(like moc and uic producing corrupt output when I changed QString). The rare 
API like isSharedWith above might have some changes, but should be really 
minimal.

I'll also post benchmarks of QVector.

-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel Open Source Technology Center
     Intel Sweden AB - Registration Number: 556189-6027
     Knarrarnäsgatan 15, 164 40 Kista, Stockholm, Sweden
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 190 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.qt-project.org/pipermail/development/attachments/20120624/c6403fa5/attachment.sig>