[Development] Changing container privates again

João Abecasis joao.abecasis at nokia.com
Mon Jun 11 11:02:24 CEST 2012


On 9. juni 2012, at 17.45, ext Thiago Macieira wrote:

> Hello
> 
> Moving the discussion from the series of patches I've begun on Gerrit to the 
> ML.
> 
> tl;dr: all I wanted was to add the prepend optimisation to QVector so I could 
> work on QList. Then João told me of a request by Tor Arne about letting 
> QString have a "notify of destruction" function. So I changed the internals of 
> QArrayData again.
> 
> Current QArrayData is:
> 
> struct Q_CORE_EXPORT QArrayData
> {
>    QtPrivate::RefCount ref;
>    int size;
>    uint alloc : 31;
>    uint capacityReserved : 1;
> 
>    qptrdiff offset; // in bytes from beginning of header
> 
>    [ member functions ]
> };
> 
> Size is 3*4 + maybe padding + pointer size = 16 bytes or 24 bytes
> 
> After my changes, it is:
> 
> struct Q_CORE_EXPORT QArrayData
> {
>    QtPrivate::RefCount ref;
>    uint flags;
>    int size;       // ### move to the main class body?
>    // -- 4 bytes padding here on 64-bit systems --
>    qptrdiff offset; // in bytes from beginning of header
>    // size is 16 / 24 bytes
> };

The most often used elements have to be offset and size. The ref-count is used in copying and detaching, as typically will be the flags.

As long as we're doing more open-heart surgery I would support moving offset and size to the beginning of the struct, to try to avoid padding holes.

If we are to inline any data in QVector/QString/QByteArray/QList themselves, offset and size should go together, which would potentially make sizeof(QContainer) == 3 * sizeof(void*), up from sizeof(void*). Read-only operations wouldn't touch the header or the reference count at the cost of copies and, well, sizeof(QContainer).

> struct QArrayAllocatedData : public QArrayData
> {
>    uint alloc;
>    // 4 bytes tail padding on 64-bit systems
>    // size is 20 / 32 bytes
> };
> 
> struct QArrayForeignData : public QArrayData
> {
>    void *token;
>    void (*notifyFunction)(void *);
>    // size is 24 / 40 bytes
> };

Following Olivier's suggestion I think it might be beneficial to have alloc unconditionally in the base class, even if it is not being used at times. If nothing else, it saves padding. Additionally, deleter function and token would be more generally useful if they can be used with the alloc member.

Say, you allocate a buffer, you want some QContainer to manage it *and* change it in place as necessary *and* free it when done. This is similar to the WebKit use case, but here we don't assume an external ref-count so ref-count of 1 means the data can be changed.

> The changes are:
> - instead of a single bit of flags, there's a full integer now (32 bits), 
> which allow us to to more things.
> 
> - I've reserved 3 of those bits to indicate the type of array: raw data (like 
> QStringLiteral and fromRawData), heap-allocated data, foreign data.

I want to clearly discuss what those bits or flags will mean and their exact semantics. These are my suggestions:

    - CapacityReserved (taking over from the current bit)
    - Mutable (taking over from alloc != 0, frees alloc member to be reused when data is immutable)
    - Notify/Deleter (new functionality)

> - foreign data is like fromRawData: it comes from somewhere else, we don't 
> manage its memory and it's immutable. The difference is that we'll call a 
> notify function (see above) when our refcount drops to zero. This allows, for 
> example, to use QString on data managed by WTF::String or UTF-16 data stored 
> in an mmap'ed page.

Let's make "foreign" and immutable orthogonal.

> - the "alloc" member is moved from the standard data to the allocated data 
> (it makes sense). This member should only ever be accessed in non-const 
> functions (more or less, there are exceptions), usually after those functions 
> have decided that they need to allocate or reallocate memory.

Let's keep it in the base but not overload it with the "mutable bit"?

> - as a drawback, the header overhead in memory allocation increases 4 bytes 
> on 32-bit systems and 8 bytes on 64-bit ones (due to the presence of tail 
> padding). It's possible to store data in that tail padding, though, but I 
> don't want to .

Keeping alloc in the base and moving things around sizes would be fixed at 20/24 bytes, with no padding. "Foreign" data would grow the header to 28/40 bytes.

> - in fact, I was thinking of changing the size and alloc members to size_t, 
> so this header could be used on a container supporting larger memory sizes, if 
> we wanted to, in the future.

As long as we're having this discussion, I see no reason not to make them unsigned, at the very least. I support size_t as well.

> - André requested that the size member be moved away from the header into the 
> main class body itself. I haven't done that yet and I'm not sure I should. It 
> would be major surgery for something that we haven't proven yet. And I don't 
> think we have time to prove it. But it would decrease the size of the header 
> by 8 bytes on 64-bit systems.

I think it only helps if we move both offset and size together. I'm not convinced this is something we should be doing. (Besides now being very sub-optimal timing for this discussion to be happening ;-)

> - since we stored the type of the data, we know when we allocated it. Since 
> we know that and we know the size of the header, the "offset" member becomes 
> the prepend optimisation: we know how much buffer we have between the end of 
> the header and the beginning of the data.

This requires that we tie "foreign" to detached allocation and "native" (not-"foreign" :-p) to a single allocation. This is an assumption that I would like to get rid of. Perhaps we can make it hold for the constrained use case of QList, which offers the prepend optimization.

Another option is to keep an extra pointer to the beginning of the data, together with (or after) the alloc member. This would mean "foreign" and prepend-optimization will be mutually exclusive. This is fine for the QList use case we currently have, but is something that needs to be discussed as these subtleties do have an impact in how much interoperability we can get between QList and QVector.

(Another use case for all of this is QRingBuffer. Even without building it now we should enable it to use the same infrastructure)

> Besides all that, there are a bunch of small changes. Before we discuss the 
> minor changes and implementation details (whether we need one or two option 
> enums, for example), I'd like to know if anyone has more ideas relating to the 
> headers themselves.

Following what was discussed in the patches themselves, I suggest you keep AllocationOptions around as long as reasonable and then we'll have a much better idea of whether to keep them independent or ditch them ;-) But agreed, those are implementation details and there are still some issues above that need to be hammered down.

Cheers,


João




More information about the Development mailing list