Memory allocation overhead (Re: KFileItem)

[Thiago Macieira]

On domingo, 1 de setembro de 2013 10:46:45, David Faure wrote:
> On Friday 23 August 2013 12:57:15 Frank Reininghaus wrote:
> > http://code.woboq.org/userspace/glibc/malloc/malloc.c.html
> > 
> > A comment in that file [1] already says that the minimum allocated
> > size on a system with 8-byte pointers is 24/32 bytes (see below for an
> > explanation why it's not one fixed value).
> 
> Hi Frank,
> 
> Thanks for the detailed explanation!
> 
> I'm stunned. It means every class (in Qt and elsewhere) with a d pointer,
> uses 32 bytes for the d pointer, rather than the expected 8 bytes.

According to the comment, the a minimum allocation of 16 bytes includes the 
overhead. Since the pointer is also returned aligned to 8 bytes, it looks like 
the memory distribution is one of two possibilities:

	| <overhead> |  <wasted>  |   usable space   |
	0			 4			  8                  16

	| <overhead> |   usable space    | <wasted>  |
	0            4                   12          16

For 64-bit platforms, the minimum allocation is 32 bytes, the alignment is 16 
bytes. So the above graph is still the same, but multiply the byte offsets by 
2.

The choice between the two depends on the alignment of the chunk of memory. If 
the alignment of the chunk is a multiple of 2*sizeof(void*), it's the first 
case. If it's not, it's the second case.

For value-type classes (no virtual table), usually sizeof(Klass) == 
sizeof(void*). For object classes, since they have a virtual table, 
sizeof(Klass) == 2*sizeof(void*). It's the case I drew above.

In any case, the allocation is always the same (4*sizeof(void*) = 16 or 32).

If QObject were sizeof(void*) bytes larger, the allocation would then be 
either 5*sizeof(void*) or 6*sizeof(void*), depending on the alignment of the 
free chunk. Those two are almost evenly distributed, so we could say the 
average allocation size is 5.5 * sizeof(void*).

For the value-type classes, I agree we should use a few more bytes.

> Maybe in some cases (small private class + class instanciated many times) we
> would save quite some memory by moving some stuff as private members, like
> 
> Private *d; // not used for now, always null
> int m_value;
> int m_min;
> int m_max;
> int m_step;

My branch already has 
sizeof(QString) == sizeof(QByteArray) == sizeof(QVector<T>) == 3*sizeof(void*) 
and 
sizeof(QVariant) == 4 * sizeof(void*)

We'll implement that for Qt 6. It also enables "small string optimisation" for 
QString (5 characters) and QByteArray (11 characters).

For new value-type classes, we should start doing what you recommended. But we 
should design the class so that the d pointer gets used from the get go. 
Having it sit there and waste space is not going to help either.

> => one less allocation, 32 bytes saved per instance.
> 
> I wonder if all malloc implementations commonly used (i.e. including BSD,
> Mac and Windows) behave this way, though (but if they don't, the above
> doesn't lose anything anyway).
> 
> In the case of KFileItem, this obviously can't be done (huge private class).
> But making it a Q_MOVABLE_TYPE sounds right (since it is movable), we
> should just fix the code that relies on item pointers being stable across
> changes to the QList (e.g. by using QLinkedList).

If you care about memory overhead and efficiency, don't use QList.

-- 
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
   Software Architect - Intel Open Source Technology Center
      PGP/GPG: 0x6EF45358; fingerprint:
      E067 918B B660 DBD1 105C  966C 33F5 F005 6EF4 5358
-------------- 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://mail.kde.org/pipermail/kde-frameworks-devel/attachments/20130901/54028076/attachment.sig>