Can't find where memory allocation is happening

I have a method that is called many times, and according to the profiler, it is putting 200 mb of memory into GC.Alloc. I can't figure out where this is being allocated however. None of the other methods this one calls allocate memory, so I'm wondering what could be doing this.

This is part of my pathfinding code, so performance is crucial. The following methods are profiled and cause zero memory allocation. PriorityQueue.Add, PriorityQueue.GetRoot, GetRadiusAroundCell, GetDistance.

I thought the Exception might do it even when not thrown, but I ruled that out. PathNode and Point are value types.

What am I missing here? Where is the allocation happening?

Code (CSharp):

1.     /// <summary>
2.     /// Continues a path
3.     /// </summary>
4.     /// <param name="dest">destination cell</param>
5.     /// <param name="landonly"></param>
6.     /// <param name="useSupply"></param>
7.     /// <param name="friendlyBock">Friendly units block the path</param>
8.     /// <returns></returns>
9.     bool SearchDestination(Point dest,bool landonly,bool useSupply,bool friendlyBock, PathBlockCodes[,] pathblock, List<Point> neighbors)
10.     {
11.         Profiler.BeginSample("SearchDestination");
12.         //get next on queue,  and test for destination
13.         PathNode next = open.GetRoot();
14.         //put it in closed
15.         closed[next.Here.X,next.Here.Y] = next;
16.         //test for destination
17.         if (next.Here == dest)
18.         {
19.             Profiler.EndSample();
20.             return true;
21.         }
22.         //if not dest then put valid neighbors on open
23.         //get list of neighbors
24.         int radius;
25.         if (BoardManager.Instance.Map[next.Here.X, next.Here.Y].Terrain == MapCell.TerrainTypes.Water)
26.             radius = 2;
27.         else
28.             radius = 1;
29.  
30.         //        if(landPath)
31.         //            radius = 1;
32.         //        else
33.         //            radius = 2;
34.         BoardManager.Instance.GetRadiusAroundCell(neighbors,next.Here,radius);
35.         for(int i = 0;i < neighbors.Count;++i)
36.         {
37.             Point nodePos = neighbors[i];
38.             //moving from water to land and vise versa is only allowed at a distance of one
39.             if (BoardManager.Instance.Map[next.Here.X, next.Here.Y].Domain != BoardManager.Instance.Map[nodePos.X, nodePos.Y].Domain)
40.             {
41.                 if (BoardManager.Instance.Map[next.Here.X, next.Here.Y].Terrain != MapCell.TerrainTypes.City &&
42.                     BoardManager.Instance.GetDistance(next.Here, nodePos) > 1)
43.                 {
44.                     continue;//skip
45.                 }
46.             }
47.             if (pathblock != null && pathblock[nodePos.X, nodePos.Y] == PathBlockCodes.Block)
48.                 continue;
49.  
50.             //PathNode node = new PathNode(nodePos);
51.             openStorage[nodePos.X, nodePos.Y].Parent = next.Here;
52.             openStorage[nodePos.X, nodePos.Y].PassID = currentPassID;
53.             //perform a series of tests for validity
54.             bool valid = false;
55.             //first test for landPath match rembering land units can cross water but at
56.             //a higher cost unless landonly = true
57.             //if nodePos == dest. drop test fpr landPath
58.             int cost = next.Cost;
59.             if ( nodePos == dest ||
60.                 (BoardManager.Instance.Map[nodePos.X,nodePos.Y].Terrain == MapCell.TerrainTypes.Water &&
61.                 landPath == false) ||
62.                 (landPath == true && (landonly == false || (landonly == true && BoardManager.Instance.Map[nodePos.X,nodePos.Y].Terrain != MapCell.TerrainTypes.Water))))
63.             {
64.                 //test for friendlyBlock and if true, skip if the map contain a friendly
65.                 //non-supply unit. pathblock.TreatAsSupply will override friendly block
66.                 if(!friendlyBock || BoardManager.Instance.Map[nodePos.X,nodePos.Y].Owner != TurnStateManager.Instance.WhosTurn ||
67.                     BoardManager.Instance.Map[nodePos.X,nodePos.Y].Unit == Unit.UnitTypes.Truck ||
68.                     BoardManager.Instance.Map[nodePos.X,nodePos.Y].Unit == Unit.UnitTypes.SupplyShip ||
69.                     BoardManager.Instance.Map[nodePos.X,nodePos.Y].Terrain == MapCell.TerrainTypes.City ||
70.                     (pathblock != null && pathblock[nodePos.X,nodePos.Y] == PathBlockCodes.TreatAsSupply))
71.                 {
72.                     //Calculate cost to enter this cell from next
73.                     if(BoardManager.Instance.Map[nodePos.X,nodePos.Y].Terrain == MapCell.TerrainTypes.Water &&
74.                         !(useSupply && BoardManager.Instance.Map[nodePos.X,nodePos.Y].Owner == TurnStateManager.Instance.WhosTurn &&
75.                             BoardManager.Instance.Map[nodePos.X,nodePos.Y].Unit == Unit.UnitTypes.SupplyShip))
76.                     {
77.                         if (landonly)
78.                             throw new Exception("Water node in landonly path");
79.                         else
80.                             cost += 60;//slightly higher cost than land, but decreased from 100
81.                     }
82.                     else if((useSupply && BoardManager.Instance.Map[nodePos.X,nodePos.Y].Owner == TurnStateManager.Instance.WhosTurn &&
83.                         (BoardManager.Instance.Map[nodePos.X,nodePos.Y].Unit == Unit.UnitTypes.Truck ||
84.                             BoardManager.Instance.Map[nodePos.X,nodePos.Y].Unit == Unit.UnitTypes.SupplyShip ||
85.                             BoardManager.Instance.Map[nodePos.X,nodePos.Y].Terrain == MapCell.TerrainTypes.City)) ||
86.                             (pathblock != null && pathblock[nodePos.X,nodePos.Y] == PathBlockCodes.TreatAsSupply))
87.                     {
88.                         //no(small) cost for supply move !note: NO cost causes endless loops if no path found
89.                         cost += 1;
90.                     }
91.                     else
92.                         cost += 10;
93.                     openStorage[nodePos.X,nodePos.Y].Cost = cost;
94.                     //Then test for matching passID on closed
95.                     if (closed[nodePos.X,nodePos.Y].PassID == currentPassID)
96.                     {
97.                         //test for lower cost
98.                         if(cost < closed[nodePos.X,nodePos.Y].Cost)
99.                             valid = true;
100.                     }
101.                     else
102.                     {
103.                         //if passID mismatch, place on closed node for future comparison
104.                         //closed[nodePos.X,nodePos.Y] = node;
105.                         closed[nodePos.X, nodePos.Y].Parent = next.Here;
106.                         closed[nodePos.X, nodePos.Y].PassID = currentPassID;
107.                         closed[nodePos.X, nodePos.Y].Cost = cost;
108.                         valid = true;
109.                     }
110.                 }
111.             }
112.             //place on open queue if valid
113.             if(valid)
114.             {
115.                 //calculate distance to dest
116.                 double distance = BoardManager.Instance.GetDistance(nodePos,dest);
117.                 //add cost to distance for priority queue
118.                 distance += cost;
119.                 open.Add(openStorage[nodePos.X,nodePos.Y],distance);
120.             }
121.         }
122.         Profiler.EndSample();
123.  
124.         return false;
125.     }
126.  

 

It's pretty unusual for a function called "Add" to never allocate memory, though many common classes (e.g. List<T>) will only sometimes allocate memory when it's called.

I don't notice anything else obvious, but it's not short, it's fairly messy, and it's incomplete (refers to variables and functions that are not defined in this excerpt), so I'm not going to go through it with a fine-toothed comb. You could try disabling parts of the function to narrow down where it's happening.

Also, consider removing the commented-out code and refactoring with helper functions to make the logic clearer.

 

I figured it out, and it's worth mentioning what it was. I was able to use deep profiling for a small time before my computer crashed from the load, and I found the problem in my Point struct.

The Point struct used to be a class a long time ago, and the == operator still had code handling null objects and same references, causing a boxing/unboxing. It was a small allocation but I was using the heck out of it. So anyway, my pathfinder, instead of allocating ~170 MB per frame, is now allocating around 3 MB per frame!