Data Locality and Polymorphism [closed]

Question

I've been reading over the various chapters available at http://gameprogrammingpatterns.com, and in particular his chapter over Data Locality(http://gameprogrammingpatterns.com/data-locality.html) has raised a few questions. I've sent him out an email, but while waiting for it I figured I'd gather the opinions of others.

In the chapter, it is suggested that you would take your GameEntity class and strip everything away, sticking all of the components into an array and using a dirty bit to tell whether or not the component is active. This allows for faster iteration and avoids thrashing the cache.

However, it is also stated to avoid polymorphism in order to keep all components of some type the same size, and avoid virtual methods. Rather, for every type you would have an array. To me, this sounds wasteful. Say I have 20 different enemies, and I allow for 100 enemies to exist at a time. That'd be 21(20 different MOBs + 1 array that would hold the entity) arrays of 100 entries, so 2100 objects just for the different enemies. And then each enemy needs a physics component, a rendering component, and maybe even more depending on the game. If every enemy needs it's own physics and rendering component, that'd be 21 Entities + 20 Physics Components + 20 Rendering Components, all multiplied by 100(or however many entities you are allowing to exist at once). That's a lot of data for stuff that isn't going to even be used most of the time.

Wouldn't it be simpler(and smarter) to just have arrays of the base class, then stick in the needed subclass at some index? The base class would hold all the data that would need to be accessed by any of the subclasses, the subclasses would only have an overloaded Update() function. Yeah, it'd be a bit slower because then the program would have to look at the vTable over and over again to figure out which Update() function to use and not all the data in the base class will be used by every subclass, but it sounds simpler and faster than having 100+ arrays, each with 100+ members, when a large portion of them aren't even being used at any given moment. Are there any downsides to my take on it? Am I missing an important concept of data locality? What is your take / what would you do?

Answer 1

Wouldn't it be simpler(and smarter) to just have arrays of the base class, then stick in the needed subclass at some index?

This doesn't work. Child classes are likely to be a larger size than the base class, since child classes usually add some new data members. If you have an array of a base class (which is, say 32 bytes in size) you can't fit a child class (which is larger than 32 bytes) in the array elements.

You'd have to store references to the object instances in the array (or pointers). Using references does not give you data locality since the actual instances still end up spread out over memory and iterating over the array requires you to do "pointer chasing" to actually access the data in each object.

You could make an array full of over-sized entries big enough to hold any child of the base, but then smaller base classes put into the array are spread out unnecessarily in memory. This means you retrieve less useful data in each cache line request and your overall memory access times suffer.

There are many options to avoid waste. One is to allow your array of components to be resizeable in some fashion. If you use a plain resizeable array, you'd want to store indices rather than direct pointers to the elements of the array. You could also use a chunked approach in which you allocate new pages of memory when the "array" grows and then keep an array of the pages making up the "array." This allows you to efficiently iterate over the elements of the container, more or less with the same efficiency as a completely contiguous array, but it allows you to grow the array without needing to copy/move all the elements whenever it does grow.