[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