Sign in to follow this  

Data Flow Between Systems

This topic is 831 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

 

I was recently watching Mike Acton's talk at the CPP Con, regarding "Data Oriented Design", and I've been thinking a lot about how I might be able to structure my game code to better take advantage of cache coherency.  The ideal here would be that all major processing is done on contiguous arrays of data, directly in-order.

 

But I've been struggling on one particular aspect of this: the problem is that the ordering requirement between various systems is not the same.  For example, suppose I have a typical flow of data: I have high-level behavior that updates positions/rotations, which then needs to be transformed by collision and collision response, and then converted into matrix transforms for draw calls.  There are distinct ordering requirements for each step here: behavior will want data grouped by type, collision will want it grouped by spatial locality, and rendering will want it grouped by draw order/material/etc.  Beyond that, these requirements will change as the state of my game changes ( not referring to static objects here ).

 

This means that I cannot simply set up fixed arrays and run my processing in the same order across the board.  Somehow, I have to convert between the different orderings as I go.  Specifically I am considering the efficiency of the reads from the source, the writes to the destination, and then the reads at the destination.  I have thought of three possibilities to do this:

 

 

Maintain the data in linked lists per-system

 

- This is what I have done for many years to solve this problem.  It is easy to use, and there is no major processing required to maintain ordering.  But the issue is, you end up iterating ( reads at the destination ) out of order, and you have all the node values filling up your cache.

 

 

Use linked lists for indexing and copy to arrays per-system

 

- I have just recently tried this out.  The iteration at the destination is noticeably faster, but the copy ( writes to the destination ) is now out of order and takes longer.  Overall, it has been only a minor speed boost for me.

 

 

Copy to arrays directly and sort per-system

 

- I have not tried this out yet, but I intend to.  Theoretically this could have the least amount of cache misses as everything is done in order.  It's hard to believe that the cost of running the sort algorithm would not outweigh the gains, but I'll have to test that.

 

 

Does anybody else out there have solutions that I am not thinking of?  I'd be greatly interested to know how people tackle this kind of problem.

 

Thanks for reading!

Share this post


Link to post
Share on other sites

The only approaches I can think of is to either duplicate the data to support multiple orderings (only the data you need to duplicate, since this is already expensive enough), or only optimize the ordering for the system where it matters the most (the rest can do indirect access).

 

I would think that most of the time there is just one system that is the bottleneck, so it should be enough to optimize for that system. Duplication has a lot of overhead (both RAM and CPU) so I would avoid that if its not strictly necessary.

 

If you do maintain multiple orderings, make sure to take advantage of temporal coherency in the order by choosing the correct sorting algorithm. The order is likely to be similar or even exactly the same as in the last frame, so dont throw that data away, and use an algorithm that has good complexity if data is already sorted (I think bubble sort had this property, even though it sucks with unsorted data).

Share this post


Link to post
Share on other sites

Thanks guys,

 

I am going with the assumption that I should duplicate the data, for the reasons you describe Sean.  But my problem is the data needs to be in different orders for different systems, so when I duplicate it I end up having to jump all over memory to reorder it ( it's never a linear memcpy ).  I think that's probably inevitable, and I am trying to consider the best way to do it.

 

@Waterlimon - That's an interesting thought, regarding keeping it sorted over multiple frames.  However, although it's true that the order is unlikely to change, the data itself almost certainly will ( assuming these are all dynamic objects ), so I still need to re-write data into the sorted "slots" each frame.  I can cache the sorted index to avoid running the algorithm, but that's almost identical to the second method I was discussing ( which never actually entails a sort ).  Unless I am misunderstanding your suggestion?

Share this post


Link to post
Share on other sites

There are distinct ordering requirements for each step here: behavior will want data grouped by type, collision will want it grouped by spatial locality, and rendering will want it grouped by draw order/material/etc.

Behaviour produces a list of (rigidBodyID, forceVector) pairs.
Physics consumes those, perhaps sorting them in place before applying those forces to the requested bodies. It then does position/velocity/acceleration updates it its own internal order, along with collision/etc.
Physics then produces an array of pairs of (renderableID,transformMatrix) pairs.
The rendering system then consumes that data to -
A) update the positions of it's bounding volumes for culling, and
B) streams them into cbuffers for use by the GPU.
The rendering system can then frustum cull it's bounding volumes, and use the resulting visibility data to get an array of visible objects.
It can then sort that array into material/etc order and submit draw-calls -- n.b. this step only needs to consume cbuffer ID's, not the transforms.

Share this post


Link to post
Share on other sites

This topic is 831 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this