Question Using Unity Jobs and Burst performance is greatly reduced while pathfinding

Hi!

I tried to implement pathfinding to my game in Unity, based on videos and improving on its code. To get more efficient with multi-threading, I would like to implement Unity Jobs, but as it is my first time to do it, I got some interesting results.

With the code below I get much worse performance than without jobs and burst and I don't understand why. On the profiler (profiling in Unity editor) it takes at least 14 ms to find a new path which is much worse than it should be, as it is much faster without jobs. That's only with two units doing the pathfinding to the same target on a level with below 1000 nodes. As I have found code on the internet in the same pathfinding topic, I think it should be much more performant. Watching videos performance hit should be below 1ms even in these situations. I found even github repo with bigger maps and more than 100 agents with much better performance.

Maybe I don't understand something with the job system, or made a mistake somewhere in the code, but can't figure out what causes this lower performance.

First I have a Unit which call a PathRequestManager every time the target object move a certain distance and after a specified time. This creates a new PathRequest with the current position, the target position, a callback which should be called when the path is calculated and the current unit. Then in a method I add the requested positions to separate NativeLists. These will contain the pathrequest parameters which should be called the next Update().

In the update I see if there pathfinding should be done with a shouldDoPathFinding variable which is set to true when a new path request is added. If it is true I call StartFindPathJobifiedHash method. Pass the required native arrays, hash maps, multi hash maps to the job and schedule it.

Code (CSharp):

1.     public void StartFindPathJobifiedHash()
2.     {
3.         CopyNextAttributesToCurrent(); //Copies the next pathfinding attributes to the current list
4.         ClearNextPathfindingAttributes(); //Clears next pathfinding attributes
5.  
6.        //unitList contains the units which should do pathfinding in current Update
7.         for (int i = 0; i < unitList.Count; i++)
8.         {
9.             NodeStruct startNode = grid.NodeFromWorldPointJobified(startPosList[i]);
10.             int startNodeID = startNode.nodeID;
11.             NodeStruct endNode = grid.NodeFromWorldPointJobified(endPosList[i]);
12.             int endNodeID = endNode.nodeID;
13.  
14. //startNodeList and endNodeList are native lists
15.             startNodeList.Add(startNodeID);
16.             endNodeList.Add(endNodeID);
17.         }
18.      
19.        //node neighbours are calculated when grid is created on main thread
20.         NativeParallelMultiHashMap<int, int> neighboursMap = grid.neighboursMapJobified;
21.  
22.         //originalPathNodeArray is a native array which contains all the nodes in the grid, populated when the grid is calculated
23.         // neighboursMap is a native parallel multi hashmap, with node ids as keys and neighbour ids as values, populated when the grid is calculated
24.         // waypointsHash native parallel multi hashmap with node ids as keys and positions as values
25.         FindPathJobParallel findPathJob = new FindPathJobParallel { pathRequestIDList = pathRequestIDList, originalPathNodeArray = originalPathNodeArray, neighboursMap = neighboursMap, startNodeList = startNodeList, endNodeList = endNodeList, waypointsHash = waypointsHash, pathSuccessHash = pathSuccessHash, originalPathNodeArrayHash = originalPathNodeHash, unitIDs = unitIDs };
26.      
27.         JobHandle jobHandle = findPathJob.Schedule(unitList.Count, 1);
28.         jobhandle = jobHandle;
29.     }

Here is the job:

Code (CSharp):

1. [BurstCompile]
2. public struct FindPathJobParallel : IJobParallelFor
3. {
4.  
5.  
6.  
7.     [ReadOnly, NativeDisableParallelForRestriction] public NativeArray<NodeStruct> originalPathNodeArray;
8.     [ReadOnly, NativeDisableParallelForRestriction] public NativeParallelHashMap<int, NodeStruct> originalPathNodeArrayHash;
9.  
10.     [ReadOnly, NativeDisableParallelForRestriction] public NativeList<int> pathRequestIDList;
11.     [ReadOnly, NativeDisableParallelForRestriction] public NativeList<int> startNodeList;
12.     [ReadOnly, NativeDisableParallelForRestriction] public NativeList<int> endNodeList;
13.     [ReadOnly, NativeDisableParallelForRestriction] public NativeList<int> unitIDs;
14.  
15.     [WriteOnly, NativeDisableParallelForRestriction] public NativeParallelMultiHashMap<int, float3> waypointsHash;
16.     [NativeDisableParallelForRestriction] public NativeParallelHashMap<int, bool> pathSuccessHash;
17.     [ReadOnly, NativeDisableParallelForRestriction] public NativeParallelMultiHashMap<int, int> neighboursMap;
18.  
19.  
20.  
21.  
22.     public void Execute(int i)
23.     {
24.  
25.         NativeList<NodeStruct> openList = new NativeList<NodeStruct>(Allocator.Temp);
26.  
27.         NativeList<NodeStruct> closedList = new NativeList<NodeStruct>(Allocator.Temp);
28.  
29.  
30.  
31.         NativeParallelMultiHashMap<int, int> openHashMap = new NativeParallelMultiHashMap<int, int>(100, Allocator.Temp);
32.         NativeParallelMultiHashMap<int, int> closedHashMap = new NativeParallelMultiHashMap<int, int>(1000, Allocator.Temp);
33.  
34.  
35.         NativeList<int> neighbourIndexes = new NativeList<int>(10, Allocator.Temp);
36.  
37.         NativeArray<NodeStruct> pathNodeArray = new NativeArray<NodeStruct>(originalPathNodeArray.Length, Allocator.Temp);
38.         NativeParallelHashMap<int, NodeStruct> pathNodeHash = new NativeParallelHashMap<int, NodeStruct>(originalPathNodeArray.Length, Allocator.Temp);
39.  
40.  
41.         NodeStruct startNodeStruct = originalPathNodeArray[0];
42.         NodeStruct endNodeStruct = originalPathNodeArray[0];
43.  
44.         NativeParallelHashMap<int, bool> successList = new NativeParallelHashMap<int, bool>(100, Allocator.Temp);
45.  
46.  
47.         NodeStruct nodeStruct = new NodeStruct();
48.         nodeStruct = originalPathNodeArrayHash[startNodeList[i]];
49.         startNodeStruct = nodeStruct;
50.  
51.         startNodeStruct.parentID = startNodeStruct.nodeID;
52.  
53.  
54.  
55.         NodeStruct endNodeStructNew = new NodeStruct();
56.         endNodeStructNew = originalPathNodeArrayHash[endNodeList[i]];
57.         endNodeStruct = endNodeStructNew;
58.  
59.         if (!pathNodeHash.ContainsKey(startNodeList[i]))
60.         {
61.             pathNodeHash.Add(startNodeList[i], startNodeStruct);
62.         }
63.         if (!pathNodeHash.ContainsKey(endNodeList[i]))
64.         {
65.             pathNodeHash.Add(endNodeList[i], endNodeStruct);
66.         }
67.  
68.  
69.  
70.         startNodeStruct.gCost = 0;
71.      
72.         openList.Add(startNodeStruct);
73.         openHashMap.Add(startNodeStruct.nodeID, startNodeStruct.nodeID);
74.      
75.         while (openList.Length > 0)
76.         {
77.             NodeStruct currentNodeStruct = GetLowestCostFNodeIndex(openList, openHashMap);
78.          
79.             closedList.Add(currentNodeStruct);
80.             closedHashMap.Add(currentNodeStruct.nodeID, currentNodeStruct.nodeID);
81.             if (currentNodeStruct.nodeID == endNodeStruct.nodeID)
82.             {
83.              
84.                 pathSuccessHash[unitIDs[i]] = true;
85.                 successList[i] = true;
86.                 break;
87.             }
88.  
89.        
90.             var neighboursOnIndexEnumerator = neighboursMap.GetValuesForKey(currentNodeStruct.nodeID);
91.  
92.             while (neighboursOnIndexEnumerator.MoveNext())
93.             {
94.              
95.                 neighbourIndexes.Add(neighboursOnIndexEnumerator.Current);
96.             }
97.  
98.             NodeStruct neighbourStruct = originalPathNodeArray[0];
99.          
100.             for (int neighbourIndex = 0; neighbourIndex < neighbourIndexes.Length; neighbourIndex++)
101.             {
102.              
103.                 int currentNeighbourIndex = neighbourIndexes[neighbourIndex];
104.                 neighbourStruct = originalPathNodeArray[currentNeighbourIndex];
105.  
106.  
107.                 if (!neighbourStruct.walkable)
108.                 {
109.                     continue;
110.                 }
111.  
112.                 if (closedHashMap.ContainsKey(currentNeighbourIndex))
113.                 {
114.                     continue;
115.                 }
116.  
117.  
118.                 int newMovementCostToNeighbour = currentNodeStruct.gCost + (int)GetDistanceJobified(currentNodeStruct.worldPosition, neighbourStruct.worldPosition, currentNodeStruct.gridX, currentNodeStruct.gridY, neighbourStruct.gridX, neighbourStruct.gridY) + neighbourStruct.movementPenalty;
119.                 if (newMovementCostToNeighbour < neighbourStruct.gCost || !openHashMap.ContainsKey(currentNeighbourIndex))
120.                 {
121.                     NodeStruct newNodeStruct = new NodeStruct();
122.                     newNodeStruct.gridX = neighbourStruct.gridX;
123.                     newNodeStruct.gridY = neighbourStruct.gridY;
124.                     newNodeStruct.walkable = neighbourStruct.walkable;
125.                     newNodeStruct.worldPosition = neighbourStruct.worldPosition;
126.                     newNodeStruct.movementPenalty = neighbourStruct.movementPenalty;
127.                     newNodeStruct.walkable = neighbourStruct.walkable;
128.                     newNodeStruct.gCost = newMovementCostToNeighbour;
129.                     newNodeStruct.hCost = (int)GetDistanceJobified(neighbourStruct.worldPosition, endNodeStruct.worldPosition, neighbourStruct.gridX, neighbourStruct.gridY, endNodeStruct.gridX, endNodeStruct.gridY);
130.                     newNodeStruct.nodeID = neighbourStruct.nodeID;
131.                     newNodeStruct.parentID = currentNodeStruct.nodeID;
132.                     newNodeStruct.angle = neighbourStruct.angle;
133.                     newNodeStruct.normal = neighbourStruct.normal;
134.                     newNodeStruct.modifiedWorldPosition = neighbourStruct.modifiedWorldPosition;
135.  
136.                     if (!pathNodeHash.ContainsKey(newNodeStruct.nodeID))
137.                     {
138.                         pathNodeHash.Add(newNodeStruct.nodeID, newNodeStruct);
139.                     }
140.                     else
141.                     {
142.                         pathNodeHash[newNodeStruct.nodeID] = newNodeStruct;
143.                     }
144.                  
145.                     if (!openHashMap.ContainsKey(currentNeighbourIndex))
146.                     {
147.                         openList.Add(neighbourStruct);
148.                         openHashMap.Add(neighbourStruct.nodeID, neighbourStruct.nodeID);
149.                      
150.                     }
151.                 }
152.  
153.             }
154.  
155.         }
156.  
157.         if (pathSuccessHash[unitIDs[i]])
158.         {
159.          
160.             NativeList<float3> waypointsList = new NativeList<float3>(100, Allocator.Temp);
161.             waypointsList = RetracePathJobifiedHash(originalPathNodeArrayHash[startNodeStruct.nodeID], pathNodeHash[endNodeStruct.nodeID], pathNodeHash);
162.  
163.             for (int j = 0; j < waypointsList.Length; j++)
164.             {
165.                 waypointsHash.Add(unitIDs[i], waypointsList[j]);
166.              
167.                 pathSuccessHash[unitIDs[i]] = waypointsList.Length > 0;
168.             }
169.  
170.  
171.  
172.             waypointsList.Dispose();
173.         }
174.      
175.  
176.         openList.Dispose();
177.         closedList.Dispose();
178.         pathNodeArray.Dispose();
179.         neighbourIndexes.Dispose();
180.  
181.     }
182.  
183.  
184.  
185.     public NodeStruct GetLowestCostFNodeIndex(NativeList<NodeStruct> openList, NativeParallelMultiHashMap<int, int> openHashMap)
186.     {
187.         NodeStruct lowestCostNode = openList[0];
188.  
189.         int lowestIndex = 0;
190.  
191.         for (int i = 0; i < openList.Length; i++)
192.         {
193.             NodeStruct currentCostNode = openList[0];
194.             if (currentCostNode.fCost < lowestCostNode.fCost)
195.             {
196.                 lowestCostNode = currentCostNode;
197.                 lowestIndex = i;
198.             }
199.         }
200.         openList.RemoveAt(lowestIndex);
201.         openHashMap.Remove(lowestCostNode.nodeID);
202.         return lowestCostNode;
203.  
204.     }
205.  
206.     float GetDistanceJobified(float3 nodeAPos, float3 nodeBPos, int nodeAGridX, int nodeAGridY, int nodeBGridX, int nodeBGridY)
207.     {
208.  
209.         int dstX = math.abs(nodeAGridX - nodeBGridX);
210.         int dstY = math.abs(nodeAGridY - nodeBGridY);
211.         float dstZ = math.abs(nodeAPos.y - nodeBPos.y);
212.  
213.         if (dstZ != 0)
214.         {
215.          
216.             dstZ = dstZ * 10;
217.         }
218.         if (dstX > dstY)
219.             return 14 * dstY + 10 * (dstX - dstY) + (int)dstZ;
220.         return 14 * dstX + 10 * (dstY - dstX) + (int)dstZ;
221.      
222.     }
223.  
224.     NativeList<float3> RetracePathJobifiedHash(NodeStruct startNode, NodeStruct endNode, NativeParallelHashMap<int, NodeStruct> pathNodeArray)
225.     {
226.      
227.  
228.         NativeList<NodeStruct> path = new NativeList<NodeStruct>(100, Allocator.Temp);
229.         NodeStruct currentNode = endNode;
230.  
231.         while (currentNode.nodeID != startNode.nodeID)
232.         {
233.          
234.             path.Add(currentNode);
235.             currentNode = pathNodeArray[currentNode.parentID];
236.  
237.         }
238.  
239.         NativeList<float3> pathVector3List = new NativeList<float3>(100, Allocator.Temp);
240.  
241.         for (int i = 0; i < path.Length; i++)
242.         {
243.             pathVector3List.Add(path[i].worldPosition);
244.         }
245.  
246.      
247.         NativeList<float3> waypoints = new NativeList<float3>(pathVector3List.Length, Allocator.Temp);
248.         for (int i = 0; i < path.Length; i++)
249.         {
250.             waypoints.Add(path[i].worldPosition);
251.         }
252.  
253.         path.Dispose();
254.         pathVector3List.Dispose();
255.  
256.         pathNodeArray.Dispose();
257.         return waypoints;
258.     }
259.  
260.  
261. }

The job is a simple A* pathfinding script rewritten with native lists and arrays. I create the nodes of the grid on start and use that at every pathfinding. To not overwrite nodes, when a new node found I create a new node struct and use that for the future of the current job. It works great, but I can't find out why a job takes at least 14ms to complete. In the profiler I can see that multiple threads are working.

Could you please take a look at the code and try to tell me where the problem is?

 

There is too much code honestly and getting it just right for Burst to provide you with a speed boost can be complicated. You can perhaps try to make a smaller example, also there is a dedicated Burst forum.

 

I don't think my problem is only with burst as normal (job running) code shouldn't be this slow either. I mean, I don't think that because the code runs on multiple cores it should have degraded performance. Tried to comment the code to be more understandable, but if there is any question I'm happy to answer.

The question has been moved to the job topic, thank you for that.

 

How are you measuring the performance? If you're too eager about it and you don't turn on the synchronous compilation, you are perhaps including the actual compilation in your measurement. That's one way to mess this up.

 

I have measured it with the profiler which shows the time the job actually takes, but tried to watch it in the late update method too (where I get the results) and it is the same.

 

1. Test in builds, not in editor
2. There is overhead from the job system, so it might perform slower for 2 units, but faster with 100 (compared to regular c#)
3. This is a lot of code, not digging through everything rn
4. Maybe check the burst compiler inspector to see if it gives interesting errors?

 

Look at noAlias attribute because you use NativeDisableParallelForRestriction on collections

 

There is no overhead, the code is literally compiled during runtime. (I mean sure, you can call that the overhead.) Turning on synchronous compilation flag forces it to finish compiling before start. See here.

 

There is overhead when scheduling jobs etc:
https://blog.unity.com/engine-platform/improving-job-system-performance-2022-2-part-2

Did not look at the full code, and did not see any profiler metrics, so this might not be the issue indeed

 

Oh sure I agree with that as an overhead, but that's when you attempt to use jobs for something rather small, so the logistics of it becomes more expensive than the actual work. I'm kind of assuming that's not the case here.

 

Thank you, I was able to solve the problem.

 

What was the solution?