Fast initialization of big jagged array

Question

I have a jagged array that represents a Grid and each item of array is a Cell. The Grid have 2600 rows and 2600 columns. I need to calculate a coordinate of each Cell, create instance of Cell object and add it into array. Now the code I'm using takes about 3200-3800 ms on my computer. Is there any way to make it faster?

public GridCell[][] Cells;
private void CreateCells(int cellWidth, int cellHeight, int startX, int startY)
    {          
        Cells = new GridCell[RowsCount][];
        for (int i = 0; i < RowsCount; i++)
        {
            Cells[i] = new GridCell[ColumnsCount];
            for (int j = 0; j < ColumnsCount; j++)
            {
                Point coordinate = new Point(startX + cellWidth * j, startY + cellHeight * i);
                Cells[i][j] = new GridCell(cellWidth, cellHeight, coordinate);
            }
        }
    }

Answer 1

You mentioned in the comments that both GridCell and Point are classes. Classes are by far the most common thing to create, but if you're okay with the different semantics and they mostly hold data rather than functionality, you can turn them into structs.

A struct is almost like a class, but it's a value type rather than a reference type. This means that code like this:

Point a = new Point(0, 0);
Point b = a;
b.X = 5;
Console.WriteLine(a);

…will print 0 if it's a struct and 5 if it's a class.

These semantics allow structs to be embedded within other things, and not have to have their own space on the heap. Allocating from the heap can be expensive, so if you can allocate, say, an array of structs, only one allocation needs to be done rather than many.

Answer 2

Considering you are working with 6760000 objects, you have a fine performance. And the main time is probably spent constructing new objects on heap. So using structures instead of class gives you a boost, as you have observed.

If you have large CPU cache you can also try to use single array like:

public GridCell[] Cells = new GridCell[RowsCount * ColumnsCount];

with addressing, like:

Cells[i * ColumnsCount + j] = x;

Answer 3

Consider using Parallel.For - something like this is trivial to multithread.

As shown, while bigger initial gains can be found elsewhere if you're willing to change functionality (in this case by using structs, but allocating single array might also have some benefit) threading can still be used to increase performance.

Some simple tests:

//Single Threaded          : 1701, 1825, 1495, 1606
//Multi Threaded           : 1516, 1446, 1581, 1401
//Struct Single Threaded   :  154,  157,  153,  151
//Struct MultiThreaded     :  104,  107,  106,  103

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                Benchmark("Single Threaded", () => CreateCells(1, 1, 0, 0));
                Benchmark("Multi Threaded", () => CreateCellsThreaded(1, 1, 0, 0));
                Benchmark("Struct Single Threaded", () => CreateStructCells(1, 1, 0, 0));
                Benchmark("Struct MultiThreaded", () => CreateStructCellsThreaded(1, 1, 0, 0));
            }
        }

        static void Benchmark(string Name, Action test)
        {
            var sw = Stopwatch.StartNew();
            test();
            UpdateResults(Name, sw.ElapsedMilliseconds.ToString());
            GC.Collect();
        }

        static Dictionary<string, string> results = new Dictionary<string, string>();
        static void UpdateResults(string key, string value)
        {
            value = value.PadLeft(4);
            if (results.ContainsKey(key))
                results[key] += ", " + value;
            else
                results[key] = value;

            Console.Clear();
            foreach (var kvp in results) Console.WriteLine(kvp.Key.PadRight(25) + ": " + kvp.Value);
        }

        const int RowsCount = 2600;
        const int ColumnsCount = 2600;

        public class Point
        {
            public int x;
            public int y;
            public Point(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
        }

        public class GridCell
        {
            public int width;
            public int height;
            public Point point;
            public GridCell(int width, int height, Point point)
            {
                this.width = width;
                this.height = height;
                this.point = point;
            }
        }

        public struct StructPoint
        {
            public int x;
            public int y;
            public StructPoint(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
        }


        public struct StructGridCell
        {
            public int width;
            public int height;
            public StructPoint point;
            public StructGridCell(int width, int height, StructPoint point)
            {
                this.width = width;
                this.height = height;
                this.point = point;
            }
        }

        private static void CreateCells(int cellWidth, int cellHeight, int startX, int startY)
        {
            var Cells = new GridCell[RowsCount][];
            for (int i = 0; i < RowsCount; i++)
            {
                Cells[i] = new GridCell[ColumnsCount];
                for (int j = 0; j < ColumnsCount; j++)
                {
                    Point coordinate = new Point(startX + cellWidth * j, startY + cellHeight * i);
                    Cells[i][j] = new GridCell(cellWidth, cellHeight, coordinate);
                }
            }
        }
        private static void CreateCellsThreaded(int cellWidth, int cellHeight, int startX, int startY)
        {
            var Cells = new GridCell[RowsCount][];
            Parallel.For(0, RowsCount, new ParallelOptions { MaxDegreeOfParallelism = 4 }, i =>
            {
                Cells[i] = new GridCell[ColumnsCount];
                for (int j = 0; j < ColumnsCount; j++)
                {
                    Point coordinate = new Point(startX + cellWidth * j, startY + cellHeight * i);
                    Cells[i][j] = new GridCell(cellWidth, cellHeight, coordinate);
                }
            });
        }

        private static void CreateStructCells(int cellWidth, int cellHeight, int startX, int startY)
        {
            var Cells = new StructGridCell[RowsCount][];
            for (int i = 0; i < RowsCount; i++)
            {
                Cells[i] = new StructGridCell[ColumnsCount];
                for (int j = 0; j < ColumnsCount; j++)
                {
                    var coordinate = new StructPoint(startX + cellWidth * j, startY + cellHeight * i);
                    Cells[i][j] = new StructGridCell(cellWidth, cellHeight, coordinate);
                }
            }
        }
        private static void CreateStructCellsThreaded(int cellWidth, int cellHeight, int startX, int startY)
        {
            var Cells = new StructGridCell[RowsCount][];
            Parallel.For(0, RowsCount, i =>
            {
                Cells[i] = new StructGridCell[ColumnsCount];
                for (int j = 0; j < ColumnsCount; j++)
                {
                    var coordinate = new StructPoint(startX + cellWidth * j, startY + cellHeight * i);
                    Cells[i][j] = new StructGridCell(cellWidth, cellHeight, coordinate);
                }
            });
        }
    }
}