Handles are the better pointers
floooh.github.io
floooh.github.io
The best solution I found was to get rid of objects and allocation entirely and instead store the state of the game in per-type tables like in this article.
Then I realized that I didn't need per-type tables at all, and if I used what amounted to a union of all types I could store all the game state in a single table, excluding graphical data and textures.
Next I realized that since most objects had properties like position and velocity, I could update those with a single method by iterating through the table.
That led to each "object" being a collection of various properties acted on by independent methods which were things like gravity and collision detection. I could specify that a particular game entity was subject to gravity or not, etc.
The resulting performance was fantastic and I found I could have many thousands of on-screen objects at the time with no hiccups. The design also made it really easy to save and replay game state; just save or serialize the single state table and input for each frame.
The final optimization would have been to write a language that would define game entities in terms of the game components they were subject to and automatically generate the single class that was union of all possible types and would be a "row" in the table. I didn't get around to that because it just wasn't necessary for the simple game I made.
I was inspired to do this from various articles about "component based game design" published at the time that were variations on this technique, and the common thread was that a hierarchical OO structure ended up adding a lot of unneeded complexity for games that hindered flexibility as requirements changed or different behaviors for in-game entities were added.
Edit: This is a good article on the approach. http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy...
I then took it to the furthest extreme I could (everything in a single table) just to see if it would work well, and it did. Almost a purely functional approach to game architecture.
Frame State 0 -> Collection of composable functions to modify state -> Frame State 1
I found that to be vastly simpler and more effective than the OO approach of segregating state and functions into individual opaque objects. At that point OO seemed like such a brain-dead way to make things more difficult for myself I wondered if the entity-component idea wouldn't be more universally applicable to systems other than games. It is.
This was one of those rare cases where taking something to a logical extreme had an architectural benefit (all state in one easy-to-reason about table) that matched up really well with the performance benefit (memory locality). For systems where the system state is too large or varied to fit in a human's head, the benefits wouldn't be as apparent. But game states are, by definition, something that should be fairly easy to reason about because that's what the player is seeing and interacting with.
For instance, you could a physics system that loops over all of the velocity and position components and increments the positions by the velocity and a collision system that loops over the position components and handles collision.
>memory locality
The system you're describing has less memory locality than the ECS system described above. That's the main benefit of the added complexity of storing components separately. Another big benefit is that you can store different components in different types of data structures depending on how you need to access them.
Don't get me wrong, I'm not saying the ECS I'm talking about is necessarily better. It's not normally needed, and it's almost definitely overused by games that don't need it.
The idea behind it is that you can have a "WorldPosition" Component which stores all world positions as a flat array, and a "Gravity" System which acts upon WorldPosition components and makes them move. The idea is that since your data is tightly packed, it's easier to update.
A lot of people get this confused, though, so no worries.
The reason it worked in my case was that for a 2d game, the state of even the maximum sized entity was very small. For animated objects I had a per-entity integer that stored what frame to display. The texture and animation data was stored elsewhere outside the table, but that was also loaded before the game started so there was no allocation after that point.
For a 3d game with complex animations it would be foolish to try to store all the animation and texture data in the same table, but I'd probably do something very similar for the game state.
It took until the late 90's and some overenthusiastic misfires with class inheritance-based designs(they don't compose cleanly) for the modern component-driven styles to start emerging. The tradeoff being made in current engines is basically one of late vs early binding - it's easier to write tooling against a late binding system where you can attach more nodes arbitrarily(e.g. Godot's scene system), but your optimization potential is better if you can compute exactly the data structures and containers needed for each category of entity and asset(there's a talk from Handmadecon about how Destiny went too far down this path and worked themselves into a corner).
Edit: Also, the biggest sticking point for working a GC in games isn't really with the entity and asset management since pooling will suffice for guaranteeing the quantities of elements needed for any given scene; it's with algorithms that work with standard functions that expect a GC environment, like string manipulation.
Of course, I also didn't consider any extra space wasted since it could potentially be used for recycling new components.
django-typed-models https://github.com/craigds/django-typed-models
> polymorphic django models using automatic type-field downcasting
> The actual type of each object is stored in the database, and when the object is retrieved it is automatically cast to the correct model class
...
> the common thread was that a hierarchical OO structure ended up adding a lot of unneeded complexity for games that hindered flexibility as requirements changed or different behaviors for in-game entities were added.
So, in order to draw a bounding box for an ensemble of hierarchically/tree/graph-linked objects (possibly modified in supersteps for reproducibility), is an array-based adjacency matrix still fastest?
Are sparse arrays any faster for this data architecture?
Interesting, never came across it. But I've got a Django GitHub library (not yet open source, because it's in a project I've been working with on and off) that does the same for managing GitHub's accounts. An Organization and User inherit the same properties and I downcast them based on their polymorphic type field.
IDK how to do partial indexes with the Django ORM? A simple filter(bool, rows) could probably significantly shrink the indexes for such a wide table.
Arrays are fast if the features/dimensions are known at compile time (if the TBox/schema is static). There's probably an intersection between object reference overhead and array copy costs.
Arrow (with e.g. parquet on disk) can help minimize data serialization/deserialization costs and maximize copy-free data interoperability (with columnar arrays that may have different performance characteristics for whole-scene transformation operations than regular arrays).
Many implementations of SQL ALTER TABLE don't have to create a full copy in order to add a column, but do require a permission that probably shouldn't be GRANTed to the application user and so online schema changes are scheduled downtime operations.
If you're not discovering new features at runtime and your access pattern is generally linear, arrays probably are the fastest data structure.
Hacker News also has a type attribute that you might say is used polymorphically: https://github.com/HackerNews/API/blob/master/README.md#item...
Types in RDF are additive: a thing may have zero or more rdf:type property instances. RDF quads can be stored in one SQL table like:
_id,g,s,p,o,xsd:datatype,xml:lang
... with a few compound indexes that are combinations of (s,p,o) so that triple pattern graph queries like (?s,?p,1) are fast. Partial indexes (SQLite, PostgreSQL,) would be faster than full-table indexes for RDF in SQL, too.
If you refactor your object construction into factory functions, you can make the factory responsible for implementing the memory management, and the objects themselves responsible for implementing the memory use. The objects can be ignorant about the handle array. The objects can delegate any memory-related functions to the factory methods.
Given this article is about c++, no need for factory patterns or anything like that. You can overload the new operator on a global, and a per type basis and do it that way.
Specifically, this can easily be used to create a narrative for many functional idioms. The cost of memory and compute has been a large part of the ride in many modern tricks.
All those data items were structures in arrays, part of the "Polyhedron" object. All interconnections between them were array indices. The Polyhedron object owned everything for that polyhedron. Delete that and all the parts went away.
https://developer.apple.com/library/archive/documentation/ma...
I hope not.
Originally, a handle was an index in a table of allocated memory blocks; the idea was to be able to move these blocks around without affecting the program.
When Apple released computers which used 68030 processors, which had a 32-bit address bus, this trick stopped working. There was an awkward period where "32-bit addressing" was an option which could be turned on and off in the Memory control panel for compatibility with older software (and hardware!) which wasn't yet "32-bit clean".
This was definitely a case of someone not planning to be successful and not looking far enough into the future
It seems to me like separation of state and behaviours is one of those fundamental rules that should apply to most large software applications.
These problems indeed belong to a non-OOP view of programming. In OOP, the behavior is concentrated in objects while here a significant part of the behavior is concentrated in references.
I have been working on one possible generic solution which is called concept-oriented programming [1] and where references are first-class elements of the program where a great deal of the program behavior is performed during object access using these references.
One of the main ideas is that each object class is accompanied with a reference class. Such a couple is referred to as a concept (hence the name of the model). If reference class is empty then we get normal OOP. If object class is empty then we can model normal values (which are passed by copy). Of course, we can build a hierarchy by inheriting the behavior of references and objects (which is different from the classical inheritance but generalizes it in case we have only object classes).
COP is still on early stage and cannot be used just because there are other quite serious unsolved problems. But I see that the problems described in this post are not exceptions - describing how objects are represented and how they are accessed is an important piece of custom functionality in any complex system and it is precisely COP tries to formalize (along with some other tricky problems).
[1] http://conceptoriented.org Links on concept-oriented programming (COP)
http://www.mirandabanda.org/bluebook/bluebook_chapter30.html...
I've always wondered what the performance impact would be on 64 bit, assuming 32 bit indexes: on the one hand, half-size for most pointers, on the other hand extra indirection and the size of the table.
Video games are a special case where allocations and deallocations are often well scheduled and predictable. For the more general case, using a data type like ivector[1] for the object arrays would provide the desired memory safety. It gives you the flexibility of safely accessing an object via index, iterator or (zero-overhead smart) pointer. Even though it's a vector (like std::vector) its iterators behave like list iterators. That is, after an insertion or removal operation, unlike indexes, they continue to point to the same item (not necessarily the same position) and they only become invalid when the item they point to is removed. In particular, they don't become invalid after a resize/reallocation operation.
So using ivector's iterators instead of index handles would allow you to safely perform insertion/removal operations if necessary.
Also, for performance reasons you may sometimes want to temporarily obtain a direct pointer to the item. ivector allows you to obtain a zero-overhead smart pointer to the item that is guaranteed not to become invalid. [2] It does this by disabling "resize" operations on the vector while it exists.
[1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus#vectors
[2] https://github.com/duneroadrunner/SaferCPlusPlus#make_xscope...
As for those next steps, I'm under the vague impression that they aren't as popular these days because larger cpu caches have greatly reduced the cost of moving contiguous data in most real-world scenarios. So that more often than not the cache coherency benefits of simple contiguous data outweigh the avoidance of shifting some of that (contiguous) data.[1]
[1] simple microbenchmark of contiguous vs non-contiguous containers near the end of the article: https://www.codeproject.com/articles/1087021/stable-iterator...
At some point with bigger data you will hit the brick wall where the memory move is too expensive. This is typically at a bunch of megabytes in size for localized block inserts. The idea of these only slightly more advanced structures is to amortize the cost or defer it.
For instance, a gap buffer is essentially 3 vectors/arrays. Piece table is a few more, merged as needed, usually few. A zipper can mix contiguous (potentially heap) access with tree structuring for rarely modified or accessed parts.
As for iterator stability. Either the structure knows about a active iterators (expensive) and fixes them up or you should probably use plain old pointers as such. Bet you didn't know you can and should use a pointer as an iterator to a contiguous memory... And if you really for some reason do need to hold stable iterators to anything, std::array is good enough. Remember you cannot safely resize due to potential for memory copies on reallocation. (yes there are tricks, no they're very not cheap nor threadsafe nor concurrent) The consistency model of ivector iterators is not quite explicit.
Some observations about the strategy based on the article:
- It does *not* prevent memory leaks. It uses fixed size arrays, so once you allocate more memory
than there is room in the array, then the program has to exit.
- It does not prevent use after free. It just makes it easier to detect when this has happened.
Also this could work in any language. I wonder if it's common in game development for Android, because of Java and garbage collection spikes.
Oh, and another observation: I think this strategy is fully compatible with RAII and smart pointers. Smart pointers are implemented using malloc/free, and this strategy is isomorphic to malloc/free, so combining them should work fine.
widget_handle widget = widget_manager_new_widget(manager);
widget_tweak(manager, widget);
widget_tweak(widget)
{
actual_widget = widget_manager_lookup_widget(manager, widget);
}
Most of the benefits described can be had by using pools rather than a naive heap allocator.
Seem like a nice way to hide bugs, though.
The manager has to live in file-scope or above since there is no room in the handle to save a reference to it. At that point, you're creating a singleton and reducing the flexibility of the module. You now have all the usual issues with globals and singletons.
Unless of course you're passing around structures containing a handle and pointer to its manager...
The usual issues with globals pop up when people whant to run shortcuts and never implement the data separation from global to local when they should, think they can be used to replace a database like system, or - the horrors - use some multi level stack based system to push and pop global state as they merrily progress along the call stack - i.e run computations while using the global state as some sort of auxiliary storage unit.
Additionally thread safety puts very stringent requirements on global state, further making singletons and language goals worthless with few exceptions.
If you wanted to have different types of objects in one collection first you'd have to ask yourself if you really need to keep them together. But if so I suppose you'd just put base fields in one collection and new additional fields in another. Then handle to derived object would consist of two indexes, one in the base collection and the other in the collection of additional fields. Methods that access base field would need to use first index for them, and second index for additional fields.
Not sure if I'm being clear enough. Imagine you want to store collection of various subtyped objects in the database. This is pretty much the same problem. You keep base fields in one table, and specific fields in other tables (one for each subtype), and if you want to operate just on base fields you use base table, but if you want to operate on fields specific for a subtype you join base table with table that contains fields specific for that subtype.
Yes, there is a non-zero chance that spare bits will be identical. But that's only relevant, if you have a bug in your code wherein you are trying to use a destroyed handle. If you are never using a destroyed handle, then the spare bits being identical is completely okay.
Another way to think of this is that the spare bits are optional. The interface is good even if there were no spare bits. The spare bits only add an additional probabilistic security check.
Alternatively, give each item a unique handle (again counting up) and implement some sort of lookup table to convert those handles into actual indexes.
Depending on how many index bits you want, you might be good with only 64 bits in total. 2^56 ns in years = 2.3; 2^52 ns in days = 52; 2^48 ns in days = 3.3; and so on.
All of these figures are worst case scenarios, anyway. Your program probably simply can't actually be made to allocate objects at that rate.
This is exactly the same behavior you get with shared_ptr, both the user code AND the rendering system would hold a reference to the object and it would only be deallocated once BOTH of them destory their shared_ptr. weak_ptr allows even more fine grained control.
You still need to manage your resource lifetime somehow, with either some equivalent of unique_ptr or shared_ptr. Otherwise you've just reinvented global variables. How else would you know when to free an object from your object pool? A "least-used" pattern could be useful in some scenarios but then you also need to be able to reconstruct the object again in case someone asks for it after a long time of being idle (like swapping to disk).
My struggles are here: https://github.com/lostmsu/mem_bitness
No wonder that's slow and wasteful of both cache and branch prediction. What's wrong with using a proper generational moving garbage collector?
Yep.
> What's wrong with using a proper generational moving garbage collector?
Because then you don't have deterministic performance which is necessary in certain contexts–or am I misunderstanding you here?
But sure, there are cases where you want the level of predictability of reference counting, in which case I'd rather take the performance penalty than spend time and pollute the codebase doing a lot of tricks to arrange memory as a compacting garbage collector would.