Sign in to follow this  
SeraphLance

Ideal Memory Layout For In-Game Assets?

Recommended Posts

So this is mostly a theoretical question, as my current solution is "dynamically allocate everything on load and store void pointers", which is obviously subpar in every respect.  Either way I need to do something.  The only question is what.

 

I've been thinking about how to store resources I load in my game.  I've got two competing ideas in my head, but I'm sure there are more:

 

1.  Allocate by scene:  I could create a special file format with all the scene data zipped up and a header that contains pertinent information (like uncompressed scene size).  With this, I can load the entire file whenever I need a scene and block-allocate everything together.  Unloading the scene would be easy -- just free the whole buffer.  This has the benefit of being nice and compact, and I could mitigate a lot of load time by just prefetching scenes as the player goes through the game, which is great.  On the other hand, it means all my data is grouped by scene, so linear traversals of things (like, say, for rendering) would be less than optimal, to put it nicely.

 

2.  Allocate by type:  Reserve a bunch of buffers for each type of resource I need and bucket on that.  This has the benefit of leaving all of my data contiguous for fast traversal, but makes in-place sorting or deleting things impossible without index invalidation or some kind of lookup table (which defeats the purpose of making stuff contiguous in the first place).  It's also wasteful since each buffer has to be as large as you could possibly fill, even if they're not taken simultaneously.

 

I'd like the benefits of both, honestly, but I know that's impossible.  What do other games do?  A mix and match of the two?  Something more fine-grained, like a flag parameter telling where to put the data?  I know of other allocators like memory pools, but I'm less sure how they're applied.

 

Are there any good resources for this sort of thing?  The only thing I've seen to even touch on it is this book, but even that basically just touches on the different types of allocators out there.

 

Share this post


Link to post
Share on other sites

dynamically allocate everything on load and store void pointers
The most common solution to deserializing any complex structure would be that, except using real pointers instead of void. Not sure why you suggest throwing away type safety.

So there's always #3 too - Just allocate with new instead of from some pool :D

On the other hand, it means all my data is grouped by scene, so linear traversals of things (like, say, for rendering) would be less than optimal
As long as "a scene" is large this doesn't really matter. Two linear traversals over two big data sets is just as good as one linear traversal over a single doubly-big data set... Two traversals can actually be better than one, if they're done by two threads :wink:

 

Some notes on #1 --

If you have a scene format like that, which can just be loaded straight into memory, you can use byte-offsets in place of pointers within your data structures. You can write a C++ template class that implements the -> operator for these types, so at runtime you can use them as if they actually were real pointers, without ever having to do a deserialization pass :)

If the scene owns a linear allocator / stack allocator, then you can just allocate many different objects from it, and they'll end up being in one big contiguous lump. However, if the scene data is, say, 1MB in size, then the fact that it's all contiguous doesn't really matter if two different objects that are accessed at similar points in time are at different locations within that 1MB block...

Back in the PS2/Wii days I'd seen quite a few 'adventure' games work by defining the maximum memory size of a single scene. They'd then pre-allocate three scene-sized chunks. Two scenes would be loaded and active at a time (so you could walk from one to the next without a loading screen), and a third scene would be streamed in and deserialized in the background while you were playing. There was also usually a 4th 'permanent' scene that contained things like the pause menu and the main character (things that always needed to be loaded). These scene chunks were just stack allocators - as the various scene loading systems required memory, they just incremented that pointer. Deleting a scene just reset that pointer back to the start of the chunk.

Share this post


Link to post
Share on other sites
The most common solution to deserializing any complex structure would be that, except using real pointers instead of void. Not sure why you suggest throwing away type safety.

Well, currently, I have one big array of void pointers and reference them by index.  They're void pointers because the data is heterogenous.  It was never intended to be a long-term solution, just a stopgap while I got the implementation of the rest of the resource system ironed out (like the loading code and thread management stuff). 

As long as "a scene" is large this doesn't really matter. Two linear traversals over two big data sets is just as good as one linear traversal over a single doubly-big data set... Two traversals can actually be better than one, if they're done by two threads

I'm not sure I follow this.  If I load by scene my buffer will look something like (butchered BNF):

scene:=[texture|texture|texture|...|sound|sound|sound|...|model|model|model...] 
resource_memory:=[<scene>], [<scene>], [<scene>], ... [<global stuff>]

If I wanted to traverse say... models to render, I have to traverse at least two separate arrays.  for both global stuff and the individual scene.  On the other hand, if I bucket by type, it looks like this:
textures:=[texture|texture|texture|...|texture]

models:=[model|model|model|...|model]

<etc>

 

With that I can traverse the entire thing very quickly, or I can break it up into arbitrary parallel traversals by just subdividing the array.

If you have a scene format like that, which can just be loaded straight into memory, you can use byte-offsets in place of pointers within your data structures. You can write a C++ template class that implements the -> operator for these types, so at runtime you can use them as if they actually were real pointers, without ever having to do a deserialization pass

My understanding is that it's faster to load compressed data on disk and decompress at runtime than it is to read the decompressed data off the disk.  I don't actually know if that's true, but it seems a common practice.  I'm sure to some degree it depends on the format in question; you obviously wouldn't get much benefit from compressing dds textures for example.

Nevermind, I see what you're getting at.  Yeah, that would be nice.  Most of the assets I actually use in practice are trivial to deserialize though (except shaders, but I'm not even sure if those are safe to store as bytecode).

Back in the PS2/Wii days I'd seen quite a few 'adventure' games work by defining the maximum memory size of a single scene. They'd then pre-allocate three scene-sized chunks. Two scenes would be loaded and active at a time (so you could walk from one to the next without a loading screen), and a third scene would be streamed in and deserialized in the background while you were playing. There was also usually a 4th 'permanent' scene that contained things like the pause menu and the main character (things that always needed to be loaded). These scene chunks were just stack allocators - as the various scene loading systems required memory, they just incremented that pointer. Deleting a scene just reset that pointer back to the start of the chunk.

That's actually almost exactly what I envisioned for #1, though I had planned on having fixed-size blocks for the off-disk memory allocation, and a stack for scene temporaries. 

Edited by SeraphLance

Share this post


Link to post
Share on other sites

There are an enormous number of ways to handle serialization, and there are hundreds (possibly thousands) of books and websites on the subject.

Solutions range from simple 'flat files' on the direct approach, to data that has been carefully formatted for direct memory mapping from disk for instant use. In between there are various formatting techniques, hierarchical structures, four character codes, name/value pairs, and assorted other objects.  Usually the more powerful and faster options require more engineering work, although many people forget that a direct linear processing of a flat file is rather speedy.

Fixed-size blocks, memory pools, pointers that get re-aligned based on type and placed in the proper location, and assorted other techniques are all valid approaches. 

 

The biggest gotcha for what you've described with void pointers is the problem of data alignment. Void pointers are not particularly aligned, and some data types have specific requirements of 2-byte, 4-byte, 8-byte, 16-byte, and other alignment positions. 

Share this post


Link to post
Share on other sites

So this is mostly a theoretical question, as my current solution is "dynamically allocate everything on load and store void pointers", which is obviously subpar in every respect.  Either way I need to do something.  The only question is what.

 

I've been thinking about how to store resources I load in my game.  I've got two competing ideas in my head, but I'm sure there are more:

 

1.  Allocate by scene:  I could create a special file format with all the scene data zipped up and a header that contains pertinent information (like uncompressed scene size).  With this, I can load the entire file whenever I need a scene and block-allocate everything together.  Unloading the scene would be easy -- just free the whole buffer.  This has the benefit of being nice and compact, and I could mitigate a lot of load time by just prefetching scenes as the player goes through the game, which is great.  On the other hand, it means all my data is grouped by scene, so linear traversals of things (like, say, for rendering) would be less than optimal, to put it nicely.

 

2.  Allocate by type:  Reserve a bunch of buffers for each type of resource I need and bucket on that.  This has the benefit of leaving all of my data contiguous for fast traversal, but makes in-place sorting or deleting things impossible without index invalidation or some kind of lookup table (which defeats the purpose of making stuff contiguous in the first place).  It's also wasteful since each buffer has to be as large as you could possibly fill, even if they're not taken simultaneously.

 

I'd like the benefits of both, honestly, but I know that's impossible.  What do other games do?  A mix and match of the two?  Something more fine-grained, like a flag parameter telling where to put the data?  I know of other allocators like memory pools, but I'm less sure how they're applied.

 

Are there any good resources for this sort of thing?  The only thing I've seen to even touch on it is this book, but even that basically just touches on the different types of allocators out there.

Dynamically allocating everything is not necessairly a bad thing, if you mean you are asking the OS for your data. The process is slow, but it is not -that slow-. And it is not likely going to be the area of your bottle necks so soon.

 

In most circumstances, the biggest reason you'd avoid dynamic allocation are going to be for a few things.

When you have thousands of a little single but small type. So you convert it into one big allocation and reuse the memory slots that they currently take up. This is called pooling. Many small allocations at once tend to be horridly slow.

When you have a very small amount of memory. I don't believe an OS will typically try to defrag your memory on an embedded system. So you could potentially only have two gigs to use and that's shared between the GPU and the CPU. Fragmenting your memory will only leave small clumps of free space available that becomes unusable due to it being so small.

 

Or when you will be constantly allocating and deallocating in real time.Then obviously you will need to take some steps to not only speed this up, but to also keep track of your memory usage.

Edited by Tangletail

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