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

[Randall O'Reilly]

I’m surprised nobody has mentioned that, because of the private data nature of most Qt classes, they are a) already allocating the private data object on the heap all the time and incurring all that overhead and memory allocation badness, and b) are essentially a pointer to an object already — thus QList adds another redundant pointer on top of that, and hence QVector functions much like a QList might have worked for objects with significant amounts of their own member data.  Seems like a compelling argument in favor of QVector to me..

- Randy

> On Jul 10, 2015, at 1:33 PM, Thiago Macieira <thiago.macieira at intel.com> wrote:
> 
> 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
> 
> _______________________________________________
> Development mailing list
> Development at qt-project.org
> http://lists.qt-project.org/mailman/listinfo/development