Introduction
Multi dimensional arrays exist in almost every programming language, but generally they are not the best solution to any problem because of various reasons. In this article I will show the different approaches offered by C# to create a 2D array. The article focuses primarialy on these, because it's the most common use of multidimensional arrays.
The "standard" way
C# rovides two types of arrays. The "standard" multidimensional array which has the following syntax:
var myarray = new int[2, 3];
The First number specifies the number of rows, while the second one specifies the number of columns. It has a neat, and understandable syntax, nothing fancy or complicated. But the biggest catch is the performance. If you have to pass this array to a function, then it will be painfully slow.
The slowness comes from the internals of the CLR. A multidimensional array doesn't have a Length property. Instead it has a GetLength(int dimension) method that returns the specified dimensions length. This requires more arithmetic than a standard Length property call, because length returns a memory segment, that can be compared, and worked with.
Jagged array
Another, better way is to use a Jagged array. A Jagged array is a one dimensional array of one dimensional arrays. Because of this layout the rows can differ in length. An extra overhead of memory consumption is added this way. The jagged array has the following syntax:
var jaggedArray = new int[2][];
for (int i=0; i<2; i++) jaggedArray[i] = new int[3];
The extra memory overhead comes from that we are storing an array of arrays. Each array has some internal properties that needed to be stored. This can be a big overhead, if we are dealing with a large array. Also notice the extra initialization cycle that is needed for the initialization of the sub arrays.
Dense array
Beyond these two approaches exists another implementation, which is called dense array. The dense term comes from matrices. A dense array is actually a one dimensional array indexed in a special way, so you can fit a 2 dimensional array into a one dimensial one.
This has some very good benefits, for example you could easily copy the elements, with an Array.Copy call. The downside of this is that you have to use some fancy indexing, which can lead to a serious performance issue. Typically you would calculate the element index for a given row, and column with the following method:
var index = column * rows + row;
array[index] = 33;
The biggest catch in this formula is the multiplication. Modern compilers and CPUs handle multiplication very well, but at large numbers this takes some time. If you have a 10000x10000 array, then you have to perform 100000000 multiplications on every indexing. This problem can be solved by storing the column and row multiplication value in another array, and looking up the value at indexing, sure it costs some extra memory, but the performance won't be as bad as multiplying every time.
The Implementation
Implementing the dense array method every time is bit of an overkill. Luckily we have Generics in c# since .net 2.0, so I came up with a generic Dense array class. The implementation is currently in a proof of concept stage, but it can easily extended to a full featured implementation.
namespace DenseArray
{
public class DenseArray<T> : IEnumerable<T>
{
private T[] _dataarray;
private int[] _columnindexes;
private void CalculateColumnIndexes()
{
_columnindexes = new int[Columns];
for (int i=0; i<Columns; i++)
{
_columnindexes[i] = i * Rows;
}
}
public DenseArray(int rows, int columns)
{
_dataarray = new T[rows * columns];
Rows = rows;
Columns = columns;
CalculateColumnIndexes();
}
public DenseArray(DenseArray<T> source)
{
_dataarray = new T[source.Rows * source.Columns];
Rows = source.Rows;
Columns = source.Columns;
Array.Copy(source._dataarray, this._dataarray, source._dataarray.LongLength);
_columnindexes = new int[Columns];
Array.Copy(source._columnindexes,
this._columnindexes,
source._columnindexes.LongLength);
}
public DenseArray(T[,] array)
{
Rows = array.GetLength(0);
Columns = array.GetLength(1);
_dataarray = new T[Rows * Columns];
CalculateColumnIndexes();
for (int i = 0; i < Rows; i++)
{
for (int j = 0; j < Columns; j++)
{
this[i, j] = array[i, j];
}
}
}
public int Columns { get; private set; }
public int Rows { get; private set; }
public T this[int row, int column]
{
get { return _dataarray[_columnindexes[column] + row]; }
set { _dataarray[_columnindexes[column] + row] = value; }
}
public T this[int i]
{
get { return _dataarray[i]; }
set { _dataarray[i] = value; }
}
public IEnumerator<T> GetEnumerator()
{
return (IEnumerator<T>)_dataarray.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return _dataarray.GetEnumerator();
}
public T[] GetRow(int rowindex)
{
T[] ret = new T[this.Columns];
for (int i = 0; i < this.Columns; i++)
{
ret[i] = this[rowindex, i];
}
return ret;
}
public T[] GetColumn(int columnindex)
{
T[] ret = new T[this.Rows];
for (int i = 0; i < this.Rows; i++)
{
ret[i] = this[i, columnindex];
}
return ret;
}
public void SetRow(int row, T[] items)
{
if (row < 0 || row > this.Rows)
throw new ArgumentOutOfRangeException("row");
if (items == null)
throw new ArgumentNullException("items");
int limit = Math.Min(items.Length, this.Columns);
for (int i = 0; i < limit; i++)
{
this[row, i] = items[i];
}
}
public void SetColumn(int column, T[] items)
{
if (column < 0 || column > this.Columns)
throw new ArgumentOutOfRangeException("column");
if (items == null)
throw new ArgumentNullException("items");
int limit = Math.Min(items.Length, this.Rows);
for (int i = 0; i < limit; i++)
{
this[i, column] = items[i];
}
}
}
}
Using the code
Using the implementation is quite easy, it acts like a 2D array, because the class provides object indexers:
var dense = new DenseArray<int>(3, 3);
dense[0, 2] = 42;
The implementation provides methods for getting and setting whole column data in an easy way. Also it implements the IEnumerable interface, which is at the moment
Performance
I measured the performance of the methods shown in this article with a simple program (source code is in the downloadable zip), that allocates a 10000x10000 element array using the standard 2D array method, the jagged method and my implementation. The results was measured on a machine with an Intel i3 530 CPU running a 64 bit version Windows 10 with .NET framework 4.6 and 4GiB RAM.
|
|
2D array |
Jagged array |
DenseArray |
1st Run |
Memory Allocation in bytes: |
400527360 |
403034112 |
400023552 |
Random fill time in ms: |
2292 |
1599 |
1962 |
Memory overhead in % |
0,6259 |
-0,1258 |
Speed Gain in % |
43,3396 |
16,8196 |
2nd Run |
Memory Allocation in bytes: |
400510976 |
403079168 |
400023552 |
Random fill time in ms: |
2285 |
1556 |
1990 |
Memory overhead in % |
0,6412 |
-0,1217 |
Speed Gain in % |
46,8509 |
14,8241 |
3rd Run |
Memory Allocation in bytes: |
400502784 |
403087360 |
400039936 |
Random fill time in ms: |
2271 |
1373 |
1958 |
Memory overhead in % |
0,6453 |
-0,1156 |
Speed Gain in % |
65,4042 |
15,9857 |
|
Average Memory in bytes: |
400513706,7 |
403066880 |
400029013,3 |
|
Average random fill time in ms: |
2282,666667 |
1509,333333 |
1970 |
|
Average memory overhead compared to 2d array in %: |
0,6375 |
-0,1210 |
|
Average speed gain compared to 2d array in %: |
51,2367 |
15,8714 |
Further improvements
The implementation in the future might be extended with proper GetHashCode() and ToString() ovverides, and a decent implementation of an Enumeratior coud be added, because the current enumerator enumerates items as they are in the underlaying array.
History
- 2015-12-16 Initial release