[Development] HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO

[Thiago Macieira]

On Friday 10 July 2015 15:22:13 Milian Wolff wrote:
> > In this case, qdoc creates a QList<ParsedParameter> as it parses a
> > function
> > signature. All the calls to malloc occur one right after another, and then
> > the list is complete. There hasn't been any intervening heap work, so all
> > these ParsedParameters will be sequential and will be allocated right
> > after
> > the QList itself.
> 
> This is not necessarily true. Malloc implementations are free to return
> random  pointers. Maybe you are lucky and the stuff is sequential, most
> probably not.

Don't forget the overhead of each allocation.

If you're allocating 16 bytes, for example, then Glibc's malloc will return 
pointers that are offset 32 bytes from each other. That means you get two 
elements per cacheline, as opposed to four.

A QList of 8 elements of 16 bytes each occupies:
	8 * sizeof(void*) + sizeof(QListData) + overhead = 8 * 8 + 16 + 16
	8 * (sizeof(element) + overhead) = 8 * 32
	-----
	352 bytes (6 to 19 cachelines)[*]

A QVector of the same 8 elements is
	8 * sizeof(element) + sizeof(QArrayData) + overhead = 8 * 16 + 16 + 16
	---
	160 bytes (75% chance of 3 cachelines, 25% of 4 cachelines)

The best of QList is still 50% worse than the worst of QVector.

[*] How I came up with these numbers:
the array block is 96 bytes long, so in the best case it spans 2 cachelines. 
In the best case, each of the 32-byte blocks for the elements is contiguous, 
so we have one single 352-byte block. That's 6 cachelines.

in the worst case, the array block spans 3 cachelines due to alignment and 
each of the 8 elements is not only in a different cacheline, each also spans 2 
cachelines without sharing them with other elements or the array header.

Now, to be fair, iteration does not touch the region for malloc's overhead, so 
iterating would touch at most 2 + 8 = 10 cachelines in the worst case, but 
still 6 on the best.
-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel Open Source Technology Center