3
\$\begingroup\$

I am making a game server and currently I am experiencing a huge performance hit.

I have a class Map which holds a Dictionary of the class Tile with each tile having X, Y, and Z coords, some lists, etc. nothing fancy as it's a MMORPG.

Currently in the Map class I have this:

public Tile GetTile(Coordinate_t coordinate)
{
    if (Tiles.ContainsKey(coordinate))
    {
        return Tiles[coordinate];
    }
    return null;
}

Coordinate_t is a struct containing X, Y and Z as UInt32. the Dictionary is represented like this:

 Dictionary<Coordinate_t, Tile> Tiles;

Basically I need to hold over 7 million tiles in this list, but it's being really slow! Every time I try to get around 12 tiles in a function it increases the program CPU use to 1~3% which is a lot! Since the game server is supposed to hold over 100 players online at a time.

Any ideas why is it being so slow? Are there better ways to hold a huge amount of tiles of a game in a list to be accessed continuously without having such a huge performance hit?

\$\endgroup\$
2
  • \$\begingroup\$ Shouldnt you have tagged this as C# instead of C++? \$\endgroup\$
    – user35344
    Commented Oct 14, 2014 at 6:52
  • 4
    \$\begingroup\$ Any specific reason you're not just using a three dimensional array for this? \$\endgroup\$
    – Mario
    Commented Oct 14, 2014 at 7:24

2 Answers 2

7
\$\begingroup\$

When you have a 3-dimensional world and you say you have 7 million tiles, I would assume that your game world is a cube of roughly 200x200x200 tiles.

Instead of storing this in a hash table (Dictionary) you could also store it in a three-dimensional array. Arrays have much less overhead and much more predictable performance characteristics than hash tables.

However, arrays are only a good solution when the size of your data doesn't change. When you want the world to be able to grow dynamically during the game (like in Minecraft where new world data is randomly generated while the player explores), you need to resize the array every time the world grows, which is always a very expensive operation. Also, when you have a sparse world with large empty spaces, an array can be very wasteful because you also need to allocate memory for these areas while more dynamic data structures allow to just have no entry for these tiles.

When this is the case, a Dictionary might be the better choice after all.

When you use a Dictionary, you need to be aware that it is very important that you override the public int GetHashCode() method of the objects you store in it in a way that most objects return an unique value. Any objects which return the same value will be stored as a linked list under that key which then needs to be iterated one by one. Considering that your Coordinate_t seems to be a set of 3 integers between 0 and 255 (8 bit), you could in fact fit the whole coordinate into the 32bit integer to ensure that each coordinate returns an unique hash code.

public override int GetHashCode() {
    return x + y << 8 + z << 16;
}

The binary representation of the hash-code of each coordinate-triplet will then be:

 00000000zzzzzzzzyyyyyyyyxxxxxxxx
\$\endgroup\$
2
  • \$\begingroup\$ Indeed I don't need to re size my tiles array as the map is loaded from the map file the user creates within the map editor so the map size is always the same value! Using arrays Tile[,,] Tiles = new Tile[mapSizeX,MapSizeY,15]; is the way I use it on a live server. Thank you for this, this is right what I was looking for. \$\endgroup\$ Commented Oct 14, 2014 at 8:57
  • \$\begingroup\$ If you have a large world that you can load in parts then it can be beneficial to split it up into chunks and use a dictionary on the world level and a array on the chunk level to find the cells. \$\endgroup\$ Commented Oct 14, 2014 at 15:52
3
\$\begingroup\$

Try changing your GetHashCode to something that better distributes the values to reduce the number of collisions in the dictionary.

If your hash code is bad you're going to get the performance of a list rather than a hash-set. To show this consider a GetHashCode method that always returns 0 for any object.

Trying to put that into a Dictionary will force the dictionary to put all the items into the same bucket (http://en.wikipedia.org/wiki/Hash_table#Hashing), yielding linear search time rather than close to random access time for a perfect hash.

The math behind a clever hash is beyond me, for integer only structs I usually use something similar to the example below.

Consider this implementation of your Coordinate_t struct;

struct Coordinate_t
{
    int x, y, z; 
    public Coordinate_t(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public override int GetHashCode() {
        uint h = 0x811c9dc5;
        h = (h ^ (uint)x) * 0x01000193;
        h = (h ^ (uint)y) * 0x01000193;
        h = (h ^ (uint)z) * 0x01000193;
        return (int)h;
    }
}

If you comment out the GetHashCode you'll see a massive change in performance when using a dictionary.

Test application

struct Coordinate_t {
    int x, y, z; 
    public Coordinate_t(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    // Uncomment this to make it go faster
    //public override int GetHashCode() {
    //    uint h = 0x811c9dc5;
    //    h = (h ^ (uint)x) * 0x01000193;
    //    h = (h ^ (uint)y) * 0x01000193;
    //    h = (h ^ (uint)z) * 0x01000193;

    //   return (int)h;
    //}
}

class Program {
    static void Main(string[] args) {
        var tiles = new Dictionary<Coordinate_t, string>();
        var sw = new Stopwatch();
        sw.Start();
        const int count = 100;
        for (var x = 0; x < count; ++x)
            for (var y = 0; y < count; ++y)
                for (var z = 0; z < count; ++z)
                    tiles[new Coordinate_t(x, y, z)] = String.Format("{0}.{1}.{2}", x, y, z);
        sw.Stop();
        Console.WriteLine("Add took {0}", sw.Elapsed);
        sw.Reset();
        sw.Start();
        for (var x = 0; x < count; ++x)
            for (var y = 0; y < count; ++y)
                for (var z = 0; z < count; ++z)
                {
                    var expected = String.Format("{0}.{1}.{2}", x, y, z);
                    if (tiles[new Coordinate_t(x, y, z)] != expected)
                    {
                        throw new Exception("Something is super-broken!");
                    }
                }

        sw.Stop();
        Console.WriteLine("Get took {0}", sw.Elapsed);
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Fair point. I elaborated a bit. \$\endgroup\$
    – bornander
    Commented Oct 14, 2014 at 8:00
  • \$\begingroup\$ This was a very interesting answer I didn't know there was hash within dictionary items and that there was a way to optimize it, but instead I just needed to use arrays since I won't need to dynamically re size the array, I guess I should of said it. But thank you for your thoughtful answer! \$\endgroup\$ Commented Oct 14, 2014 at 8:59
  • \$\begingroup\$ Arrays will be faster but you will (if you have a lot of "empty" tiles) take the hit on memory consumption instead. If you know memory won't be an issue, use arrays. If I was you I'd still look into a sparse array implementation if you have many empty tiles, en.wikipedia.org/wiki/Sparse_array. \$\endgroup\$
    – bornander
    Commented Oct 14, 2014 at 9:23
  • \$\begingroup\$ @bornader A Dictionary<int, Whatever> is a common implementation of a sparse array. Doing it as a linked list like in the Wikipedia article would be counter-productive in this case because index-access would be slow. \$\endgroup\$
    – Philipp
    Commented Oct 14, 2014 at 13:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .