4 ms·

> objects of the same type occupy continuous blocks in memory, Depending on the language, a single object may have a lot of overhead that adds up in an array.

> objects of the same type occupy continuous blocks in memory, Depending on the language, a single object may have a lot of overhead that adds up in an array. What you often see is one ArrayObject with arrays of properties, kind of like a transposition. A problem there is that in memory the arrays are of course laid out one after the other, which actually destroys cache locality if you need to access more than 1 property inside a loop (it will need to load back and forth to the different property arrays), so it's a somewhat dumb approach. But, at least it saves the overhead, so maybe not too bad. And in a high level interpreted language like php you likely weren't gonna get cache locality anyway. The point is to group all properties you are going to be accessing in a hot loop together in a small-ish array. C has structs for this, 0 overhead "entities" (although they may be padded to multiples of 4 bytes, so keep that in mind). You have compiler specific keywords to forego padding ("struct packing"), or maybe you're lucky and the data just fits exactly right. Either way, in such cases an array of structs is imo the most sane way to go. In fact, C++ offers classes and structs. In my opinion, struct should be used for entities like "weapon" or "car". CLASSES (or objects) should be unix-philosophy adhering miniprograms that do one task and do it well (oh hey, it's the single responsibility principle!). They way most programmers write OOP is a pretty convoluted way to model actual entities anyway. car.drive()? Oh? The car drives it self? No. agent.drive(car) should be the actual method. Agent, mind you, can be a driving AI, or a human driver, or whatever. Maybe the agent is a part of the car? In that case, use composition, not inheritance. (oh hey, entity component system!)

skocznymroczny 5y ago
OOP doesn't force you do do car.drive(). You can have an abstract agent class/interface with virtual "drive(Car c)" method. The method would be overriden by AIAgent, HumanAgent etc. The car itself would have more basic behavior, such as "accelerate()", "turnLeft()", "turnRight()"
- temporama1 5y ago
  Kill me now
- bruce343434 5y ago
  I think you are over engineering it. The way I imagine it: Car {float throttle, float brake, float wheel} inherits PhysicalObject {velocity, mass, position} Agent.accelerate(Car c){ c.throttle++; } Agent.drive(Car c){ ... accelerate(c); ... } Human inherits Agent
- orwin 5y ago
  Interface is the best way to do a clean job in this case.
- jhgb 5y ago
  > You can have an abstract agent class/interface with virtual "drive(Car c)" method. The method would be overriden by AIAgent, HumanAgent etc. Is that a convoluted way of saying "use multiple dispatch", or am I reading it wrong?
jcelerier 5y ago
> In fact, C++ offers classes and structs. In my opinion, struct should be used for entities like "weapon" or "car". CLASSES (or objects) should be unix-philosophy adhering miniprograms that do one task and do it well (oh hey, it's the single responsibility principle!). Please no. The only thing that matters is the language rules ; any non-computer-encodable arbitrary rule like this on top of the language rules just causes an additional lava layer. There is one difference between class and struct and it's default visibility. Use one or the other according to which causes less tokens to appear in your code
- bruce343434 5y ago
  Fair point
mytailorisrich 5y ago
> agent.drive(car) should be the actual method That's equally object-oriented so I don't see how OOP is a nonsensical way to model. A sensible model is up to the designer, not OOP.
- bruce343434 5y ago
  You're right. It's not OOP, but rather the way most tutorials teach it (and most programmers write it).
- ajuc 5y ago
  The reason OOP kills cache locality and multithreading opportunities is walking the object graph depth-first through nested method calls and pointers. Doesn't matter if it's car.drive() referencing driver through a private pointer or driver.drive(Car c) calling methods on Car through the provided parameter - in both cases you will jump from class Car to Driver and back and then again for the next car and the next driver. In real life the callstack is rarely 2-levels deep - I've seen stacktraces that had hundreds of levels. So your code will jump 100 levels down then 10 levels up then another 10 levels down, and so on, and then finally back up through 100 levels of nesting only to advance to the next top-level object and do the whole ceremony again for each of them :) It boggles the mind when you think about it :) When the object graph is big enough and doesn't completely fit in cache this slows the code by orders of magnitude each time you jump through the border. And because dependencies are implicit and execution order is accidental (and programmer doesn't actually know what other execution orders would be correct) - you cannot easily parallelize that code. The alternative is to specify the dependencies explicitly, split the data according to functions that use it not according to metaphysical Classes where it belongs and walk the data graph in levels - starting from the level that doesn't depend on any other code being run, completing the level first then going to the level that now has all dependencies satisfied, and so on. Of course there might be cycles that require special treatment, but at least they are explicit so you won't introduce them unless you actually have to. End result is basically "relational programming". In case of gamedev it's called Entity Component System.
  - mytailorisrich 5y ago
Firadeoclus 5y ago
> A problem there is that in memory the arrays are of course laid out one after the other, which actually destroys cache locality if you need to access more than 1 property inside a loop (it will need to load back and forth to the different property arrays), so it's a somewhat dumb approach. Caches are perfectly capable of dealing with more than one stream of data (there are some very specific edge cases you may have to consider), accessing multiple arrays linearly in a loop is generally more efficient than accessing a single array of structs when you don't use almost all the struct elements.
- moldavi 5y ago
  I've seen a lot of ECS implementations that store components in hash maps, keyed by entity ID. They iterate over one hash map in a linear way which is fast, but then they do a bunch of slow lookups like GP is saying. In those situations, GP's suggestions are wise. If you can iterate over arrays in parallel like you say, that's also a good approach.
  - ajuc 5y ago
    There are tradeofs between regular arrays, sparse arrays and hash maps in ECS - it's very similar in concept to storage hints in relational databases, and similarly to relational databases you can add indexes if needed.
  - professoretc 5y ago
    > They iterate over one hash map in a linear way which is fast, but then they do a bunch of slow lookups like GP is saying. Usually all but the most simple "systems" will need to access more than one component, which means you have a choice between a) store component data in regular arrays (and potentially waste huge amounts of space if relatively few entities have those components) or b) store component data in some kind of hash table (and then you use cache locality for all but the "primary" component of a system).
duped 5y ago
> A problem there is that in memory the arrays are of course laid out one after the other, which actually destroys cache locality if you need to access more than 1 property inside a loop (it will need to load back and forth to the different property arrays), so it's a somewhat dumb approach. This is actually why memory layout != DoD. You need to account for this in the architecture of the program, so that the systems only operate on a small amount of data that are relevant to them at one time. The tradeoff is paying for all the data, all the time, and some of the data most of the time. For a large class of programs that can be architected around mostly non-unique, trivially copyable fields with few relations, the tradeoff between AoS and SoAs is obvious. For other programs where your entities need relational information and form trees or graphs, it can be less obvious whether the data representation is going to be faster. However in these cases you store the relationship as your data (for example, as an adjacency matrix), but implementing any kind of textbook algorithm over it is basically reverse engineering pointers with indexes.

skocznymroczny 5y ago

OOP doesn't force you do do car.drive(). You can have an abstract agent class/interface with virtual "drive(Car c)" method. The method would be overriden by AIAgent, HumanAgent etc. The car itself would have more basic behavior, such as "accelerate()", "turnLeft()", "turnRight()"

temporama1 5y ago
Kill me now
bruce343434 5y ago
I think you are over engineering it. The way I imagine it: Car {float throttle, float brake, float wheel} inherits PhysicalObject {velocity, mass, position} Agent.accelerate(Car c){ c.throttle++; } Agent.drive(Car c){ ... accelerate(c); ... } Human inherits Agent
orwin 5y ago
Interface is the best way to do a clean job in this case.
jhgb 5y ago
> You can have an abstract agent class/interface with virtual "drive(Car c)" method. The method would be overriden by AIAgent, HumanAgent etc. Is that a convoluted way of saying "use multiple dispatch", or am I reading it wrong?

jcelerier 5y ago

> In fact, C++ offers classes and structs. In my opinion, struct should be used for entities like "weapon" or "car". CLASSES (or objects) should be unix-philosophy adhering miniprograms that do one task and do it well (oh hey, it's the single responsibility principle!). Please no. The only thing that matters is the language rules ; any non-computer-encodable arbitrary rule like this on top of the language rules just causes an additional lava layer. There is one difference between class and struct and it's default visibility. Use one or the other according to which causes less tokens to appear in your code

bruce343434 5y ago
Fair point

mytailorisrich 5y ago

> agent.drive(car) should be the actual method That's equally object-oriented so I don't see how OOP is a nonsensical way to model. A sensible model is up to the designer, not OOP.

bruce343434 5y ago
You're right. It's not OOP, but rather the way most tutorials teach it (and most programmers write it).
ajuc 5y ago
The reason OOP kills cache locality and multithreading opportunities is walking the object graph depth-first through nested method calls and pointers. Doesn't matter if it's car.drive() referencing driver through a private pointer or driver.drive(Car c) calling methods on Car through the provided parameter - in both cases you will jump from class Car to Driver and back and then again for the next car and the next driver. In real life the callstack is rarely 2-levels deep - I've seen stacktraces that had hundreds of levels. So your code will jump 100 levels down then 10 levels up then another 10 levels down, and so on, and then finally back up through 100 levels of nesting only to advance to the next top-level object and do the whole ceremony again for each of them :) It boggles the mind when you think about it :) When the object graph is big enough and doesn't completely fit in cache this slows the code by orders of magnitude each time you jump through the border. And because dependencies are implicit and execution order is accidental (and programmer doesn't actually know what other execution orders would be correct) - you cannot easily parallelize that code. The alternative is to specify the dependencies explicitly, split the data according to functions that use it not according to metaphysical Classes where it belongs and walk the data graph in levels - starting from the level that doesn't depend on any other code being run, completing the level first then going to the level that now has all dependencies satisfied, and so on. Of course there might be cycles that require special treatment, but at least they are explicit so you won't introduce them unless you actually have to. End result is basically "relational programming". In case of gamedev it's called Entity Component System.
- mytailorisrich 5y ago

Firadeoclus 5y ago

moldavi 5y ago
I've seen a lot of ECS implementations that store components in hash maps, keyed by entity ID. They iterate over one hash map in a linear way which is fast, but then they do a bunch of slow lookups like GP is saying. In those situations, GP's suggestions are wise. If you can iterate over arrays in parallel like you say, that's also a good approach.
- ajuc 5y ago
  There are tradeofs between regular arrays, sparse arrays and hash maps in ECS - it's very similar in concept to storage hints in relational databases, and similarly to relational databases you can add indexes if needed.
- professoretc 5y ago
  > They iterate over one hash map in a linear way which is fast, but then they do a bunch of slow lookups like GP is saying. Usually all but the most simple "systems" will need to access more than one component, which means you have a choice between a) store component data in regular arrays (and potentially waste huge amounts of space if relatively few entities have those components) or b) store component data in some kind of hash table (and then you use cache locality for all but the "primary" component of a system).

duped 5y ago

> A problem there is that in memory the arrays are of course laid out one after the other, which actually destroys cache locality if you need to access more than 1 property inside a loop (it will need to load back and forth to the different property arrays), so it's a somewhat dumb approach. This is actually why memory layout != DoD. You need to account for this in the architecture of the program, so that the systems only operate on a small amount of data that are relevant to them at one time. The tradeoff is paying for all the data, all the time, and some of the data most of the time. For a large class of programs that can be architected around mostly non-unique, trivially copyable fields with few relations, the tradeoff between AoS and SoAs is obvious. For other programs where your entities need relational information and form trees or graphs, it can be less obvious whether the data representation is going to be faster. However in these cases you store the relationship as your data (for example, as an adjacency matrix), but implementing any kind of textbook algorithm over it is basically reverse engineering pointers with indexes.