Sunday, December 6, 2009

Optimization II - When the difference between struct and class saves you

So, I'm still on an optimization kick. Map generation is still taking way too long, maps take too much memory. I figured I'd share this story, since it wasn't what I expected.

So, I want the ability to have large levels, even if I don't use them. Say, 250x250, and maybe 50 levels total. My original data structure looked like:

class Map
     private MapTile[,] m_map;

class MapTile
   enum terrianType;
   bool visited;
   int scratch; //Use in map generation algorithsms.

There are two major issues with this, naive set of data structures. The first is that we have an array of classes. In c#, this means we really have an array of references. It looks something like this poor graphic.

This is a bit wasteful in my case, as it added 4 bytes (on 32-bit machines) for every map tile. 250 (tiles) x 250 (tiles) x 50 (levels) x 4 bytes = Around 12.5 megs. So switching to structs (which are stored inline) makes sense.

The second issue was the data types for the MapTiles. Ignoring padding, each maptile is (4 bytes (Enum) + bool (1 byte) + int (4 bytes)) 9 bytes large.

In c#, you can set the underlying type for enums. Since there will never be more that 255 terrain types, I switched that to a byte. The scratch value also never needed more than 255 types, so to byte that went as well. My final size is 3 bytes.

For each of these changes I measured speed and memory usages before and after and compared. This way, I could make sure things like structure padding and such wouldn't ruin my day and make things take the same amount of space anyway. I won't share the numbers, out of embarrassment of how much memory was being uses, but let's just say I use a much more reasonable amount now.


Claes Mogren said...

Could you just post in general terms what the difference was? Like 10mb for classes and 7 for structs, or was it more like 10 to 1?

donblas said...

For example, my "worse case" scenario is 250x250 floor, with 50 of them for the entire dungeon. That was nearly 60 megs before any optimizations. The array of pointers was 16 megs in itself.
After optimizations, the same 50 levels, 250x250 is 8.9 megs.

That's not including the world generation, which I trimmed a bunch off of as well.

The Destroyer of Worlds said...

I've been reading your blog for a while and find it both entertaining and insightful. Thanks for sharing your thoughts and updates!

Just a thought regarding this post, and your latest post where you found that a dictionary of classes is better than a dictionary of structs. Its a helpful observations and I'll be thoughtful of this.

I am wondering why you are keeping this information as structs and classes in the first place. Wouldn't a three dimensional array be the most compact representation? Add a separate set of collections to account for sparse data such as monsters and items.
I am unsure there is anything to be gained from making individual map tiles into objects or structs for storage purposes- that's not what they were designed for.
Since one of the original purposes of OO programming is to separate logic from data, your map object could keep a very hard-coded, optimized data version internally, but expose that data as objects to external frameworks for logic purposes. And the map objects should probably be able to do most of the logic internally, such that your non-map logic would rarely get a tile back anyway, but rather a boolean CanMoveHere or int DistanceToHere or somesuch.

This way, you could do extreme forms of compression without the rest of your game knowing it. For instance, if your dungeon is quite sparse, then inside your map object, you could encode the world as a series of sections, each section described by its own optimized array. When you enter a level, you would access the sections and re-generate a flat, sparse map for performance reasons. With extra cleverness you could add malleable terrain such as tunnels through dynamic creation of new sections.

The point being, use objects to represent game logic, not data structures.

donblas said...

That is an interesting thought Destroyer, one I haven't thought about. Pushing all of my IMapTile methods onto IMap and removing the fact that it is a two dimensional array. I'll have to think more about that.