patterncsharpCritical

Dijkstra path finding in C# is 15x slower than C++ version

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

pathfinding codereview csharp c++stackoverflow algorithm c#performance

15xpathdijkstraversionthanslowerfinding

Problem

I'm implementing Dijkstra's algorithm with a priority queue for a game I'm developing in Unity with C#. I was a bit disappointed with the performance, so I decided to port the code to C++ and see if the performance was related to the language or the algorithm itself. The path finding searches through a 3D grid and selects certain edges/neighbours based on some extra criteria (cell filter).

The problem is that this grid contains only 3000 cells, and the C# algorithm takes 38 ms to find a path. The C++ version takes just 2 ms to do the exact same thing!

The two source files of the algorithm are below and I'm wondering if someone experienced with C# can point out if I've done anything horribly inefficient or if C# is just slower here. The C# version stores the grid as a multidimensional array and the C++ version simulates it with an extra get_index function that computes an index into a vector using the x, y and z coordinates. I simulate a priority queue in C# by using a SortedSet with a special queue node containing both the value and the priority value (dist). Both algorithms simulate updating the priority queue by just appending a new value that invalidates the old one. This is done by also storing the priorities in the dist hash table.

C#:

```
using System;
using System.Collections.Generic;
using System.IO;

namespace PathFinding.NET {
struct Vec3 {
public int x, y, z;

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

public static Vec3 operator +(Vec3 a, Vec3 b) {
return new Vec3(a.x + b.x, a.y + b.y, a.z + b.z);
}

public static bool operator ==(Vec3 a, Vec3 b) {
return a.x == b.x && a.y == b.y && a.z == b.z;
}

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

public static float Dist(Vec3 a, Vec3 b) {
int dx = a.x - b.x;
int dy

Solution

First of all, you should run the FindPath method a couple of times before measuring, to give the C# runtime a chance to optimize the code.

// Warmup iterations for profiling
for (int j = 0; j < 10; j++) {
    FindPath(start, end, CellFilter);
}

Doing this gets the time down to about 17 ms on my machine (from 38 ms initially).

Running the code in a profiler shows that over 70% of the time is spent in Dictionary and SortedSet methods. For the JIT to optimize those you have to provide it with the necessary information for its Key types, otherwise it will fall back to runtime reflection and virtual method calls.

Any struct that is used as a Key in a Dictionary should implement the IEquatable interface. Also GetHashCode and Equals should be overridden (the compiler even warns about it).

struct Vec3 : IComparable, IEquatable {
    [...]
    public bool Equals(Vec3 other) {
        return other == this;
    }

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

    public override bool Equals(object obj) {
        if (obj is Vec3) {
            return (Vec3)obj == this;
        }

        return false;
    }
}

SortedSet mostlikely needs the IComparable interface which QueueNode already had, but it should be changed to the generic one.

struct QueueNode : IComparable {
    [...]
    public int CompareTo(QueueNode other) {
        if (Dist != other.Dist) {
            return Dist.CompareTo(other.Dist);
        } else {
            return Value.CompareTo(other.Value);
        }
    }
}

After these changes FindPath only takes 4 ms.

We can further optimize the Dictionaries by passing in a custom IEqualityComparerand eliminating the int.GetHashCode() calls.

class Vec3Comparer : IEqualityComparer
{
    public bool Equals(Vec3 a, Vec3 b) {
        return a == b;
    }

    public int GetHashCode(Vec3 obj) {
        return ((IntegerHash(obj.x)
                ^ (IntegerHash(obj.y) > 1)
                ^ (IntegerHash(obj.z) > 16;
        h *= 0x85ebca6bU;
        h ^= h >> 13;
        h *= 0xc2b2ae35U;
        h ^= h >> 16;
        return (int)h;
    }
}

void FindPath(...) {
    [...]

    // Initialize data structures
    Vec3Comparer comparer = new Vec3Comparer();
    var dist = new Dictionary(comparer);
    var prev = new Dictionary(comparer);

    [...]
}

The final code takes about 2.8 ms for FindPath.

In conclusion, always implement the correct generic interfaces on structures that are used in collections. It allows the JIT to actually optimize the code.

Useful links

-
Dictionary(Of TKey, TValue) Class. See the Remarks section, thanks to @t3chb0t.

-
C# performance tips for Unity, part 2: structs and enums. It talks specifically about the Unity implementation.

Final Code

```
using System;
using System.Collections.Generic;
using System.IO;

namespace PathFinding.NET {
struct Vec3 : IComparable, IEquatable {
public int x, y, z;

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

public static Vec3 operator +(Vec3 a, Vec3 b) {
return new Vec3(a.x + b.x, a.y + b.y, a.z + b.z);
}

public static bool operator ==(Vec3 a, Vec3 b) {
return a.x == b.x && a.y == b.y && a.z == b.z;
}

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

public static float Dist(Vec3 a, Vec3 b) {
int dx = a.x - b.x;
int dy = a.y - b.y;
int dz = a.z - b.z;

return (float)Math.Sqrt(dx dx + dy dy + dz * dz);
}

public static Vec3 Min(Vec3 a, Vec3 b) {
return new Vec3(
Math.Min(a.x, b.x),
Math.Min(a.y, b.y),
Math.Min(a.z, b.z)
);
}

public static Vec3 Max(Vec3 a, Vec3 b) {
return new Vec3(
Math.Max(a.x, b.x),
Math.Max(a.y, b.y),
Math.Max(a.z, b.z)
);
}

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

public int CompareTo(Vec3 other) {
if (x == other.x) {
if (y == other.y) {
return z.CompareTo(other.z);
} else {
return y.CompareTo(other.y);
}
} else {
return x.CompareTo(other.x);
}
}

public bool Equals(Vec3 other) {
return other == this;
}

public override int GetHashCode() {
return ((x.GetHashCode()
^ (y.GetHashCode() > 1)
^ (z.GetHashCode() {
public Vec3 Value;
public float Dist;

public QueueNode(Vec3 value, float dist) {

Code Snippets

// Warmup iterations for profiling
for (int j = 0; j < 10; j++) {
    FindPath(start, end, CellFilter);
}

struct Vec3 : IComparable<Vec3>, IEquatable<Vec3> {
    [...]
    public bool Equals(Vec3 other) {
        return other == this;
    }

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

    public override bool Equals(object obj) {
        if (obj is Vec3) {
            return (Vec3)obj == this;
        }

        return false;
    }
}

struct QueueNode : IComparable<QueueNode> {
    [...]
    public int CompareTo(QueueNode other) {
        if (Dist != other.Dist) {
            return Dist.CompareTo(other.Dist);
        } else {
            return Value.CompareTo(other.Value);
        }
    }
}

class Vec3Comparer : IEqualityComparer<Vec3>
{
    public bool Equals(Vec3 a, Vec3 b) {
        return a == b;
    }

    public int GetHashCode(Vec3 obj) {
        return ((IntegerHash(obj.x)
                ^ (IntegerHash(obj.y) << 1)) >> 1)
                ^ (IntegerHash(obj.z) << 1);
    }

    static int IntegerHash(int a) {
        // fmix32 from murmurhash
        uint h = (uint)a;
        h ^= h >> 16;
        h *= 0x85ebca6bU;
        h ^= h >> 13;
        h *= 0xc2b2ae35U;
        h ^= h >> 16;
        return (int)h;
    }
}

void FindPath(...) {
    [...]

    // Initialize data structures
    Vec3Comparer comparer = new Vec3Comparer();
    var dist = new Dictionary<Vec3, float>(comparer);
    var prev = new Dictionary<Vec3, Vec3?>(comparer);

    [...]
}

using System;
using System.Collections.Generic;
using System.IO;

namespace PathFinding.NET {
    struct Vec3 : IComparable<Vec3>, IEquatable<Vec3> {
        public int x, y, z;

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

        public static Vec3 operator +(Vec3 a, Vec3 b) {
            return new Vec3(a.x + b.x, a.y + b.y, a.z + b.z);
        }

        public static bool operator ==(Vec3 a, Vec3 b) {
            return a.x == b.x && a.y == b.y && a.z == b.z;
        }

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

        public static float Dist(Vec3 a, Vec3 b) {
            int dx = a.x - b.x;
            int dy = a.y - b.y;
            int dz = a.z - b.z;

            return (float)Math.Sqrt(dx * dx + dy * dy + dz * dz);
        }

        public static Vec3 Min(Vec3 a, Vec3 b) {
            return new Vec3(
                Math.Min(a.x, b.x),
                Math.Min(a.y, b.y),
                Math.Min(a.z, b.z)
            );
        }

        public static Vec3 Max(Vec3 a, Vec3 b) {
            return new Vec3(
                Math.Max(a.x, b.x),
                Math.Max(a.y, b.y),
                Math.Max(a.z, b.z)
            );
        }

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

        public int CompareTo(Vec3 other) {
            if (x == other.x) {
                if (y == other.y) {
                    return z.CompareTo(other.z);
                } else {
                    return y.CompareTo(other.y);
                }
            } else {
                return x.CompareTo(other.x);
            }
        }

        public bool Equals(Vec3 other) {
            return other == this;
        }

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

        public override bool Equals(object obj) {
            if (obj is Vec3) {
                return (Vec3)obj == this;
            }

            return false;
        }
    }

    struct Cell {
        public bool Occupied;
        public bool WalkableSurface;
    }

    struct QueueNode : IComparable<QueueNode> {
        public Vec3 Value;
        public float Dist;

        public QueueNode(Vec3 value, float dist) {
            Value = value;
            Dist = dist;
        }

        public int CompareTo(QueueNode other) {
            if (Dist != other.Dist) {
                return Dist.CompareTo(other.Dist);
            } else {
                return Value.CompareTo(other.Value);
            }
        }
    }

    class Vec3Comparer : IEqualityComparer<Vec3>
    {
        public bool Equals(Vec3 a, Vec3 b) {
            return a == b;
        }

        public int GetHashCode(Vec3 obj) {
            return ((IntegerHash(obj.x)

Context

StackExchange Code Review Q#152733, answer score: 308

Revisions (0)

No revisions yet.