Proposal: Multi-dimensional slices

Author(s): Brendan Tracey, with input from the gonum team

Last updated: November 17th, 2016

§ Abstract

This document proposes a generalization of Go slices from one to multiple dimensions. This language change makes slices more naturally suitable for applications such as image processing, matrix computations, gaming, etc.

Arrays-of-arrays(-of-arrays-of...) are continuous in memory and rectangular but are not dynamically sized. Slice-of-slice(-of-slice-of...) are dynamically sized but are not continuous in memory and do not have a uniform length in each dimension. The generalized slice described here is an N-dimensional rectangular data structure with continuous storage and a dynamically sized length and capacity in each dimension.

This proposal defines slicing, indexing, and assignment, and provides extended definitions for make, len, cap, copy and range.

§ Nomenclature

This document extends the notion of a slice to include rectangular data. As such, a multi-dimensional slice is properly referred to as simply a "slice". When necessary, this document uses 1d-slice to refer to Go slices as they are today, and nd-slice to refer to a slice in more than one dimension.

§ Previous discussions

This document is self-contained, and prior discussions are not necessary for understanding the proposal. They are referenced here solely to provide a history of discussion on the subject. Note that in a previous iteration of this document, an nd-slice was referred to as a "table", and that many changes have been made since these earlier discussions.

About this proposal

1. Issue 6282 -- proposal: spec: multidimensional slices
2. gonum-dev thread:
3. golang-nuts thread: Proposal to add tables (two-dimensional slices) to go
4. golang-dev thread: Table proposal (2-D slices) on go-nuts
5. golang-dev thread: Table proposal next steps
6. Robert Griesemer proposal review: which suggested name change from "tables" to just "slices", and suggested referring to down-slicing as simply indexing.

Other related threads

• golang-nuts thread -- Multi-dimensional arrays for Go. It's time
• golang-nuts thread -- Multidimensional slices for Go: a proposal
• golang-nuts thread -- Optimizing a classical computation in Go
• Issue 13253 -- proposal: spec: strided slices Alternate proposal relating to multi-dimensional slices (closed)

§ Background

Go presently lacks multi-dimensional slices. Multi-dimensional arrays can be constructed, but they have fixed dimensions: a function that takes a multi-dimensional array of size 3x3 is unable to handle an array of size 4x4. Go currently provides slices to allow code to be written for lists of unknown length, but similar functionality does not exist for multiple dimensions; slices only work in a single dimension.

One very important concept with this layout is a Matrix. Matrices are hugely important in many sections of computing. Several popular languages have been designed with the goal of making matrices easy (MATLAB, Julia, and to some extent Fortran) and significant effort has been spent in other languages to make matrix operations fast (Lapack, Intel MKL, ATLAS, Eigpack, numpy). Go was designed with speed and concurrency in mind, and so Go should be a great language for numeric applications, and indeed, scientific programmers are using Go despite the lack of support from the standard library for scientific computing. While the gonum project has a matrix library that provides a significant amount of functionality, the results are problematic for reasons discussed below. As both a developer and a user of the gonum matrix library, I can confidently say that not only would implementation and maintenance be much easier with this extension to slices, but also that using matrices would change from being somewhat of a pain to being enjoyable to use.

The desire for good matrix support is a motivation for this proposal, but matrices are not synonymous with 2d-slices. A matrix is composed of real or complex numbers and has well-defined operations (multiplication, determinant, Cholesky decomposition). 2d-slices, on the other hand, are merely a rectangular data container. Slices can be of any dimension, hold any data type and do not have any of the additional semantics of a matrix. A matrix can be constructed on top of a 2d-slice in an external package.

A rectangular data container can find use throughout the Go ecosystem. A partial list is

1. Image processing: An image canvas can be represented as a rectangle of colors. Here the ability to efficiently slice in multiple dimensions is important.
2. Machine learning: Typically feature vectors are represented as a row of a matrix. Each feature vector has the same length, and so the additional safety of a full rectangular data structure is useful. Additionally, many fitting algorithms (such as linear regression) give this rectangular data the additional semantics of a matrix, so easy interoperability is very useful.
3. Game development: Go is becoming increasingly popular for the development of games. A player-specific section of a two or three dimensional space can be well represented by an n-dimensional array or a slice of an nd-slice. Two-dimensional slices are especially well suited for representing the game board of tile-based games.

Go is a great general-purpose language, and allowing users to slice a multi-dimensional array will increase the sphere of projects for which Go is ideal.

Language Workarounds

There are several possible ways to emulate a rectangular data structure, each with its own downsides. This section discusses data in two dimensions, but similar problems exist for higher dimensional data.

1. Slice of slices

Perhaps the most natural way to express a two-dimensional slice in Go is to use a slice of slices (for example [][]float64). This construction allows convenient accessing and assignment using the traditional slice access

v := s[i][j]
s[i][j] = v

This representation has two major problems. First, a slice of slices, on its own, has no guarantees about the size of the slices in the minor dimension. Routines must either check that the lengths of the inner slices are all equal, or assume that the dimensions are equal (and accept possible bounds errors). This approach is error-prone for the user and unnecessarily burdensome for the implementer. In short, a slice of slices represents exactly that; a slice of arbitrary length slices. It does not represent data where all of the minor dimension slices are of equal length. Secondly, a slice of slices has a significant amount of computational overhead because accessing an element of a sub-slice means indirecting through a pointer (the pointer to the slice's underlying array). Many programs in numerical computing are dominated by the cost of matrix operations (linear solve, singular value decomposition), and optimizing these operations is the best way to improve performance. Likewise, any unnecessary cost is a direct unnecessary slowdown. On modern machines, pointer-chasing is one of the slowest operations. At best, the pointer might be in the L1 cache. Even so, keeping that pointer in the cache increases L1 cache pressure, slowing down other code. If the pointer is not in the L1 cache, its retrieval is considerably slower than address arithmetic; at worst, it might be in main memory, which has a latency on the order of a hundred times slower than address arithmetic. Additionally, what would be redundant bounds checks in a true 2d-slice are necessary in a slice of slice as each slice could have a different length, and some common operations like 2-d slicing are expensive on a slice of slices but are cheap in other representations.

2. Single slice

A second representation option is to contain the data in a single slice, and maintain auxiliary variables for the size of the 2d-slice. The main benefit of this approach is speed. A single slice avoids some of the cache and index bounds concerns listed above. However, this approach has several major downfalls. The auxiliary size variables must be managed by hand and passed between different routines. Every access requires hand-writing the data access multiplication as well as hand -written bounds checking (Go ensures that data is not accessed beyond the slice, but not that the row and column bounds are respected). Furthermore, it is not clear from the data representation whether the 2d-slice is to be accessed in "row major" or "column major" format

v := a[i*stride + j]     // Row major a[i,j]
v := a[i + j*stride]     // Column major a[i,j]

In order to correctly and safely represent a slice-backed rectangular structure, one needs four auxiliary variables: the number of rows, number of columns, the stride, and also the ordering of the data since there is currently no "standard" choice for data ordering. A community accepted ordering for this data structure would significantly ease package writing and improve package inter-operation, but relying on library writers to follow unenforced convention is a recipe for confusion and incorrect code.

3. Struct type

A third approach is to create a struct data type containing a data slice and all of the data access information. The data is then accessed through method calls. This is the approach used by go.matrix and gonum/matrix.

The struct representation contains the information required for single-slice based access, but disallows direct access to the data slice. Instead, method calls are used to access and assign values.

type Dense struct {
	stride int
	rows   int
	cols   int
	data   []float64
}

func (d *Dense) At(i, j int) float64 {
	if uint(i) >= uint(d.rows) {
		panic("rows out of bounds")
	}
	if uint(j) >= uint(d.cols) {
		panic("cols out of bounds")
	}
	return d.data[i*d.stride+j]
}

func (d *Dense) Set(i, j int, v float64) {
	if uint(i) >= uint(d.rows) {
		panic("rows out of bounds")
	}
	if uint(j) >= uint(d.cols) {
		panic("cols out of bounds")
	}
	d.data[i*d.stride+j] = v
}

From the user's perspective:

v := m.At(i, j)
m.Set(i, j, v)

The major benefits to this approach are that the data are encapsulated correctly -- the data are presented as a rectangle, and panics occur when either dimension is accessed out of bounds -- and that the defining package can efficiently implement common operations (multiplication, linear solve, etc.) since it can access the data directly.

This representation, however, suffers from legibility issues. The At and Set methods when used in simple expressions are not too bad; they are a couple of extra characters, but the behavior is still clear. Legibility starts to erode, however, when used in more complicated expressions

// Set the third column of a matrix to have a uniform random value
for i := 0; i < nCols; i++ {
	m.Set(i, 2, (bounds[1] - bounds[0])*rand.Float64() + bounds[0])
}
// Perform a matrix add-multiply, c += a .* b  (.* representing element-
// wise multiplication)
for i := 0; i < nRows; i++ {
	for j := 0; j < nCols; j++{
		c.Set(i, j, c.At(i,j) + a.At(i,j) * b.At(i,j))
	}
}

The above code segments are much clearer when written as an expression and assignment

// Set the third column of a matrix to have a uniform random value
for i := 0; i < nRows; i++ {
	m[i,2] = (bounds[1] - bounds[0]) * rand.Float64() + bounds[0]
}
// Perform a matrix add-multiply, c += a .* b
for i := 0; i < nRows; i++ {
	for j := 0; j < nCols; j++{
		c[i,j] += a[i,j] * b[i,j]
	}
}

As will be discussed below, this representation also requires a significant API surface to enable performance for code outside the defining package.

Performance

This section discusses the relative performance of the approaches.

1. Slice of slice

The slice of slices approach, as discussed above, has fundamental performance limitations due to data non-locality. It requires n pointer indirections to get to an element of an n-dimensional slice, while in a multi-dimensional slice it only requires one.

2. Single slice

The single-slice implementation, in theory, has performance identical to generalized slices. In practice, the details depend on the specifics of the implementation. Bounds checking can be a significant portion of runtime for index-heavy code, and a lot of effort has gone to removing redundant bounds checks in the SSA compiler. These checks can be proved redundant for both nd-slices and the single slice representation, and there is no fundamental performance difference in theory. In practice, for the single slice representation the compiler needs to prove that the combination i*stride + j is in bounds, while for an nd-slice the compiler just needs to prove that i and j are individually within bounds (since the compiler knows it maintains the correct stride). Both are feasible, but the latter is simpler, especially with the proposed extensions to range.

3. Struct type

The performance story for the struct type is more complicated. Code within the implementing package can access the slice directly, and so the discussion is identical to the above. A user-implemented multi-dimensional slice based on a struct can be made as efficient as the single slice representation, but it requires more than the simple methods suggested above. The code for the benchmarks can be found here. The "(BenchmarkXxx)" parenthetical below refer to these benchmarks. All benchmarks were performed using Go 1.7.3. A table at the end summarizes the results. The example for performance comparison will be the function C += A*B^T. This is a simpler version of the "General Matrix Multiply" at the core of many numerical routines.

First consider a single-slice implementation (BenchmarkNaiveSlices), which will be similar to the optimal performance.

// Compute C += A*B^T, where C is an m×n matrix, A is an m×k matrix, and B
// is an n×k matrix
func MulTrans(m, n, k int, a, b, c []float64, lda, ldb, ldc int){
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			var t float64
			for l := 0; l < k; l++ {
				t += a[i*lda+l] * b[j*lda+l]
			}
			c[i*ldc+j] += t
		}
	}
}

We can add an "AddSet" method (BenchmarkAddSet), and translate the above code into the struct representation.

// Compute C += A*B^T, where C is an m×n matrix, A is an m×k matrix, and B
// is an n×k matrix
func MulTrans(A, B, C Dense) {
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			var t float64
			for l := 0; l < k; l++ {
				t += A.At(i, l) * B.At(j, l)
			}
			C.AddSet(i, j, t)
		}
	}
}

This translation is 500% slower, a very significant cost.

The reason for this significant penalty is that the Go compiler does not currently inline methods that can panic, and the accessors contain panic calls as part of the manual index bounds checks. The next benchmark simulates a compiler with this restriction removed (BenchmarkAddSetNP) by replacing the panic calls in the accessor methods with setting the first data element to NaN (this is not good code, but it means the current Go compiler can inline the method calls and the bounds checks still affect program execution and so cannot be trivially removed). This significantly decreases the running time, reducing the gap from 500% to only 35%.

The final cause of the performance gap is bounds checking. The benchmark is modified so the bounds checks are removed, simulating a compiler with better proving capability than the current compiler. Further, the benchmark is run with -gcflags=-B (BenchmarkAddSetNB). This closes the performance gap entirely (and also improves the single slice implementation by 15%).

However, the initial single slice implementation can be significantly improved as follows (BenchmarkSliceOpt).

for i := 0; i < m; i++ {
	as := a[i*lda : i*lda+k]
	cs := c[i*ldc : i*ldc+n]
	for j := 0; j < n; j++ {
		bs := b[j*lda : j*lda+k]
		var t float64
		for l, v := range as {
			t += v * bs[l]
		}
		cs[j] += t
	}
}

This reduces the cost by another 40% on top of the bounds check removal.

Similar performance using a struct representation can be achieved with a "RowView" method (BenchmarkDenseOpt)

func (d *Dense) RowView(i int) []float64 {
	if uint(i) >= uint(d.rows) {
		panic("rows out of bounds")
	}
	return d.data[i*d.stride : i*d.stride+d.cols]
}

This again closes the gap with the single slice representation.

The conclusion is that the struct representation can eventually be as efficient as the single slice representation. Bridging the gap requires a compiler with better inlining ability and superior bounds checking elimination. On top of a better compiler, a suite of methods are needed on Dense to support efficient operations. The RowView method let range be used, and the "operator methods" (AddSet, AtSet SubSet, MulSet, etc.) reduce the number of accesses.

Compare the final implementation using a struct

for i := 0; i < m; i++ {
	as := A.RowView(i)
	cs := C.RowView(i)
	for j := 0; j < n; j++ {
		bs := b[j*lda:]
		var t float64
		for l, v := range as {
			t += v * bs[l]
		}
		cs[j] += t
	}
}

with that of the nd-slice implementation using the syntax proposed here

for i, as := range a {
	cs := c[i]
	for j, bs := range b {
		var t float64
		for l, v := range as {
			t += v * bs[l]
		}
	}
	cs[j] += t
}

The indexing performed by RowView happens safely and automatically using range. There is no need for the "OpSet" methods since they are automatic with slices. Compiler optimizations are less necessary as the operations are already inlined, and range eliminated most of the bounds checks. Perhaps most importantly, the code snippet above is the most natural way to code the function using nd-slices, and it is also the most efficient way to code it. Efficient code is a consequence of good code when nd-slices are available.

Benchmark	MulTrans (ms)
Naive slice	41.0
Struct + AddSet	207
Struct + Inline	56.0
Slice + No Bounds (NB)	34.9
Struct + Inline + NB	34.1
Slice + NB + Subslice (SS)	21.6
Struct + Inilne + NB + SS	20.6

Recap

The following table summarizes the current state of affairs with 2d data in go

	Correct Representation	Access/Assignment Convenience	Speed
Slice of slice	X	✓	X
Single slice	X	X	✓
Struct type	✓	X	X

In general, we would like our codes to be

1. Easy to use
2. Not error-prone
3. Performant

At present, an author of numerical code must choose one. The relative importance of these priorities will be application-specific, which will make it hard to establish one common representation. This lack of consistency will make it hard for packages to