4 ms·
The part about hand maintained lists is a common pitfall in game development. When you're trying to push out frames at 60fps, you generally need to be caching q
by reitzensteinm 14y ago
The part about hand maintained lists is a common pitfall in game development. When you're trying to push out frames at 60fps, you generally need to be caching quite a lot of values, for example, "Get all units that are moving" or "Get all units from side x".
The absolute best way to handle this is to start off with safe, conservative functions, that don't cache at all - create a list, iterate over each entity, add whatever fits the condition.
Then, after profiling to see what's slow, you hand roll a system that keeps a specific list updated continuously; and then importantly, keep around the old function, and in debug mode compare the lists occasionally (I usually do it every 100th access, so the game is still playable).
After that, you may not know what's causing a cached value to go out of sync, but you can at least know it's happening, instead of getting some of the most convoluted and maddening bugs imaginable. The kind that make you want to take up farming (and I'd be a shitty farmer).
- marshray 14y agoThe part about hand maintained lists is a common pitfall in game development. Whenever I hear something about hand-maintained data structures I think probably some manager or lead programmer banned C++ templates and other abstraction mechanisms because they were "too tricky and hard to understand".
- Peaker 14y agoStandard templated linked lists are suboptimal. Simple C lists ala Linux's list.h are simpler and more optimal, behavior-wise.
- marshray 14y agoWell I didn't say you had to use std::list. One can implement exactly the same behavior as Linux list.h in C++, but type-safe and namespace-scoped. But some managers prefer #defines. To each his own.
- Peaker 14y agoThe behavior of list.h essentially boils to downcasting from a list node to its container. Allowing multiple list nodes in the same container, and re-use of the same node for different lists. How do templates make this type-safe?
- marshray 14y agohttp://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/list.html http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/list... How do templates make this type-safe? By using composition instead of inheritance, it avoids the downcasting. If you want to, you can even have objects that are elements in several different lists using tag types to let the compiler keep the lists from getting cross-linked. Or you may prefer to use the node pointers for different things at your discretion. Self-removal on destruction can be useful too. All without any more run-time overhead than the two pointers you need in C.
- Peaker 14y agoI tried reading the code in intrusive/list_hook.hpp and intrusive/list.hpp, and it's quite difficult to read. However, it does seem that it inserts an extra pointer to the member (beyond the prev/next) in order to avoid the "cast". If it indeed does so, it is again less optimal than Linux's list.h. On 64-bit machines, 8 extra bytes for each list element is not always negligible. Also, the examples do not showcase using the same list member node to put in multiple lists. There's also the unsafety of putting the list node in a union (mentioned in the article) which adds unsafety regardless of templates or not. I agree about destructors improving safety, I was specifically talking about templates. With list.h, it is possible to get the same safety (unless I am misunderstanding something about the boost example) by wrapping the list anchor and node structs with a struct (typically done by a macro to define the anchor/node), which adds an array-of-0-elements of the type of the container. This allows adding the same type checks demonstrated here using templates, implemented in the list iteration, insertion/deletion and downcasting macros.
- 14y ago