koobas.hobune.stream
Multidimensional array vs dictionary performance
I am building a voxel based pathfinding system. One of the important parts is being able to mark blocks as being clear to walk on.
I made an array to hold the bool walkable using the x,y,z integer coordinates as a key:
bool[,,] worldWalkable = new bool[1000,1000,1000];
The thing is, there tends to be a lot of wasted space(non walkable blocks) and it uses a ton of memory as the map size goes up.
I thought a dictionary might be a better choice, so I made this:
Dictionary<Vector3Int, bool> worldTrav = new Dictionary<Vector3Int, bool>();
I only store true values to save memory. Everything else is assumed false.
Vector3Int is a struct that holds the x,y,z integers so I can use it as a key for the dictionary.
Like this:
using UnityEngine;
using System.Collections;
//makes a Vector3 of integers
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();
}
public static bool operator !=(Vector3Int a, Vector3Int b)
{
return !(a==b);
}
}
The thing is, when I use the dictionary, it is slooooow. Even though my array has about a billion indexes and the dictionary has 7000, the dictionary access with Vector3Int as key is much slower. Like 30-100 times slower.
Is there a better way to contain the boolean information? I will be loading and unloading chunks, so a dictionary seems much more flexible. The lookup needs to be much faster than the dictionary seems to be.
Thanks.
Edit: Turns out that I needed to implement IEquatable. Good link on how to do it is here.
After implementing, time to calculate dropped from 225+ms to 2-8ms. The speed increase appears to be from preventing boxing/unboxing while using the dictionary.
New code:
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 static Vector3Int operator +(Vector3Int a, Vector3Int b)
{
Vector3Int temp = new Vector3Int();
temp.x = a.x +b.x;
temp.y = a.y +b.y;
temp.z = a.z +b.z;
return temp;
}
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);
}
}
Dictionaries are basically hashTables so you should override GetHashCode() in Vector3I.
@Ackior: The way you calculate the Hashcode is actually very bad. It has tons of collisions with other values in your dictionary. Ins$$anonymous$$d of "xor" it would be way better to just multiply the 3 hashes together:
return x.GetHashCode() * y.GetHashCode() * z.GetHashCode();
A better implementation would be something like that (found somewhere on the net). I had to convert the int to an uint to avoid automatic type conversion into long.
uint seed = (uint)x.GetHashCode() + 0x9e3779b9;
seed ^= (uint)y.GetHashCode() + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= (uint)z.GetHashCode() + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return (int)seed;
However i'm not sure if a better hash will give you a seed boost. It always depends on the implementation of the Dict. -> benchmarking is the only way to find out which is faster in which cases ^^. It's hard to impossible to predict how a certain method will perform. It depends on so many things (CPU cache size for example).
When accessing the dictionary, you are searching for one object out of 7000
when accessing the array, there is no searching at all:
from a 3 dimensional array you select one 2 dimensional array from 1000 arrays
from the selected 2 dimensional array you select a 1 dimensional array from 1000 arrays
you select one object from 1000 objects in the 1 dimensional array
getting an element from an array is very, VERY fast - much faster than getting a hashcode and accessing the dictionary
if your main problem is memory usage, I would suggest splitting your 3D array
make a tree with sub-trees, like when you make a "k-d tree"
public class SmallNode
{
public bool[,,] walkable = new bool[10,10,10];
}
public class AverageNode
{
public SmallNode[,,] small = new SmallNode[10,10,10];
}
public class LargeNode
{
public AverageNode[,,] average = new AverageNode[10,10,10];
}
public class MyGame
{
LargeNode large = new LargeNode();
void Setup()
{
// initialize large - some of the elements in average[,,] can be "null", saving memory
// initialize all elements in average - some of the elements in small[,,] can be "null", saving memory
// initialize all elements in small - here you must assign all bool values
}
bool isWorldWalkable(int x, int y, int z)
{
// change x from [0,1000] to [0,10]
int averagex = x / 100;
int averagey = y / 100;
int averagez = z / 100;
AverageNode average = large.average[averagex,averagey,averagez];
if(average != null)
{
// get the x interval between 0-100, 100-200, etc...
int smallx = (x - averagex * 100) / 10;
int smally = (y - averagey * 100) / 10;
int smallz = (z - averagez * 100) / 10;
SmallNode small = average.small[smallx,smally,smallz];
if(small != null)
{
int walkablex = (x - averagex * 100 - smallx * 10);
int walkabley = (y - averagey * 100 - smally * 10);
int walkablez = (z - averagez * 100 - smallz * 10);
return small.walkable[walkablex,walkabley,walkablez];
}
}
return false;
}
}
Just want to add here that a multidimensional array access doesn't involve those 3 steps you've mentioned. The system directly calculates the index of the element, out of the 3 indices. Internally a multi-dim-array is more like a single flattened array.
Also your chunking of world fragments introduce a similar problem the Dictionary has but in a more complicated way ^^. If you have a good hash a Dictionary shouldn't have to search many elements as the dictionary does this "chunking" internally. Basically it groups certain hashes into "buckets" and each bucket is an ordinary array. It just caluclates the index for the correct bucket and searches that bucket for the required element.
The average case (with a good hash) for 7000 elements is that each bucket contains about 27 elements (256 buckets).
Nonetheless if it's going to be a huge world (maybe almost infinite like $$anonymous$$inecraft ^^) chunking is the only viable way of storing / handeling that amount of data.
$$anonymous$$eep in $$anonymous$$d that chunk sizes which uses a power of 2 are way more cpu friendly since you can simply right / left shift the index or bit-mask the lower index part:
int index;
int chunkIndex = index >> 4; // chunksize=16 (2 to the power of 4 == 16)
int subIndex = index & (1<<4-1); // use 15 as bit mask 0x0F or 00001111b
For a chunksize of 32 you would use 5 ins$$anonymous$$d of 4 and so on...
I'd agree, an array of 1bn booleans is 1gb, 2.47bn is the upper limit for a single array, it's instant lookup of memory address, whereas other methods are a loop through thousands of array entries to compare one of them.
