What is two dimensional array's memory representation?

Question

In Java, two dimensional array is multi one-dimensional array. That means those one-dimensional arrays not consecutive on memory.

In contrast, in C, two dimensional array in fact is one-dimensional array with size is total_row * total_column. Because Go language uses many concepts from C.

So my question is: does two dimensional array's memory representation in Go look like C or Java?

Answer 1

In Go, slices are often mistaken for arrays, so I answer regarding both.

Arrays

Quoting from the spec: Array types:

Array types are always one-dimensional but may be composed to form multi-dimensional types.

There you have your answer plain and clear. But the answer is not just that as arrays are values in Go, they are not descriptors (headers) like slices.

See this simple example:

x := [5][5]byte{}
fmt.Println(&x[0][3])
fmt.Println(&x[0][4])
fmt.Println(&x[1][0])

Output (try it on the Go Playground):

0x10432203
0x10432204
0x10432205

As you can see, the memory allocated and used for the array is contiguous: the second row starts at a memory address that is the subsequent to the address of the last element of the first row.

Checking size of arrays:

fmt.Println(unsafe.Sizeof([4][6]int{})) // 96
fmt.Println(unsafe.Sizeof([6][4]int{})) // 96

It doesn't matter if you switch rows and columns, its size is the same.

Slices

The same applies in case of slices: a multidimensional slice is a slice of slices. Spec: Slice types:

A slice is a descriptor for a contiguous segment of an underlying array and provides access to a numbered sequence of elements from that array.
...
Like arrays, slices are always one-dimensional but may be composed to construct higher-dimensional objects.

Slices are descriptors, a slice header contains a pointer to an element of an underlying (backing) array, a length and a capacity. So the number of total slices matters in terms of memory usage.

See this example:

x := make([][]byte, 2)
for i := range x {
    x[i] = make([]byte, 1000)
}
fmt.Println(len(x), len(x)*len(x[0]))

y := make([][]byte, 1000)
for i := range y {
    y[i] = make([]byte, 2)
}
fmt.Println(len(y), len(y)*len(y[0]))

Output (try it on the Go Playground):

2 2000
1000 2000

Both x and y multidimensional slices have 2000 elements total (2000 bytes), but x stores 2 slices only, each having 1000 elements, while y stores 1000 slices, each having 2 elements.

This means x requires 2 slice headers while y requires 1000 slice headers (for the elements, +1 for x and y themselves)!

A slice header is represented by reflect.SliceHeader:

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

The size of a slice header on 32-bit architectures is 12 bytes, on 64 bit architectures its 24 bytes. So in case of 32-bit arch elements of x require 2,000 bytes plus 2x12 bytes in memory which is 2,024 bytes, while elements of y require 2,000 bytes plus 1,000*12 which is 14,000 bytes.

Also note that elements of a multidimensional slice may contain slices with different lengths:

With arrays of arrays, the inner arrays are, by construction, always the same length; however with slices of slices (or arrays of slices), the inner lengths may vary dynamically. Moreover, the inner slices must be initialized individually.

Like in this example:

x := make([][]byte, 2)
x[0] = []byte{1, 2}
x[1] = []byte{1, 2, 3, 4}
fmt.Println(x[0])
fmt.Println(x[1])

Output (try it on the Go Playground):

[1 2]
[1 2 3 4]

---

If you haven't read, recommended: The Go Blog: Arrays, slices (and strings): The mechanics of 'append'