DOD and memory layout

Hi there, I'm trying to write a custom game engine for educational purpose. I read several presentations (on dice publications website and gamesfromwithin) on the subject of Data Oriented Design and I really like to manage the memory myself. I want a cache friendly game engine.

Basically, my game engine is split into two components: the Game Engine itself and the Game Framework. I will use custom allocators to manage the memory but that's not the point. Since I really love the Artemis entity framework and how logic and data are organized, I'd like to do something like this and I'm sure it can tied to the DOD concept. Lets say we have entities which have behaviours (only data) and push those data to a system(logic) with, given input data can produce output data and operate on contigous blocks of memory. So behaviours / data need to be contigous in memory so my question is, who is responsible for allocating memory for behaviours? A custom system, the system itself? And which custom allocator will be the best for such purpose?

Could you tell us what platform(s) your engine is targetting ? Remember that the kind of memory management discussed in those articles is basically beneficial to machines that have a low amount of memory (which is also slow memory) and limited cache memory. Alot of it applies to consoles or embeded systems (like cell phones). If your target is desktop PC, you will get little if any benefit at all.

As a general rule, the memory will be supplied by a linear allocator. This is an allocator that basically works as a stack. That means memory that have been allocated must be freed in the exact opposite order as the one used to allocate. To make this easier to use, DICE have designed a scope stak allocator My link that makes it easier to allocated contiguous memory and then release it when not needed.

It would help to have some snipets of code (even just pseudo code) to discuss the matter in more details. It's early here and i yet have to get some coffee

My engine targets PC first but must run on others platforms. I know this concept will be less crucial on desktop computer but still think it can help to make a more efficient code for parallelization purposes. My idea is basically to use DOD for all core specific jobs like rendering, animation, physics because it run on thousands of objects and need to be fast.

I use a stack allocator to allocate the core subsystems. For instance, when the core need to compute the world position for every objects, the memory layout will be important but the relation between two objects can change at runtime, a sword is picked by the player and its position is now relative to its parent (the player). So I need to be able to reorganize the memory, which allocator should I use?

Sorry for butting in without anything constructive to say...

But I thought the point of DOD was the speed _difference_ between cache and memory, much more then the amount of it you have. And isn't the speed difference pretty huge on a desktop PC too?

Possibly its just a little bit harder to trash the cache on a pc, but if you have a huge datastructure, you will anyhow, and will benefit greatly from being cache friendly.

And then even more if you want to parallellize.

Or am I wrong? :/

I think so Olof, it's all about access speed and CPU cache is still faster than RAM.

BTW, I tried several things to implement an entity system like artemis but DOD oriented and the point is, I am still stuck and don't know how do such a system. The idea is to be able, in an entity system, to loop through all relevant data by querying a central memory manager which return a pointer to the first element to process and a count. But since an entity system can have several component mappers, the memory layout is really hard to define.

For instance, in the Process() method of an entity system I want to be able to do something like this:

// MemoryMarker is just a struct like this
struct MemoryMarker
{
void* m_begin;
void* m_count;
// some getters and setters
};
MemoryMarker tm = ComponentMapper.Get<Transform>();
MemoryMarker rm = ComponentMapper.Get<Render>();
// tm.Count() or rm.Count() since they must process the same amount of entities
for(int i = 0; i < tm.Count(); tm++; rm++)
{
// Process job ! tm and rm points to the same entity components
}


I have something that should work but I worry about having to reorganize memory at runtime when an entity got some new component, etc..

Maybe someone can help me out

Sorry for butting in without anything constructive to say...

But I thought the point of DOD was the speed _difference_ between cache and memory, much more then the amount of it you have. And isn't the speed difference pretty huge on a desktop PC too?

Possibly its just a little bit harder to trash the cache on a pc, but if you have a huge datastructure, you will anyhow, and will benefit greatly from being cache friendly.

And then even more if you want to parallellize.

Or am I wrong? :/

It is about the difference in speed, and all platforms are affected, however, I would imagine that consoles suffer a greater impact for a few reasons -- firstly, they typically have much smaller amount of total cache, and second because the CPUs are simple, in-order cores (PS3, XBox 360) or just plain slow to begin with (Wii). The PS3 and 360 can switch to another thread cheaply and return when resources are ready, but if you stall two threads awaiting memory -- well, I'm not certain what happens, but it seems logical that you either wait, or load an external thread into one of the two contexts and hope it runs awhile. Ironically, the Wii's processor is probably the least-impacted by the rest of the system (They use 1T SRAM AFAIK, so while there is less of it, the memory system is rather fast compared to the Wii's CPU clock), but of course, the Wii runs at only 700ish Mhz to start off.

It also matters for the newest PC CPUs, see "CPU Caches and Why You Care" talk by Scott Meyers (links below).
OP, perhaps those materials will be helpful (and the links therein):
http://stackoverflow...ove-performance
[Video] http://scottmeyers.b...-available.html
[Slides] http://scottmeyers.b...accu-talks.html
http://aristeia.com/...odeCamp2010.pdf
http://igoro.com/arc...-cache-effects/

[quote name='Olof Hedman' timestamp='1325258802' post='4898165']
Sorry for butting in without anything constructive to say...

But I thought the point of DOD was the speed _difference_ between cache and memory, much more then the amount of it you have. And isn't the speed difference pretty huge on a desktop PC too?

It is about the difference in speed, and all platforms are affected, however, I would imagine that consoles suffer a greater impact for a few reasons -
[/quote]

My point was just that if the cache is say 100x faster on platform X, and just 10x faster on platform Y, I'd imagine you get a lot higher gain from being cache friendly on platform X, even if platform Y has much more cache/ram or is generally faster... I thought the problem with the insanely quick modern CPU:s is that the ram lagged behind and didn't increase in speed as fast.

What you say about the Wii fits nicely into this. The Ram is quick so you don't get as much benefit from being cache friendly.

Right, but its not always about the measurable clock-speed differences between CPU/Cache/Memory, or even the ratio of CPU MIPS to bandwidth. Simpler, in-order CPU cores like the PPC units in the Xbox360 and PS3, or Intel's Atom processors don't have the complex circuitry that their out-of-order brothers have which can keep the CPU busy while it awaits data. That's why they have the trick of having two thread contexts on-the chip -- it helps, and its simpler than OoO or hyperthreading, but if you go beyond those two contexts its essentially dead in the water until the memory reference can resolve, or a more-expensive context switch occurs.

Such a memory reference on a fast CPU might "miss" for tens or hundreds of instruction slots before it resolves, but if the CPU can keep 75% of those slots busy with other work, then the aggregate impact is less than on a slower CPU which "misses" half as many instruction slots, but can't fill any of them with other work.

I have something that should work but I worry about having to reorganize memory at runtime when an entity got some new component, etc..

Don't try to process one entity at a time.

Instead process types of components at a time; to use your example you would do all the transform components and then all the render ones.

This gives you the best chance at optimal instruction and data cache reuse while processing.

Your entities themselves only need to maintain some kind of handle to the componet to send any messages/commands they need (or not even that, you could have a completely decoupled system where by the entity stores 'id' values and sends messages via a message system to pass data a long).

The key point is not to think of an entity as being a thing you update, instead do batches of component types together.

This is what I'm trying to achieve. The entity is just here to know which component belongs to an entity. Transform Job, Render Job and so on should know nothing about entity but instead process only data. For this to work, data should be allocated carefully and that's my problem. There must be some rules when allocating data and I can't figure a way to solve this problem.

BTW, thanks @Matt-D for your links!

I have something that should work but I worry about having to reorganize memory at runtime when an entity got some new component, etc..

Maybe someone can help me out

It really depends on the scope of your game - if you have a static level allocated in a stack-like fashion, then you know exactly what you will need to allocate at loadtime. When writing out the file for a level, just write out all transform components at once, then all render components, etc. When reading a level, since all the render components are in the same place, they can be placed in a preallocated block of contiguous memory. You can have a "free store" for stuff like dynamically spawned particles and such. That will usually be enough.

If you are planning on a large amount of stuff created at runtime, or streaming a large level (thus creating a need for runtime allocations/deallocations), you can use a pool-type allocation strategy. Preallocate a block of memory enough for many transform components, then throw them all in there. When you run out, allocate more. Remember that it doesn't matter if data is contiguous across cache lines. If you have two cache lines worth of data, it doesn't matter as much if both are together in memory.

Thanks for your response. With a pool allocator in place, I will need another way to process data in my entity systems. Since in a pool allocator, as far as I know, order is not important. If I allocate all properties for one component into one block of memory and all properties for another component into another block of memory, when processing those data in my entity system, order matters (properties should appear in the same order) and that's the hard part. Maybe what I'm trying to achieve is completly crazy.

Each "pool" would be several megabytes in size, and so would contain hundreds of thousands of cache lines in contiguous memory. Allocation would look something like this

is there enough space in current pool for a new object?
yes:
construct object in pool using placement new
no:
allocate new pool, construct object in new pool using placement new

So yes, the blocks themselves would not be contiguous, but all the data in a single block would be.

Each component should be the same size, so you don't need to worry about fragmentation. A component manager would have its own list of pools that are a multiple of the size of the component they manage.

Agree, but how can I order my components to traverse them easily?

Well each component pool would basically be a
<Component Type>[Block size / sizeof(<Component Type>)] // array of <Component Type>
so you would just do an array traversal.

My main concern was based upon these presentation, slide 12, all data appear in the exact same order (L1, P1, W1 .. L3, P3, W3) and that's why it's very efficient. Same appear in the dice presentation but they did not talk about implementation details, especially when a system could process multiple types of components, for instance, a render system that needs to process all entities that have a render and a transform component since the world position of an entity should be in the transform component.

a system could process multiple types of components[/quote]

SIMD - single instruction multiple data. While distinct types can be used, they are undesirable.

If using multiple types, the simplest way is to have them stored in independent containers, then process each container using its specific function.

Often there are too many types used where they aren't really needed. Most, perhaps even all components can be expressed very few bags of primitive types.

Ok so this is where I am with my entity system.

Instead of having a class "Orc" , I have a struct "Orcs" defined like this, this is an example:

#define MAX_ORCS 50
struct Orcs
{
int posx[MAX_ORCS];
int posy[MAX_ORCS];
int speed[MAX_ORCS];

// Not entity properties
unsigned int count;
unsigned int Create() { ... }
};


And now, in my gameloop I call some processing functions like this:

void ComputePosition(int* x, int* y, int* speed, unsigned int count)
{
for(unsigned int i = 0; i < count; i++)
{
x += speed;
y += speed;
}
}
void main(int argc, char* argv[])
{
Orcs allOrcs = Orcs();
// Create some orcs
allOrcs.Create();
[...]
while(true)
{
// Other processing functions
ComputePosition(allOrcs.posx, allOrcs.posy, allOrcs.speed, allOrcs.count);
}
return 0;
}


This is a very basic example. Is this data oriented? It is already faster than a traditionnal oo approach but I have to call the processing function for each set of entities.

What you're doing there is counter-productive. Each time you update an orc, you need all three bits of data (posx, posy, and speed), so it doesn't make sense to split the three up in memory.

Like those bitsquid slides say, the method behind DOD is "isolate tasks, find data objects". In this case, "update position" is the task and position and speed are the data that the task needs. Hence they should be together - they are one data object.

Another task would be "generate a list of all visible orcs", which would need position and bounding data.

A third would be "draw all visible orcs", which would need position and model / texture data.

Position is needed by all three tasks. This means you have to either separate position out (as one struct that holds both x and y pos) or have multiple copies of position, which you then update from a "master" position. The better choice depends on specifics of the game you are making. A large, static environment (such as skyrim) would benefit from multiple copies of position, because a change in position would happen relatively infrequently and to few objects, but the benefit of cache consistency would help every single frame.