Padding a 2D array on all sides means adding new rows on the top and bottom, new columns on the left and right, and then copying the original elements to the center of the padded array. It looks like this:
There are two approaches for copying the elements. You can either copy individual items in a loop, or copy blocks of elements using Array.Copy(). In this article, I’ll show both approaches, and then show a performance comparison.
Table of Contents
Approach 1 – Copy individual elements
The simplest way to copy elements into a padded array is to loop through the original array and copy individual elements. In the padded array, elements will be shifted one row down and one column to the right.
Here’s the code:
public static int[,] GetPaddedArray_LoopVersion(int[,] originalArray)
{
int numRows = originalArray.GetLength(0);
int numColumns = originalArray.GetLength(1);
int[,] newArray = new int[numRows + 2, numColumns + 2];
for (int rowIndex = 0; rowIndex < numRows; rowIndex++)
{
for (int columnIndex = 0; columnIndex < numColumns; columnIndex++)
{
newArray[rowIndex + 1, columnIndex + 1] = originalArray[rowIndex, columnIndex];
}
}
return newArray;
}
Code language: C# (cs)Note: When using multidimensional arrays, you have to use .GetLength(0) to get the number of rows and .GetLength(1) to get the number of columns. Don’t use .Length.
Approach 2 – Copy blocks of elements
When you’re copying 1D arrays, using Array.Copy() is faster than looping through the array and copying individual elements.
Can you use Array.Copy() with multidimensional arrays? Yes, you can, because multidimensional arrays are actually 1D arrays with elements stored in a contiguous block in memory, like this:
The multidimensional appearance is a nice illusion provided by the data structure to simplify things for the programmer.
When you use Array.Copy() with multidimensional arrays, the tricky part is calculating the target location in the destination array, because you have to account for the new row on top and the new columns on the left and right. If you think about the original array and destination array as 1D arrays, then the block copying algorithm can be represented with this diagram:
The first block is located at Block Size (number of columns in the original array) + 3 (1 new row on top, 1 new columns on left, and 1 new column on the right). In each iteration, you find the next block by moving forward by Block Size + 2 (1 new column on the left and 1 new column on the right).
Here’s of the implementation of this block copying algorithm:
public static int[,] GetPaddedArray(int[,] originalArray)
{
int numRows = originalArray.GetLength(0);
int numColumns = originalArray.GetLength(1);
int[,] newArray = new int[numRows + 2, numColumns + 2];
int newIndex = numColumns + 3;
for (int originalIndex = 0; originalIndex < numRows; originalIndex++)
{
Array.Copy(originalArray, sourceIndex: originalIndex * numColumns, destinationArray: newArray, destinationIndex: newIndex, length: numColumns);
newIndex += numColumns + 2;
}
return newArray;
}
Code language: C# (cs)This approach is faster than copying individual items.
Buffer.BlockCopy() vs Array.Copy()
You can also use Buffer.BlockCopy() to copy blocks of elements. You’d use it in the loop above like this:
Buffer.BlockCopy(src: originalArray, srcOffset: originalIndex * numColumns * sizeof(int), dst: newArray, dstOffset: newIndex * sizeof(int), count: numColumns * sizeof(int));
Code language: C# (cs)This has approximately the same performance as Array.Copy(). It’s more difficult to understand though (since you have to deal with byte-based offsets), so I wouldn’t bother using it in this scenario.
Performance comparison
To compare performance, I generated 2D arrays of various sizes and used the algorithms to pad them. I ran the algorithms 10x for each size and took the average execution time.
Here are the results:
| rows x columns | 10×10 | 1000×1000 | 10,000×10,000 | 2×1,000,000 (short and wide) | 100,000×2 (tall and narrow) |
| Copy individual elements | 0.04 ms | 8.2 ms | 849 ms | 15 ms | 16 ms |
| Copy blocks with Array.Copy() | 0.02 ms | 2.4 ms | 281 ms | 4 ms | 24 ms |
The block copying approach is 2x – 4x faster in most cases. It’s slower when dealing with extremely tall and narrow arrays (many rows, few columns), because its block copying advantage is eliminated when copying lots and lots of very small blocks.
In practice, if I knew I’d only be dealing with small arrays, I’d use the individual copying approach. It’s easier to understand and the time difference is insignificant (0.02 ms vs 0.04 ms). In almost all other cases I’d use the block copying approach for improved performance.
Tests
The following unit tests verify correctness of the algorithm when dealing with arrays of various sizes:
[TestMethod()]
public void GetPaddedArrayTest_2by2()
{
int[,] originalArray = { { 1, 2 },
{ 3, 4 } };
int[,] expectedPaddedArray = { { 0, 0, 0, 0 },
{ 0, 1, 2, 0 },
{ 0, 3, 4, 0 },
{ 0, 0, 0, 0 } };
var actualPaddedArray = ArrayUtils.GetPaddedArray(originalArray);
CollectionAssert.AreEqual(expectedPaddedArray, actualPaddedArray);
}
[TestMethod()]
public void GetPaddedArrayTest_4by1()
{
int[,] originalArray = { { 1 },
{ 2 },
{ 3 },
{ 4 } };
int[,] expectedPaddedArray = { { 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 2, 0 },
{ 0, 3, 0 },
{ 0, 4, 0 },
{ 0, 0, 0 } };
var actualPaddedArray = ArrayUtils.GetPaddedArray(originalArray);
CollectionAssert.AreEqual(expectedPaddedArray, actualPaddedArray);
}
[TestMethod()]
public void GetPaddedArrayTest_1by4()
{
int[,] originalArray = { { 1, 2, 3, 4 } };
int[,] expectedPaddedArray = { { 0, 0, 0, 0, 0, 0 },
{ 0, 1, 2, 3, 4, 0 },
{ 0, 0, 0, 0, 0, 0 } };
var actualPaddedArray = ArrayUtils.GetPaddedArray(originalArray);
CollectionAssert.AreEqual(expectedPaddedArray, actualPaddedArray);
}
Code language: C# (cs)Note: To assert against multidimensional arrays, use CollectionAssert.AreEqual().
