C# resource contentions

Question

I am creating a flowfield for AI units and am trying to speed up some threaded code. My test grid size is 2000 x 2000 and I currently have the generation time down to 5.5 seconds. Profiling the code pointed something out that seems strange. The method that I use for the threads reports on average 140 Inclusive Contentions. 65 of which are for this line.

var neighbours = GetNeighbors4(cell.Point);

and below is the method being called.

private IEnumerable<IntegrationCell> GetNeighbors4(Point point)
        {
            var sizeX = _size.X - 1;
            var sizeY = _size.Y - 1;
            var x = point.X;
            var y = point.Y;

            //corners
            if (x == 0 && y == 0)
            {
                return new[]
                {
                    Cells[1, 0],
                    Cells[0, 1]
                };
            }

            if (x == sizeX && y == 0)
            {
                return new[]
                {
                    Cells[sizeX - 1, 0],
                    Cells[sizeX, 1]
                };
            }

            if (x == 0 && y == sizeY)
            {
                return new[]
                {
                    Cells[0, sizeY - 1],
                    Cells[1, sizeY]
                };
            }

            if (x == sizeX && y == sizeY)
            {
                return new[]
                {
                    Cells[sizeX - 1, sizeY],
                    Cells[sizeX, sizeY - 1]
                };
            }

            //top row
            if (y == 0)
            {
                return new[]
                {
                    Cells[x - 1, 0],
                    Cells[x + 1, 0],
                    Cells[x, 1]
                };
            }

            //bottom row
            if (y == sizeY)
            {
                return new[]
                {
                    Cells[x - 1, y],
                    Cells[x + 1, y],
                    Cells[x, y - 1]
                };
            }

            //left column
            if (x == 0)
            {
                return new[]
                {
                    Cells[0, y - 1],
                    Cells[0, y + 1],
                    Cells[1, y]
                };
            }

            //right column
            if (x == sizeX)
            {
                return new[]
                {
                    Cells[x, y - 1],
                    Cells[x, y + 1],
                    Cells[x - 1, y]
                };
            }

            //everything else
            return new[]
            {
                Cells[x, y - 1],
                Cells[x, y + 1],
                Cells[x - 1, y],
                Cells[x + 1, y]
            };
        }

Cells is just a simple 2 dimensional array to represent a grid

IntegrationCell[,] Cells; 

Now the way it works is that given a target cell in the grid, I step out like a 'wave' or 'ripple' from the target. Each iteration of the wave steps out one further from the target. As I do this, each iteration has more cells as the distance from the target increases. For each cell in each iteration, I spawn a new thread that computes the cells cost and returns a list of new cells that need to be computed/recomputed. There is a lot more that happens, but that's basically it. At one point I peak at roughly 120 threads before I hit the edge of the map, and I begin to have less cells each iteration until there are none left.

This is the full method of the thread run for each cell. (I can have over 100 running at any one time)

private IEnumerable<IntegrationCell> CostStep(IntegrationCell cell)
        {
            var result = new List<IntegrationCell>();  \\14 contentions
            var costBlock = _costfield.Cells[cell.Point.X, cell.Point.Y];
            if (costBlock.Cost == 255)
                return result;

            var neighbours = GetNeighbors4(cell.Point); \\65 contentions

            foreach (var neighbour in neighbours)  \\18 contentions
            {
                var newCost = costBlock.Cost + neighbour.Cost;
                if (cell.Cost > newCost)
                    cell.Cost = newCost;

                var childCostBlock = _costfield.Cells[neighbour.Point.X, neighbour.Point.Y];
                var newChildCost = cell.Cost + childCostBlock.Cost;

                if (childCostBlock.Cost == 255)
                    neighbour.Cost = 255;
                else if (neighbour.Cost > newChildCost)
                {
                    neighbour.Cost = newChildCost;
                    result.Add(neighbour);  \\39 contentions
                }
            }
            return result;
        }

I have placed comments of the contentions reported against each line. The contentions vary with each run, but what I cant understand is why I would have contentions reading from an array? Yes I'm updating the the array/cell and its neighbors if needed and each cell may be calculated more than once.

Answer 1

For each cell in each iteration, I spawn a new thread that ...

Probably that is the problem. Since you are doing CPU bound calculations, use only as many threads as CPU has your computer, indicated by the static property:

System.Environment.ProcessorCount

Otherwise, you are trying to schedule too much, causing a lot of contention and context switches.

I mean, more threads does not mean faster, actually, it may do the application slower because the thread management overhead. You use more threads when you have I/O bound operations, and therefore many threads are idle waiting for things to happen somewhere else (e.g.: a web service call, a database operation, an incoming request....)

Take a look at this answer: https://stackoverflow.com/a/12021285/307976, and also about how to limit the parallelism with PLINQ.