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

[Thiago Macieira]

On Friday 10 July 2015 09:50:40 Thiago Macieira wrote:
> 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.

BTW, if you benchmark the same QLinkedList:
	16 + overhead = 32 bytes		[1 or 2 cachelines]
	8 * (sizeof(QLinkedListNode<T>) + overhead) = 
		8 * (2 * sizeof(void*) + sizeof(T) + overhead) = 8 * (16 + 16 + 16)
		= 384	[8 to 16 cachelines)
	-----
	416 bytes [7 to 18 cachelines]

Comparing on cachelines, QLinkedList's best is worse than QList's best, but 
its worst is best than QList's worst.

Comparing on memory allocation, QLinkedList is 18% worse than QList and 160% 
worse than QVector. QList is a better list than QLinkedList. It's not a 
vector.

You really want to use a vector for everything except if:
 - you NEED O(1) insertion or deletion anywhere	→ use QLinkedList
 - you want stable element pointers even if the container is modified
 - copying your type is expensive and your container gets modified a lot

The first two are extremely rare.

-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel Open Source Technology Center