Sign in to follow this  
bronxbomber92

Unity Data Oriented Design Question

Recommended Posts

I was looking through an old thread on DOD and I came across this post by Hodgman: http://www.gamedev.net/community/forums/topic.asp?topic_id=575076&whichpage=2�

Looking at his code, I see this:


ParticleLifeData& life = lifeData[i];
ParticleLocation& pos = location[i];



and


ParticleLocation& pos = location[i];
ParticleMaterial& mat = material[i];



In both instances, each lookup into lifeData, location, or material will cause a catch miss, won't it? Assuming a 64 kb cache line, if the index into lifeData causes a cache miss, then lifeData[i], lifeData[i + 1], lifeData[i + 2], lifeData[i + 3], lifeData[i + 4], lifeData[i + 5], lifeData[i + 6], lifeData[i + 7] will be loaded into a cache line. But when locations is indexed, won't that cause another cache miss since the cache was either just filled or was all ready loaded with some block of lifeData? If this is the case, would it make more sense to pair either lifeData and location into one structure, or pair location and material into one structure so that the cache miss can be eliminated in one of the cases? Or, is there no cache miss because lifeData, location and material will each be loaded into separate cache lines? If this is the case, then how does the CPU know which cache line should be used when a cache miss is incurred (ie say material[i] causes a cache miss, how does the cpu know not to use the cache line that location[i] is loaded into; is it able to tell which cache line contains the "oldest" memory [ie, last touched]?)?

Share this post


Link to post
Share on other sites
Quote:
Original post by bronxbomber92
is there no cache miss because lifeData, location and material will each be loaded into separate cache lines?
Yes (hopefully, most of the time - see associativity below).
Quote:
But when locations is indexed [after indexing lifeData], won't that cause another cache miss since the cache was either just filled or was all ready loaded with some block of lifeData?
No, the cache is made up of many lines. Hopefully each array will end up in different parts of the cache.
Quote:
In both instances, each lookup into lifeData, location, or material will cause a catch miss, won't it? Assuming a 64 kb cache line, if the index into lifeData causes a cache miss, then lifeData[i], lifeData[i + 1], lifeData[i + 2], lifeData[i + 3], lifeData[i + 4], lifeData[i + 5], lifeData[i + 6], lifeData[i + 7] will be loaded into a cache line.
If [i+0] to [i+7] are all loaded into a cache line, then you definitely won't get a cache miss when accessing those 8 elements. You might get a cache-miss when accessing [i+8], however, the CPU has a prediction unit which will hopefully realise that you're traversing an array, and it will also fetch the next cache line from RAM in advance!
If not, you can issue your own prefetch instructions to do this (grab cache lines that you'll need soon, to avoid cache misses) - although, it's hard to do this right without the help of an expensive profiler ;)
Quote:
If this is the case, would it make more sense to pair either lifeData and location into one structure, or pair location and material into one structure so that the cache miss can be eliminated in one of the cases?
The reason that the particle data was broken into 3 structures in that thread (Life, Location and Material) was because different algorithms used different sub-sets of the total data.

Update only needed Life and Location data, while Render only needed Location and Material data.

So, by breaking it up into 3 structures, we're preventing Update from loading Material data into the cache for no reason, and preventing Render from loading Life data into the cache for no reason.
Quote:
how does the CPU know which cache line should be used when a cache miss is incurred (ie say material[i] causes a cache miss, how does the cpu know not to use the cache line that location[i] is loaded into; is it able to tell which cache line contains the "oldest" memory [ie, last touched]?)?
Different CPUs use different algorithms. The way that a large amount of RAM is mapped into a small amount of cache is called cache associativity.

Share this post


Link to post
Share on other sites
Thank you Hodgman! For some reason I was under the impression that there was only one cache line. The design of the program definitely makes much more sense knowing each array will most likely end up in different cache lines.

Share this post


Link to post
Share on other sites

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  

  • Announcements

  • Forum Statistics

    • Total Topics
      628320
    • Total Posts
      2982072
  • Similar Content

    • By abarnes
      Hello!
      I am a game development student in my second year of a three year program and I would like to start building my portfolio. I was thinking of creating some games to show what I can do to potential employers since I wont have any work related experience when I graduate. But as I'm sure you all know there are tons of ways to approach developing/designing a game and I'm curious if anyone had any insight as to any "standards" that come with this? Is it okay to use game engines like Unity, Unreal, Game Maker etc? Or would it be better to make a game from scratch to better show case your skills? Any and all advice will be greatly appreciated!
    • By Hilster
      Hello 2D Artists,
      I've started making a 2D Puzzle Adventure game for mobile and I'm looking for someone who would want in on creating assets for the game. The core of the programming is pretty much complete, you can walk within the grid laid out and push boxes, when there is an object on top of a pressure pad it will activate the linked objects or if there is one object with multiple linked pressure pads it requires you to activate all points for the object to become active. 

      The level iteration for the game is quick and simple, a Photoshop file that is made of individual pixels that represents objects is put into the game and it creates the level out of those pixels with the assigned objects.
      The objects that need sprites created so far is the character, box, pressure pad, door, trap door, the walls, the stairs and the tiled background.
      I intend to add more objects so the amount I'd like to add will be extended.
      My motivations for posting here is to have something that looks nice to be able to display on my portfolio, so if you're looking for a working game that you can place your art into and improve the look of your portfolio then we're in business.
      Please reply with a few past examples of your art below and I'll be in touch!
    • By thefollower
      Hi
      I have set up my TcpClient to connect to my server and that works fine. But i am a bit confused how i read messages from the network stream with it continuously running via async, without ever closing the connection ?
      My TcpClient Manager class has:
       
      public async Task<bool> Connect(string address, int port) { try { await _tcpClient.ConnectAsync(address, port); IsConnected = true; return true; } catch(Exception e) { Debug.Log(e); return false; } } public async Task<int> Read(byte[] readBuffer) { if (!IsConnected) return -1; using (var networkStream = _tcpClient.GetStream()) { try { var bytesRead = await networkStream.ReadAsync(readBuffer, 0, readBuffer.Length); return bytesRead; } catch (Exception e) { Debug.Log(e); IsConnected = false; return -1; } } }  
      So i thought to just run a co-routine and call Read constantly to get the most recent message, but that doesn't make much sense to me since a co-routine would be blocked with the await. How is this actually done? The MS Docs don't have very good Async examples with the TcpClient class so i don't know fully get how to keep calling Read correctly.
  • Popular Now