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.