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é _______________________________________________ Development mailing list [email protected] http://lists.qt-project.org/mailman/listinfo/development
