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

André Somers andre at familiesomers.nl
Fri Jul 10 14:18:08 CEST 2015


Smith Martin schreef op 10-7-2015 om 13:27:
>> I think the impedance mismatch here is that you use "list" to mean the same
>> thing as "array" or "vector" (in STL terms, not mathematically) while I only
>> use it to mean "linked list", in accordance with the STL.
> I actually just mean it's a list, and I don't care how it is implemented. I can see that it makes a difference how it is implemented, depending on how it is used, but if the use is simply: 1) build the list once; 2) process the list once, and every time I add an element to the list I have to create it somewhere, I don't see why creating it on the heap is inefficient.
>
Ah, but you _should_ care. It is a problem that programmers use 
(sometimes very complex) containers without having a clue of how they 
work, and what the performance implications of that complexity is. How 
are you going to choose the right container for your use case then?

In your case, a vector _would_ be more efficient. The problem with the 
list setup is the double indirection and the memory fragmentation that 
comes with that. Please realize that memory is no longer fast. Memory 
was about as fast as CPU's 20 years ago. Now, memory is about 400x 
slower than your CPU. That means, that if your CPU needs data that is 
not in a cache (which is an effort to fix the slowness of your RAM), it 
needs to wait for about 400 cycles until it can proceed. That is slow. 
That means that you really want to be efficient in how you access your 
data. A data structure that puts all relevant data next to each other 
and doesn't waste any space (read: a vector or a simple array) makes it 
much easier for the computer to make sure that all memory needed for a 
loop is actually loaded into cache once it is needed. It becomes much 
harder to do that if you have an array of pointers to who-knows-where in 
memory where the actual data resides. That means that the CPU first has 
to follow the pointer to the array, and then every time the pointer to 
actual data. That means a memory access more, and a big chance of the 
data you really need not yet being in your cache, incurring the wait 
time to load it. That is not going to be fast.

So yes, you _should_ case about what is going on. You are going to 
choose what the right container is by applying your knowledge on the 
performance trade-offs the classes you use.

The situation is even worse with using datastructures like QMap and QSet 
by the way...

André




More information about the Development mailing list