What is a fast, cache-friendly object/entity system?

[RonanZero]

My game is going to be run on some systems where the CPU is a bottleneck. There may to be FPS drop issues if I structure my code badly. I know a little tiny bit of how to optimize memory accesses in C++, in Lua not so much especially since it's a scripting language. I need to minimize cache misses on the script side. What sort of data structures should I be using?

Just normal metatables that hold all their variables inside each instance?
Separate arrays for common object variables? Like, object_x[], object_y[], object_sprite_id[] etc. so I don't need to follow the object for that specific piece of data?
Something else?

My original design was a very "managed" object system; a lot of things would be handled by the "world", like instead of the object drawing itself it just has parameters like should_draw, sprite_id, offset etc. Same for collision handling, it just specifies it's collision box area and the "world" does the rest, notifying objects when/if a collision happens.

I'm not sure if that idea better or worse than them handling drawing themselves in a :draw() method, for example. I can go either way.

[raidho36]

If you're going to use struct of arrays like this you're guaranteed to miss cache a lot. You would usually want to optimize this for each type of component, with all component data allocated in close proximity. Tables are allocated in memory contiguously so the whole thing would usually be fetched, but beyond that it's a pretty random heap allocation. Only sequential allocation has good odds of taking adjacent space, but then garbage collection would ruin it anyway. For rigid enough objects you could use C structs, then you could put them in memory in a way that optimizes cache access, although that's in a realm of micro optimization (which could worsen the performance even) because modern processors prefetch data pretty well. LuaJIT is compiled to machine code and if coupled with C data it could offer decent memory allocation control. Note that you will gain more from using C data exclusively in computations than you would through optimizing memory layout.

[RonanZero]

Is what you mean, having for example a "sprite component" or "collision component", store them all in their own component arrays (like object #2's sprite data is in sprite_components[2] etc.), then update each component sequentially from object 1's component to the highest object index? That's good for less cache misses?

Like

Code: Select all

for obj_id=1,maxObjects do
    draw_object_sprite(sprite_component[obj_id])
end

[raidho36]

The idea is that if a component is localized in memory, then it could be easily pre-fetched in a loop, and it could stay in cache. If it's spread across multiple arrays then a part of each array has to be fetched individually, which usually doesn't work as well, and it's at higher odds to get wiped out of cache. Performance of traversing an array of pointers to random memory locations would depend on CPUs speculative execution capabilities.

Fun piece of trivia, RAM was called "random access" because in principle you could access any location in it at the same speed, even if you choose address randomly, so you didn't had to worry about memory access pattern - as opposed to physical storage units which work best if you read data sequentially. Well, apparently, with modern hardware you need to read RAM sequentially too, and it became but a faster smaller "disk" drive that can't retain data. Exemplified by SSDs.

[RonanZero]

So is my idea above correct?

[raidho36]

Well, yes, but you'll need to do more work than that. If you use arrays of objects that are not contiguous in memory, it's the same as if you accessed them with no pattern at all. So I suppose if you want substantial improvement you'll have to get your hands dirty and use FFI and C data.

Code: Select all

ffi.cdef ( "typedef struct entity_t { double x, y, dx, dy; int foo, bar; } entity_t;" )
entities = ffi.new ( "entity_t[ ? ]", max_entities )
for i = 0, num_entities - 1 do
    entities[ i ]:update ( )
end