Class vs Struct - It actually can matter

So, the second of my optimization realizations today involves the difference between structs and classes. For those who've been with this blog for awhile, you might remember a post I made half a year ago, here. In that post, I realized that a list of structs uses a lot less memory than a list of classes when each item is crazy small and there are a huge number of them.

Today, I've ran into the inverse. I made Point a struct back when I made that realization, thinking that it was small and therefore memory savings were worth the savings. However, when you stick an item into a dictionary as a key, it apparently makes a copy if it is a struct. It also makes a copy if you query the dictionary with a struct as the key. This meant I could rack up half a million or more point copies by scrolling for 15 seconds in my skill tree. This caused the memory manager to go crazy, and introduce the lag I was seeing. Switching it to a class helped a bunch.

When should you use struct vs when should you use class? Here's my current huristic:

If the item is large or you won't be having a crazy huge number of them - Use class, the possible optimization isn't worth it.
If a large number of the items will be stored in memory in a list - Try struct, as you'll save a pointer sized (4 or 8 bytes) amount for each item.
If you will be using it as a key (or value to a lesser extent) in a dictionary - Use a class, as each query on the dictionary and every access will make a copy.

Optimizations are great, but sometimes it helps not to be an idiot...

So, if you've been following my progress on magecrawl, you'll remember my article on optimization trying to cut down on memory usage and map generation time. If not, here and here.

Well, I did a bit of programming this morning before work, and on the way driving to work I had one of those "Wait a second..." moments. Here's the guilty section of code:

private void GenerateMapFromGraph(MapNode current, Map map, Point seam, ParenthoodChain parentChain)
       {
            if (current.Generated)
                return;

            current.Generated = true;
            bool placed = false;

            System.Console.WriteLine(string.Format("Generating {0} - {1}", current.Type.ToString(), current.UniqueID.ToString()));

It's that last line that got me. It was some debugging code that I forgot to remove. This function gets called recursively during map generation, a huge number of times and writing to stdout is very slow.

Some baseline numbers (release mode attached to debugger) in generating 100 maps gives me:

• Before - 47473ms
• After - 1041ms

Yeah, only a 45x speedup. While all the other optimizations were great, and needed due to memory usage, this appears to be the root cause of my performance issues.

The lesson for today, next time performance is terrible, check stdout to make sure you aren't dumping 10000 lines of text to it during map generation.

Update: Now I just need to find some crazy optimization for my cave map generator and I can get rid of my "loading" screen, since I can generate 100 of the stitch levels in about a second.

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;
     ..more..
}

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.

Optimization - Or when your application eats up 150+ megs of memory generating maps...

So, yesterday I finished stairways and generation of multiple level maps. It's somewhat boring, but it works. I turned the map generator up to generator 5 levels and built a release build, to get an idea of performance. There was a second pause before the game started, a bit more than I'd like to see. I turned it up to 50 maps, and ran into a 30 second pause that the task manager claimed ate up 150 megs of ram.

Now before you get out pitchforks and tell me that all the managed code stuff I talked about in the previous article is the cause of it, I want to make two quick points.

• Much of that memory would be reclaimed the minute another program asked for it, since it was a lot of garbage the garbage collected was waiting for next collection on.
• The mistakes I made would have been just as slow in C++, RAII would have reclaimed the memory right away (good), but all the allocations I made would have been just as slow (bad).

I won't bore you with the normal two or three quotes about premature optimization and difficulty in predicting where to optimize, you have already heard them before. What I will say is that every time I run into performance, every single time the cause is not where I'd guess.

A month ago when I was just starting the map generator, I was seeing poor performance moving around. I figured it had to be in my game engine somewhere, maybe in the other actors movement. It turned out to be a part of the GUI that was walking every single tile in my map to draw, even if off screen. Since it was in my GUI loop, just the act of walking all the tiles didn't scale to 200x200 sized maps.

To get back at the story at hand, I figured the way I was generating maps was too slow, that I'd need to rip it out and start over. I made the decision to measure my performance and see what was slow. I'd like to tangent to point out the CLR Profiler and EQATEC Profiler, which are free and awesome. So, it turned out that the subroutine that placed chests and monsters was taking 55% of the entire generation time, and using a crazy amount of memory.

The way the chest and monster placement works for my cave generator is simple: from the generated map, get a clear point that isn't too close to the stairs and use it. Repeat for number of chests and monsters. The problem was in the get a clear point. My naive algorithms walked the entire map and created a list of free points. Then it randomized it, and started grabbing from the front of the list until it found one wasn't too close. I figured it'd be more effective than randomly generating points and checking them in maps with a small percentage of empty tiles. You might see the problem here already, I'm walked all the tiles to painstakingly generate a list, randomize it, and then throw it away when done. When you do this 20+ times per level, then 50 levels in a row, it adds up.

Once I cached the list, the generation time dropped in half, and so did memory. I found another similar issue in the core map generator, see here for details. I'm tracking one more down in the stitch map generator right now.

The "lesson" from this story, if there is one, is that I would have never guessed that GetClearPoint was the culprit. A lot of people claim they want fast code, and might try to optimize where they think it's going to be slow, and do nothing but add bugs and obscure coding constructs. Write the simplest code first (with reason, no bubble sorts), then measure and see what's slowing you down. Once you know that, you can whip out the black magic optimizations there.