Jagged ArrayUse jagged arrays to store data that comes in different sizes, and to reduce memory usage.
C#
Jagged arrays. With a jagged array, we can represent a 2D space with uneven lengths of each row. No space is wasted at the end of rows.
2D Array
Array
This kind of data structure can save memory by avoiding wasted space. And it can optimize lookups, as we are acting upon simple 1D arrays.
First example. This code is a short (but complete) program you can run in a console project. It builds up a small jagged array, and then iterates through it.
Part 1 First we create a jagged array of int elements. The array has 3 rows—so it can have 3 subarrays once they are all assigned.
int
Part 2 We assign the indexes to new int arrays. We only have an array of empty references—new arrays must be created for the rows.
Part 3 We examine each item in the jagged array. We call Length first on the array of references, and iterate through the rows.
Part 4 We iterate over the inner arrays (the columns) and print all the element values to the screen.
Console
using System; // Part 1: declare local jagged array with 3 rows. int[][] jagged = new int[3][]; // Part 2: create a new array in the jagged array. jagged[0] = new int[2]; jagged[0][0] = 1; jagged[0][1] = 2; jagged[1] = new int[1]; jagged[2] = new int[3] { 3, 4, 5 }; // Part 3: iterate overall the elements. for (int i = 0; i < jagged.Length; i++) { // Part 4: iterate over the inner array. // ... Print all its elements. int[] innerArray = jagged[i]; for (int a = 0; a < innerArray.Length; a++) { Console.Write(innerArray[a] + " "); } Console.WriteLine(); }
1 2 0 3 4 5
2D arrays. We determine how to choose between jagged arrays and 2D arrays. First ask the question: will every row in my collection have the same number of elements?
And If so, you can consider 2D arrays, but often you have varying numbers of elements.
Detail Jagged arrays are faster and have different syntax. They are faster because they use the "newarr", vector IL calls internally.
Detail The boost in performance with jagged arrays is because they are optimized for starting at 0 indexes.
IL
private static void CompareIL() { int[,] twoD = new int[1, 1]; // 1 x 1 array twoD[0, 0] = 1; int[][] jag = new int[1][]; jag[0] = new int[1]; jag[0][0] = 1; // 1 x 1 jagged array }
Methods. We can use the type of the jagged array in method signatures. They will be passed as references. This eliminates most copying. Only the reference is copied on each function call.
Detail This receives a jagged array. The string data is not copied when it is called—just the reference to that data is copied.
using System; class Program { static void PrintFirstElement(string[][] values) { // Only the reference is copied when this method is called with an array. Console.WriteLine(values[0][0]); } static void Main() { PrintFirstElement(new string[][] { new string[] { "bird", "frog" }, new string[] { "cat", "dog" }}); } }
bird
Benchmark, element access. The .NET Framework has optimizations for single-dimension arrays within a jagged array. A 2D array cannot take advantage of them.
Version 1 This code accesses the elements in a 2D array. It loops over elements with a for-loop.
for
Version 2 This version of the code accesses the elements of a jagged array in a for-loop.
Result Jagged have substantial optimizations in the intermediate language level. This can be exploited to speed up programs.
using System; using System.Diagnostics; const int _max = 100000; // Set up data. var a1 = new int[100, 100]; var a2 = new int[100][]; for (int i = 0; i < 100; i++) { a2[i] = new int[100]; } // Version 1: access 2D array. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { for (int a = 0; a < 100; a++) { for (int x = 0; x < 100; x++) { int c = a1[a, x]; } } } s1.Stop(); // Version 2: access jagged array. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { for (int a = 0; a < 100; a++) { for (int x = 0; x < 100; x++) { int c = a2[a][x]; } } } s2.Stop(); // Results. Console.WriteLine(s1.Elapsed.TotalMilliseconds); Console.WriteLine(s2.Elapsed.TotalMilliseconds);
2D array access: 1286.5545 ms Jagged array access: 486.7875 ms
Benchmark, allocation. Consider a space of 100 by 100 elements. We can allocate 100 separate arrays in a jagged array (101 arrays total), or use a single 2D array.
Version 1 Here we allocate 2D arrays. A 2D array only requires 1 allocation, and can be garbage-collected easier as well.
Version 2 In this version of the code we allocate jagged arrays in a tight loop. More allocations must occur.
Result It is faster to allocate the space in the form of a 2D array. The jagged array could be allocated lazily, which might be better.
using System; using System.Diagnostics; class Program { const int _max = 100000; static void Main() { // Version 1: create 2D array. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { Create2DArray(); } s1.Stop(); // Version 2: create jagged array. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { CreateJaggedArray(); } s2.Stop(); // Print times. Console.WriteLine(s1.Elapsed.TotalMilliseconds); Console.WriteLine(s2.Elapsed.TotalMilliseconds); } static int[][] CreateJaggedArray() { var array = new int[100][]; for (int i = 0; i < 100; i++) { array[i] = new int[100]; } return array; } static int[,] Create2DArray() { var array = new int[100, 100]; return array; } }
2D array allocation: 202.1575 ms Jagged array allocation: 452.0066 ms
Benchmark, memory use. A jagged array will use more memory than a 2D array assuming all sub-arrays are allocated. Here we see 2 programs that test memory use.
Version 1 This measures the memory use of a jagged array of 1000 sub-arrays. The memory size (measured with GetTotalMemory) is printed.
GC.Collect
Version 2 This measures the memory of a 2D array of the same element count as the jagged array in version 1. It uses less memory.
Result For rectangular shapes, prefer a 2D array for best memory compactness. Fewer bytes per element are used.
Important If your data is truly "jagged" or uneven in the lengths of subarrays, a jagged array may be far superior in memory use.
using System; long b1 = GC.GetTotalMemory(true); // Version 1: test memory usage of a jagged array. int[][] jagged = new int[1000][]; for (int i = 0; i < 1000; i++) { jagged[i] = new int[100]; } long b2 = GC.GetTotalMemory(true); jagged[0][0] = 0; Console.WriteLine("{0} bytes (jagged 1000 x 100)", b2 - b1);
865368 bytes (jagged 1000 x 100)
using System; long b1 = GC.GetTotalMemory(true); // Version 2: test memory usage of a two-dimensional array. int[,] array = new int[1000, 100]; long b2 = GC.GetTotalMemory(true); array[0, 0] = 0; Console.WriteLine("{0} bytes (2D 1000 x 100)", b2 - b1);
400040 bytes (2D 1000 x 100)
Performance, review. Element access in jagged arrays is faster than in 2D arrays. But to allocate a large space at once, 2D arrays are a better choice.
Summary. Jagged arrays are fast and easy to use once you learn the syntax. Prefer them to 2D arrays when performance is key. Be careful of excess memory usage.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.