3 ms·

I apologize that my comment probably came off as a bit too upfront. I need to work on that. I was only saying that it isn't really a good idea to present numb

I apologize that my comment probably came off as a bit too upfront. I need to work on that. I was only saying that it isn't really a good idea to present numbers like that without having a clear idea of what's causing the worst-case performance. Glancing over the code, and assuming the first bullet fired is always the first one to impact the ground, it looks like the code is always going to run std::vector::erase on the first element of the vector, which will always shift the 499 remaining elements. It's possible that's the reason for the worst-case performance, rather than vector being inherently a worse choice than list. It was very counterintuitive and weird to realize that vector is almost always a better choice than list due to how powerful the CPU caches are. CPU caching is so good that taking full advantage of caching will usually outweigh algorithmic tweaks, like whether you're using a list or a vector. So the power of vector is that its elements are in contiguous memory, whereas the downfall of list is that they usually aren't. It's difficult to prove that's true except in real-world scenarios. Unless a test is designed to introduce memory fragmentation, the cache performance penalty of using list won't really show up in the results. All of the list allocations will be pretty much contiguous in a test environment, so the tests will show performance on par with vector. But in the real engine, you'll be left scratching your head why everything's running so slowly, when the answer is because the elements are sprayed all across your memory space and it's causing the CPU cache to stall when they're accessed... EDIT: There is no actual rendering time or AI or anything else which would prevent us from seeing upwards of 100,000 "frames" per second. When your FPS is higher than, say, 1,000, it becomes very difficult to pin down the reasons for performance fluctuations. An engine under load behaves differently than an artificial test, so you'll need to measure the performance impact in a real engine, especially when the framerates in the test are so high. Your monitor is capped at 70 fps, or some high-end monitors can do ~130. Something like 100,000 fps isn't an accurate reflection of the behavior of the real system. Most of the discrepancy is due to memory fragmentation causing CPU thrashing, but your specific test might be running into some other discrepancies, like: - clock() might not be a high resolution timer, so the worst-case timing might be due to discrepancies in the clock mechanism itself, especially at 100,000+ FPS. See http://stackoverflow.com/questions/6749621/high-resolution-timer-in-linux http://stackoverflow.com/questions/6749621/high-resolution-t... - since your test is running for 100+ seconds and your timing measurements are taking into account an entire frame, some frames are going to run interrupts. If an interrupt takes a long time to process, that load will show up in your timing measurements. The result is that vector (or list) will be unfairly pinned as the reason for the performance issue, when interrupts were the cause. I'm not confident about the second one, but the point is that there are all kinds of conflating variables.

falcolas 12y ago
> So the power of vector is that its elements are in contiguous memory In either case, you'll end jumping all over memory for the actual items in either a std::vec or a linked list, since they are both holding pointers to the actual objects (and based on how the nodes are being created, the linked list containers are closer in memory to the nodes). That said, my premise was not that linked lists were faster to iterate over, it's that they offer a consistent addition/removal time, which is frequently better for a game engine than access with huge deviations. There are many games out there which boast 100+ FPS on my gaming computer. However, they still look like crap because they will have intermittent drops to 1 or even .5 fps. I (and many others) would prefer a constant 50 (or 30) FPS than a stuttering 140. Real time OSes offer the same commitments: constant gaps between program resumes, even if that constant delay is large.
- sillysaurus3 12y ago
  Okay, there's some kind of failure to communicate, and the frustration level is rising. The failure is probably on my end, so I apologize. In either case, you'll end jumping all over memory for the actual items in either a std::vec or a linked list, since they are both holding pointers to the actual objects (and based on how the nodes are being created, the linked list containers are closer in memory to the nodes). That said, my premise was not that linked lists were faster to iterate over, it's that they offer a consistent addition/removal time, which is frequently better for a game engine than access with huge deviations. CPU caching doesn't work like that. When you access any pointer, the CPU cache will automatically cache 256 bytes from the access address. So if your object is at address "x", everything from [x, x+256) will be put into the CPU cache. Your Projectile class contains 6 floats, so each Projectile is 24 bytes. When you're using std::vector, all of your projectiles are stored contiguously in memory. That means when you access a projectile, you'll automatically cache (256 bytes / sizeof(Projectile) - 1) = the next 9 projectiles. So you get a bunch of performance for free, simply by using vector. When you use list, you lose all of that caching. The reason is because list's memory allocations are all over the place. When you use list, the memory region [x, x+256) is solely that one projectile. That means your CPU will end up caching a bunch of irrelevant bytes of memory. That also means the CPU will have to cache each projectile individually as they're accessed. You're trading automatic caching of 10 projectiles for having to cache each individual projectile. Since taking advantage of CPU caching gives you 10x or 100x speedups, that's a very bad tradeoff. Addition/removal from a container is a tiny, tiny fraction of tininess of what a modern game engine does. It's so tiny that add/removal performance is almost always irrelevant unless you're adding/removing a huge number of elements every frame, which is rare. Iteration performance is almost the only thing that matters for a game engine, because every single frame you'll be iterating over hundreds of containers. If each iteration causes your CPU cache to thrash, then you're in for a world of pain. The takeaway is that list is an awful choice for any realtime game, and it's dangerous to give the impression that it's better. If someone were to take your tests at face value and start using list in their own game engines, a few months later they're going to be wondering why their performance is so terrible and why their profilers aren't showing the cause. As far as performance characteristics go, memory fragmentation / CPU caching matter so much that discounting them is a recipe for disaster. There are many games out there which boast 100+ FPS on my gaming computer. However, they still look like crap because they will have intermittent drops to 1 or even .5 fps. I (and many others) would prefer a constant 50 (or 30) FPS than a stuttering 140. Agreed! But list vs vector isn't the cause. A lot of the stuttering has to do with loading resources from disk, flushing the GPU pipeline, or other I/O intensive actions. On a modern CPU, add/removals from containers aren't the reason for the slowdown. Either way, good luck, and keep on making cool stuff.

falcolas 12y ago

> So the power of vector is that its elements are in contiguous memory In either case, you'll end jumping all over memory for the actual items in either a std::vec or a linked list, since they are both holding pointers to the actual objects (and based on how the nodes are being created, the linked list containers are closer in memory to the nodes). That said, my premise was not that linked lists were faster to iterate over, it's that they offer a consistent addition/removal time, which is frequently better for a game engine than access with huge deviations. There are many games out there which boast 100+ FPS on my gaming computer. However, they still look like crap because they will have intermittent drops to 1 or even .5 fps. I (and many others) would prefer a constant 50 (or 30) FPS than a stuttering 140. Real time OSes offer the same commitments: constant gaps between program resumes, even if that constant delay is large.

sillysaurus3 12y ago
Okay, there's some kind of failure to communicate, and the frustration level is rising. The failure is probably on my end, so I apologize. In either case, you'll end jumping all over memory for the actual items in either a std::vec or a linked list, since they are both holding pointers to the actual objects (and based on how the nodes are being created, the linked list containers are closer in memory to the nodes). That said, my premise was not that linked lists were faster to iterate over, it's that they offer a consistent addition/removal time, which is frequently better for a game engine than access with huge deviations. CPU caching doesn't work like that. When you access any pointer, the CPU cache will automatically cache 256 bytes from the access address. So if your object is at address "x", everything from [x, x+256) will be put into the CPU cache. Your Projectile class contains 6 floats, so each Projectile is 24 bytes. When you're using std::vector, all of your projectiles are stored contiguously in memory. That means when you access a projectile, you'll automatically cache (256 bytes / sizeof(Projectile) - 1) = the next 9 projectiles. So you get a bunch of performance for free, simply by using vector. When you use list, you lose all of that caching. The reason is because list's memory allocations are all over the place. When you use list, the memory region [x, x+256) is solely that one projectile. That means your CPU will end up caching a bunch of irrelevant bytes of memory. That also means the CPU will have to cache each projectile individually as they're accessed. You're trading automatic caching of 10 projectiles for having to cache each individual projectile. Since taking advantage of CPU caching gives you 10x or 100x speedups, that's a very bad tradeoff. Addition/removal from a container is a tiny, tiny fraction of tininess of what a modern game engine does. It's so tiny that add/removal performance is almost always irrelevant unless you're adding/removing a huge number of elements every frame, which is rare. Iteration performance is almost the only thing that matters for a game engine, because every single frame you'll be iterating over hundreds of containers. If each iteration causes your CPU cache to thrash, then you're in for a world of pain. The takeaway is that list is an awful choice for any realtime game, and it's dangerous to give the impression that it's better. If someone were to take your tests at face value and start using list in their own game engines, a few months later they're going to be wondering why their performance is so terrible and why their profilers aren't showing the cause. As far as performance characteristics go, memory fragmentation / CPU caching matter so much that discounting them is a recipe for disaster. There are many games out there which boast 100+ FPS on my gaming computer. However, they still look like crap because they will have intermittent drops to 1 or even .5 fps. I (and many others) would prefer a constant 50 (or 30) FPS than a stuttering 140. Agreed! But list vs vector isn't the cause. A lot of the stuttering has to do with loading resources from disk, flushing the GPU pipeline, or other I/O intensive actions. On a modern CPU, add/removals from containers aren't the reason for the slowdown. Either way, good luck, and keep on making cool stuff.