6 ms·
Linked lists have more consistent performance than std::vector. And taking half a second to render one frame when you're averaging 100fps is way worse than cons
by falcolas 12y ago
Linked lists have more consistent performance than std::vector. And taking half a second to render one frame when you're averaging 100fps is way worse than consistent 50 FPS.
There was recently an article about intrusive linked lists, and this same question came up. I took the unreal linked list library, and wrote a similar std::vector implementation, and tested it. The test was simple, fire 50,000 bullets at a rate of 500 rounds per second, and remove them when they fall 2 meters. They existed in 3 separate lists: physics objects, renderable objects, and all objects. When they hit the ground, they were removed from all lists. Capture the clock ticks to generate each "frame", and do a few calculations on them at the end.
The average and median operation times for std::vector were indeed a fair bit faster (at -o3, at no optimizations the ILL implementation was faster). However, the worst case for std::vector was... much worse. More than 1000x worse in some runs. One test run showed the worse case taking over two millisecond for a single frame of just manipulating vectors!
$ ./benchmark_ill
Minimum: 0.000000
Maximum: 0.000094
Average: 0.000005
Median: 0.000005
Total Frames Rendered: 18968118
Total Run Time: 100.663895
$ ./benchmark_v
Minimum: 0.000000
Maximum: 0.004813
Average: 0.000002
Median: 0.000002
Total Frames Rendered: 35859663
Total Run Time: 100.664009
- sillysaurus3 12y agoWait a sec. You can't bust out numbers like that without being clear about a few key points: 1. What was std::vector's removal algorithm like? Are you sure that .remove() wasn't shifting all elements in the vector? The "correct" removal algorithm in that case looks like this: Swap the target element to the end, and then decrease the vector's size by 1. But if I remember correctly, std::vector's remove method doesn't work like that, so of course it will have terrible worst-case performance if it was shifting all elements of the array when you remove the first one. 2. What's causing the worst-case slowdown? Are you sure you weren't simply seeing the effects of the L2 CPU cache being invalidated? A linked list will thrash the CPU cache constantly, whereas vectors thrash the cache much less since the elements are stored in contiguous memory. For a modern game running on a modern CPU, vectors are almost always the better choice for that reason. EDIT: I'm not sure your numbers are trustworthy. For example, there's no way it rendered 35859663 frames in 100 seconds. That would be 358,596 FPS. Assuming your FPS was actually something like 358, not 358,596, that's still an extremely high FPS. When your FPS is so high, it becomes difficult to accurately measure the reasons for worst-case performance. A sudden spike within a single frame could be for any of a dozen reasons, such as CPU cache eviction, a GPU pipeline stall, or some other program on your computer taking CPU resources.
- falcolas 12y ago> You can't bust out numbers like that Nobody is preventing you from writing your own benchmark and "busting out [your own] numbers". :) That said, yes, my deletion algorithm is naive, and I welcome a pull request to fix it. https://github.com/garrickp/intrusive_benchmark https://github.com/garrickp/intrusive_benchmark > Are you sure you weren't simply seeing the effects of the L2 CPU cache being invalidated Perhaps, but I doubt it's the cause of the worst case scenario, particularly since I'm doing identical loops over the physics and renderable objects, and as you say the linked list should have the worse performance. EDIT: One more small point - if the programmer is relying on the order of the items at all, the "tail tuck" method of deletion would not work. EDIT[2]: Addressing your edit - the numbers are only for the action of applying physics and adding/deleting objects - the code should reflect that. There is no actual rendering time or AI or anything else which would prevent us from seeing upwards of 100,000 "frames" per second. The times are also fairly stable (the standard deviation of max times is around 20%) between runs.
- sillysaurus3 12y agoI 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.
- flohofwoe 12y agoDynamic arrays like std::vector must be tweaked for a special use case as well, for instance it is quite essential to pre-allocate the array to a capacity of the expected number of entries using std::vector::reserve() so that no excessive re-allocation takes place while the array grows. Also special care must be taken if the objects have an expensive copy operation (that's where the new move-semantic in C++11 may help a lot).
- sillysaurus3 12y agoIt's not so much that dynamic arrays are the problem as std::vector specifically is the problem. Many game engines implement their own version of vector which is designed to grow by power-of-2. That way if you add 100 elements, the vector has already reserved 128 slots. If you add 129, it'll automatically reserve 256. Etc. Automatic power-of-2 growth turns out to have very nice performance and memory characteristics. std::vector itself might work that way, but since the implementation can be different on different platforms, it's usually a better idea to write your own when performance matters.
- flohofwoe 12y agoI agree! It's just that C++ people from outside the gaming industry always give me the evil look when I start ranting about how useless the std containers actually are ;)
- barrkel 12y agoI doubt there are any vector implementations that don't use exponential growth. Without exponential growth, push_back doesn't have constant time, and adding n elements doesn't take O(n) time. Since push_back is required to take amortized constant time, an implementation without exponential growth (or some kind of magic) wouldn't be standard conforming. Whether the exponential growth is in the form of doubling or not is just a constant factor. There's nothing magical about using powers of two. Depending on the accounting used by the allocator you're using, there may be synergies, or there might not be - some allocators require a few bytes more than the allocation request, and this requirement might inflate the underlying memory request more than necessary.
- jokoon 12y agoalready read that article about ILL, did not make much sense to me. Where do you explain why the vector is slower ?
- falcolas 12y agoI'm not saying they're slower, I'm saying the performance is more consistent. 99.9% of the time the std::vec implementation will out preform the linked list. However, that 0.1% seems to be wildly worse than the linked list. This is not a problem for most programs, however in gaming engines that hiccup shows up as a visible hitch in the framerate.
- jokoon 12y agoSo to you, that 0.1% is specific to gaming engines, how ? I don't really believe it. I think "that 0.1%" demonstrates that linked list are really irrelevant and that vectors should be used all the time. The only useful advantage of linked lists is to be able to insert an element in the middle of the list. I don't understand why anyone would want to insert data in the middle of a list, you rarely want to do that in O(1), and even if you do, you still need to know where exactly you want to insert it. If you want to have data sorted, use map<>, if you want a faster map, use a hash map. Maybe lists are relevant for vertex geometry, because it might be interesting to quickly edit and add vertices, but it's such a specific case I don't think it matters. Nobody really edits vertex geometry. You could even just build an index vector instead.
- falcolas 12y agoI don't believe it's problem endemic only to game engines, but game engines are particularly vulnerable to such latency. Google reveals many examples of how hitching causes problems for players. I'm not going to claim that memory is the primary, or even a remotely major cause of such hitching, but it's certainly not going to help when you have to spend one of the 16 milliseconds given to render a frame on memory allocation and re-ordering.