There seems to be a fair amount of confusion about the two ways to model a multidimensional array in C#. We will explore differences and similarities and hopefully help you choose the best model for your project.
If you need to brush up on array basics you can check out the article C# Back to Basics – Arrays.
Let’s dive right in!
Comparing Multidimensional and Jagged Arrays
The most-mentioned difference between a multi-dimensional array and a jagged array is that all rows have the same size in a multidimensional array. In contrast, each row in a jagged array can have a different size. While this is an interesting feature, it may be a bit misleading.
These arrays possess a range of features, including row size, that are natural consequences of their different abstractions. While a multi-dimensional array is a first-class type, jagged arrays are a composite type we create by recursive use of a simple one-dimensional array. This does not imply that the jagged array is inferior by any means. As we will see in the examples, they both have their pros and cons.
How to Initialize Arrays
Let’s start with the simplest use case and see how to initialize a multidimensional array and a jagged array.
int[,] matrix = new int[3, 4]; int[][] jaggedArray = new int[3][];
The first thing that we notice is the relatively intuitive declaration of an empty multidimensional array called matrix for this example. It will have 3 rows and 4 columns (by convention we will call the rightmost index a column index for two-dimensional arrays), or the other way around if we accept a different convention. We’ll see more information on this in the next section.
The second line leaves more room for interpretation.
When we read left to right we first notice int[] what we interpret as an array of integers. This is immediately followed by another [] which suggests that it is an array of whatever precedes it, in this case, an array of integers. We notice a somewhat counterintuitive initialization on the right side of the expression. Initialization of an integer array would look like int[3] so we would expect that an array of arrays of integers would be initialized by int[][3]. In this example, can you guess whether our jagged array is a collection of three arrays of integers or arrays containing three integers each?
Element Access and Array Traversal
Let’s see how we access elements of both of the array types.
Multidimensional Array Access
Let’s explore the state of these objects after initialization. First the multidimensional array matrix:
for (int row = 0; row < matrix.GetLength(0); row++)
{
for (int column = 0; column < matrix.GetLength(1); column++)
{
Console.Write($"{matrix[row, column]} ");
}
Console.WriteLine();
}
This example shows relatively straightforward row-by-row traversal. If we want to see the length we need to pass in the dimension, which is maybe not particularly obvious but is still consistent with the “array” of dimensions in the initialization expression ([3, 4]). The output it will show will look like this:
0 0 0 0 0 0 0 0 0 0 0 0
Nothing surprising here. Three rows, each with four elements. All elements have the default value for an integer.
Jagged Array Access
Now, let’s explore the jagged array:
for (int row = 0; row < jaggedArray.Length; row++)
{
for (int column = 0; column < jaggedArray[row].Length; column++)
{
Console.Write($"{jaggedArray[row][column]} ");
}
Console.WriteLine();
}
As we can see, it is obvious that each row will have an independent length. It is intuitive that we are iterating a collection of rows and that every row has a collection of elements.
When we run this example we get the following output:
Unhandled exception. System.NullReferenceException: Object reference not set to an instance of an object.
This shouldn’t come as a surprise. Arrays of integers are reference types, so when they are initialized, their elements are set to the default value for reference types, which is null. When we try to access the length of the first row we get this exception, since we still have no rows.
Let’s quickly fix that bug and re-run the example:
int[][] jaggedArray = new int[3][] { new int[4], new int[3], new int[4] };
for (int row = 0; row < jaggedArray.Length; row++)
{
for (int column = 0; column < jaggedArray[row].Length; column++)
{
Console.Write($"{jaggedArray[row][column]} ");
}
Console.WriteLine();
}
Here we combine the initializer with the default integer array constructor to allocate rows and exploit the fact that all rows can have a different number of elements. Let’s see the output that it produces:
0 0 0 0 0 0 0 0 0 0 0
The output is unsurprising. We can see that initializer inversion now makes more sense because the first number declares the number of rows, and we index the row and then the column, similarly to the multidimensional array.
How Array Memory is Allocated
Now let’s explore the memory layout of our multidimensional array and jagged array.
Multidimensional Array Memory Allocation
The CLI spec (section 8.9.1) states:
“Array elements shall be laid out within the array object in row-major order (i.e., the elements associated with the rightmost array dimension shall be laid out contiguously from lowest to highest index). The actual storage allocated for each array element can include platform-specific padding.”
This means that a multidimensional array is a single object in memory, equivalent to a simple array with the same total number of elements:
Elements are laid out row by row – first, the elements of the first row, from the lowest to the highest rightmost index, followed by the elements of the second row, and so on.
We can expect that for smaller multidimensional arrays this feature provides better memory and cache locality. This may, in some situations, provide better performance. However, larger arrays may easily end up in the Large Object Heap (LOH) if their size exceeds 85 Kb. This is not by itself a bad thing, but in some situations, it may be undesirable. For example, if we allocate many transient objects in the LOH, it may lead to multiple issues. Some of them include LOH fragmentation, slower and more frequent garbage collection, higher memory allocation, etc.
Jagged Array Memory Allocation
Unlike a multidimensional array, a jagged array allocates independent arrays on the heap for each row, with the addition of one array for the collection of rows:
Jagged arrays will have slightly larger overhead for a smaller number of elements. However, for a large number of elements it will create multiple smaller arrays in the Small Object Heap (SOH). If we process one row at a time, the memory or cache locality may not be an issue.
Array Performance Considerations
There are many online claims of superior performance for jagged arrays when compared to multidimensional arrays. As we will see from the following examples, this may not always be true.
Simple Scenario
Let’s start with a simple use case that resembles those used to justify the claim that a jagged array performs better.
We will process row-by-row, one element at a time looking for a maximum value.
public class MaxElement
{
private double[,] elementsMulti = new double[10000, 10000];
private double[][] elementsJagged = new double[10000][];
public MaxElement()
{
for (int i = 0; i < elementsJagged.Length; i++)
{
elementsJagged[i] = new double[10000];
}
elementsMulti[elementsMulti.GetLength(0) / 2, elementsMulti.GetLength(1) / 2] = 1;
int middleArrayIndex = elementsJagged.Length / 2;
elementsJagged[middleArrayIndex][elementsJagged[middleArrayIndex].Length / 2] = 1;
}
[Benchmark(Baseline = true)]
public void MultidimensionalArray()
{
double max = double.MinValue;
for (int row = 0; row < elementsMulti.GetLength(0); row++)
{
for (int col = 0; col < elementsMulti.GetLength(1); col++)
{
max = Math.Max(max, elementsMulti[row, col]);
}
}
}
[Benchmark]
public void JaggedArray()
{
double max = double.MinValue;
for (int row = 0; row < elementsJagged.Length; row++)
{
for (int col = 0; col < elementsJagged[row].Length; col++)
{
max = Math.Max(max, elementsJagged[row][col]);
}
}
}
}
Running this benchmark gives us the following results:
| Method | Mean | Error | StdDev | Ratio | |---------------------- |---------:|--------:|--------:|------:| | MultidimensionalArray | 154.7 ms | 0.53 ms | 0.47 ms | 1.00 | | JaggedArray | 142.2 ms | 0.31 ms | 0.27 ms | 0.92 |
Here we can see that the jagged array performs around 8% faster than the multidimensional array.
Image Convolution
Now let’s explore a different use case – a common one in image processing known as image convolution. The main difference from our simple scenario is that here, every pixel in an image will require additional 8 surrounding pixels in combination with a convolution kernel. We will explore the performance impact if we model that kernel with both a multidimensional array and a jagged array.
To keep the examples as simple as possible we will refrain from optimizing other aspects of the algorithm and instead concentrate solely on this particular aspect.
Multidimensional Array as Kernel
Let’s try to implement a simple image convolution method using a multidimensional array as a convolution kernel:
public void MultidimensionalKernel()
{
var image = (Bitmap)Image.FromFile("example.png");
var kernel = new double[,] { { 2, 1, 0 }, { 1, 0, -1 }, { 0, -1, -2 } };
int kernelOffset = 1;
var destImage = new Bitmap(image.Width, image.Height);
for (int row = 0; row < image.Height; row++)
{
for (int col = 0; col < image.Width; col++)
{
var r = 0d;
var g = 0d;
var b = 0d;
for (int kernelRow = 0; kernelRow < kernel.GetLength(0); kernelRow++)
{
int srcRow = row + (kernelRow - kernelOffset);
if (srcRow < 0 || srcRow > (image.Height - 1))
continue;
for (int kernelCol = 0; kernelCol < kernel.GetLength(1); kernelCol++)
{
int srcCol = col + (kernelCol - kernelOffset);
if (srcCol < 0 || srcCol > (image.Width - 1))
continue;
r += image.GetPixel(srcCol, srcRow).R * kernel[kernelRow, kernelCol];
g += image.GetPixel(srcCol, srcRow).G * kernel[kernelRow, kernelCol];
b += image.GetPixel(srcCol, srcRow).B * kernel[kernelRow, kernelCol];
}
}
r /= 3;
g /= 3;
b /= 3;
destImage.SetPixel(
col,
row,
Color.FromArgb(
(byte)Math.Round(r),
(byte)Math.Round(g),
(byte)Math.Round(b)));
}
}
}
In the first couple of lines, we initialize the source image, kernel, and destination image. Following that, we have two nested for loops that traverse the source image row-by-row. For each of those pixels, we have two more nested loops that traverse the convolution kernel and compute the resulting pixel color. The exact calculation is of minor importance, except for the fact that a single resulting pixel requires 9 values from the source image and another 9 from the convolution kernel.
Jagged Array as Kernel
Now, let’s see what the same algorithm looks like when we use a jagged array for a convolution kernel.
public void JaggedKernel()
{
var image = (Bitmap)Image.FromFile("example.png");
var destImage = new Bitmap(image.Width, image.Height);
var kernel = new double[][]
{
new double[] { 2, 1, 0 },
new double[] { 1, 0, -1 },
new double[] { 0, -1, -2 }
};
int kernelOffset = 1;
for (int row = 0; row < image.Height; row++)
{
for (int col = 0; col < image.Width; col++)
{
var r = 0d;
var g = 0d;
var b = 0d;
for (int kernelRow = 0; kernelRow < kernel.Length; kernelRow++)
{
int srcRow = row + (kernelRow - kernelOffset);
if (srcRow < 0 || srcRow > (image.Height - 1))
continue;
for (int kernelCol = 0; kernelCol < kernel[kernelRow].Length; kernelCol++)
{
int srcCol = col + (kernelCol - kernelOffset);
if (srcCol < 0 || srcCol > (image.Width - 1))
continue;
r += image.GetPixel(srcCol, srcRow).R * kernel[kernelRow][kernelCol];
g += image.GetPixel(srcCol, srcRow).G * kernel[kernelRow][kernelCol];
b += image.GetPixel(srcCol, srcRow).B * kernel[kernelRow][kernelCol];
}
}
r /= 3;
g /= 3;
b /= 3;
destImage.SetPixel(
col,
row,
Color.FromArgb(
(byte)Math.Round(r),
(byte)Math.Round(g),
(byte)Math.Round(b)));
}
}
}
Highlighted lines show the differences in initialization, boundary check, and element indexing. Other than that, the rest of the code is the same.
Benchmark Results
Now, let’s run these two methods in a BenchmarkDotNet benchmark and see how they compare.
| Method | Mean | Error | StdDev | Median | Ratio | RatioSD | |----------------------- |--------:|---------:|---------:|--------:|------:|--------:| | MultidimensionalKernel | 6.235 s | 0.0060 s | 0.0053 s | 6.235 s | 1.00 | 0.00 | | JaggedKernel | 7.644 s | 0.4561 s | 1.3159 s | 8.152 s | 1.35 | 0.30 |
As we can see, the jagged array kernel performs 35% slower than a multidimensional array kernel. It’s reasonable to assume that since the multidimensional array is a single object that fits in the CPU data cache, it will require fewer memory operations than a jagged array which is essentially 4 smaller objects requiring at least 4 memory operations.
From these two scenarios, we can see that both multidimensional array and jagged array have their place to shine. If performance is a key requirement in your scenario, be sure to thoroughly test both options before committing to one of them.
Multidimensional Arrays vs Jagged Arrays Summary
So let’s quickly recap the differences between jagged arrays and multidimensional arrays:
| Feature | Jagged Array | Multidimensional Array |
|---|---|---|
| Row size | Each row can have different size | All rows have the same size |
| Memory layout | Each row is a different array | Single contiguous memory block |
| Element access | Access row first, then column | Combined indexes for single element access |
| Performance | Better for large arrays and row by row processing | Better for smaller arrays and multi-row processing |
| Strength | Flexibility | Compactness |
Conclusion
In this article, we compared multidimensional arrays to jagged arrays in C#. We have seen that both have their pros and cons and that none is better in all situations. We have also seen that in performance-critical situations, both can be good candidates and that careful testing may be necessary to make the right choice.