Multidimensional array vs dictionary performance

Question

I am needing to do a lookup on a large bool set using x,y,z coordinates(integers only). I am trying to determine if a block is traversable at x,y,z location.

Currently I am using an array bool[,,]. However, this is not very flexible, and the size quickly gets massive for a decent sized map.

I thought a dictionary that only holds the true values would be much more flexible and less memory hungry. I created a struct Vector3Int to hold the x,y,z values and use as a dictionary key. Dictionary looks like Dictionary<Vector3Int, bool>.

However, doing Dictionary lookups with this key appears to be 20-100 times slower than the array lookups with x,y,z integers.

Is there a faster/better way to do this? I am using the lookups for pathfinding, so the lookup needs to be quite fast as there may be hundreds/thousands of lookups for a single path.

Vector3Int code:

public struct Vector3Int
{
public int x,y,z;

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

//checks for equality
public static bool operator ==(Vector3Int a, Vector3Int b)
{
    return a.x==b.x && a.y ==b.y && a.z ==b.z;
}

public override bool Equals(object obj)
{
    return obj is Vector3Int && this == (Vector3Int)obj;
}

public override int GetHashCode ()
{
    return x.GetHashCode() ^ y.GetHashCode() ^ z.GetHashCode();
}

//checks the two vectors for non-equality
public static bool operator !=(Vector3Int a, Vector3Int b)
{
    return !(a==b);
}
}

Array lookup:

bool[,,] worldWalkable= new bool[1000,1000,1000];

public bool CheckWalkable(int x, int y, int z)
{
    return worldWalkable[x,y,z];
}

Vs Dictionary Lookup:

Dictionary<Vector3Int, bool> worldTraversable = new Dictionary<Vector3Int, bool>();

public bool CheckTraversable(Vector3Int block)
{
    bool tempBool;
    worldTraversable.TryGetValue(block, tempBool);
    return tempBool;
} 

Test code:

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class SpeedTest : MonoBehaviour {

Dictionary<Vector3Int, bool> testDict;
bool[,,] testArray;

// Use this for initialization
void Start () 
{
    InitializeContainers();
    RunTest();

}

void InitializeContainers()
{
    testDict= new Dictionary<Vector3Int, bool>(1000);
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            for(int k=0; k<10; k++)
            {
                testDict[new Vector3Int(i,j,k)]=true;
            }
        }
    }

    testArray=new bool[10,10,10];
}

void RunTest()
{
    bool tempBool;
    float timer1, timer2;

    timer1=Time.realtimeSinceStartup;
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            for(int k=0; k<10; k++)
            {
                tempBool= testDict[new Vector3Int(i,j,k)];
            }
        }
    }
    timer2=Time.realtimeSinceStartup;
    Debug.Log("Dictionary completion time: "+(timer2-timer1)*1000+"ms");

    timer1=Time.realtimeSinceStartup;
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            for(int k=0; k<10; k++)
            {
                tempBool=testArray[i,j,k];
            }
        }
    }
    timer2=Time.realtimeSinceStartup;

    Debug.Log("Array completion time: "+(timer2-timer1)*1000+"ms");
}
}

Edit: Revised struct that fixes the problem:

using UnityEngine;
using System.Collections;
using System;
using System.Collections.Generic;

//makes a Vector3 of integers
public struct Vector3Int : IEquatable<Vector3Int>
{
public int x,y,z;

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

public bool Equals(Vector3Int other)
{
    return other.x==this.x && other.y==this.y && other.z==this.z;
}

public static bool operator ==(Vector3Int a, Vector3Int b)
{
    return a.Equals(b);
}

public override bool Equals(object obj)
{
    if(obj==null || !(obj is Vector3Int))
        return false;

    return Equals((Vector3Int)obj);
}

public override int GetHashCode ()
{
    return x ^ (y<<10) ^ (z<<10);
}

public override string ToString ()
{
    return string.Format ("("+x+", "+y+", "+z+")");
}

public static bool operator !=(Vector3Int a, Vector3Int b)
{
    return !(a==b);
}
}

The issue was boxing/unboxing like Alexei suggested. Used the directions from this link to fix the issue.

Answer 1

20-100 difference sounds about right for Dictionary vs. array. It depends on how big the data set is and whether it fits in the CPU cache. Dictionary does a lot more than to execute a single load instruction plus some address calculation. It is O(1), too, but with a higher constant factor.

You can go a few times (like 3x) faster than the built in Dictionary by implementing your own hash table and removing stuff you don't need. Especially the % operation that it uses is surprisingly slow. When you replace it with a bitmask this immediately show up on profiles as an improvement.

Also note that your hash function is likely to generate a lot of collisions. For example all permutations of the same coordinates hash to the same slot. I'd try rotate(x, 23) ^ rotate(y, 11) ^ z.

Answer 2

According to How is GetHashCode() implemented for Int32? the int hashcode is the int itself. So your Vector3Int hashcode generates a large number of collisions. You can write a better distributed hashcode for your vector to resolve that problem. See What is the best algorithm for an overridden System.Object.GetHashCode? for more information on that.

Answer 3

Frequently you can significantly speed up operations on structs by using proper generic methods that remove need for boxing/unboxing.

In case of Dictionary implementing IEquatable<T> is good starting point:

public struct Vector3Int : IEquatable<Vector3Int>
{
    public int x,y,z;

    public bool Equals(Vector3Int other)
    {
       return  x == other.x && y == other.y && z == other.z;
    }

    public override int GetHashCode ()
    {
        return x^ (y <<5)^ (z << 5);
    }
    ....

Note that you still need decent GetHashCode to avoid collisions. If your ranges are limited (i.e. 0-1024) you may get away with very basic <<10 to get perfect hashing function. Otherwise check out other links provided like What is the best algorithm for an overridden System.Object.GetHashCode?

Answer 4

The lookup of false values in bool[,,] can't be done any faster as it has a compexity of O(1). But as a counter argument it consumes a lot of space.

If your map doesn't has too many false "places", another approach would be storing just the coordinates of the false values and always look up whether this list contains this coordinate or not. For increasing the lookup time of this list you could use a HashSet<T> which also has O(n) but consumes a little more space than a sorted list or array and is a little slower (some hashes have to be computed multiple times). The other way you could store the false values is in a sorted kind of list, which gives you the best memory consumption but the lookup time is worse compared to the other solutions (O(log n)). It should be sorted because you are searching values. Searching in an unsorted array would take O(n)