5 thoughts on “proposal: spec: multidimensional slices

  1. To make progress with this proposal with the goal to come to a decision eventually, here’s an abbreviated summary of the discussion so far.

    Primary goals

    First of all, there are some overarching goals that this proposals attempts to achieve. To name a few (borrowing from #6282 (comment), and #6282 (comment)):

    • It should be straight-forward to write typical numerical algorithms in Go in a natural way.
    • There should be a “standard” mechanism to represent multi-dimensional slices/matrices in Go (one standard way to represent matrices, for instance).
    • Such algorithms should be implementable in a reasonably efficient manner, with a performance coming close to a typical C implementation.

    Virtually everybody also seems to be in agreement with respect to indexing notation and memory layout:

    • Slice/vector/matrix elements should be accessed via the familiar indexing notation, suitably extended to multiple dimensions: v[i], m[i, j], t[i, j, k], etc.

    • A multi-dimensional slice or matrix must be laid out contiguously in memory, without pointers to sub-slices. Successive slice elements may not be adjacent in memory if they have a “stride” that is > 1 (where 1 is the size of a slice element).

    Proposed design

    @btracey, with input from the gonum team, has spent considerable effort coming up with a concrete design for multi-dimensional slices with the intent to address the goals of this proposal: https://github.com/golang/proposal/blob/master/design/6282-table-data.md .
    Thank you @btracey , and the gonum team for your significant effort!

    The above design addresses many of the desired goals of this proposal and, as a significant plus, the proposed multi-dimensional slices are in many ways a natural extension of the one-dim. slices we already have in Go.

    Problem areas

    The single-biggest issue with the proposal is that one-dim. slices don’t have a stride exactly because multi-dim. slices gracefully degrade into Go’s existing slices. This problem has been pointed out as early as #6282 (comment), before a concrete design document was posted. The design document addresses this issue with various work-arounds.

    As a concrete example, given a two-dim. slice m representing a matrix [,]float64, with the proposed design it is easy and efficient (no copy of matrix elements involved) to select a matrix row i as a sub-slice m[i, :] but it is impossible to select a matrix column j that way (m[:, j] is invalid). In other words, indexing is asymmetric, and the asymmetry will lead to special treatment in algorithms (columns must be explicitly copied element-wise).

    To support various “reshaping” operations for multi-dim. slices, the design proposes operations such as reshape, and unshape. @sbinet points out that the design doc has become a bit crowded in terms of additional predeclared functions ( #6282 (comment) ).

    Alternatives

    Several alternative proposals have been floated as well:

    • #6282 (comment) proposes that the std library simply define a standard Matrix format (and perhaps Vectors, etc.).

    • #6282 (comment) proposes a “shaped slice” type for Go which is similar to multi-dimensional slices but supports strides in each dimension, and consequently doesn’t gracefully degrade into a regular (unstrided) slice in the one-dim. case.

    • https://talks.golang.org/2016/prototype-your-design.pdf discusses as an example for that talk the implementation of a rewriter that can automatically rewrite indexing expressions of the form a[i, j, k] and a[i, j, k] = x into method calls a.At(i, j, k), and a.Set(i, j, k, x) respectively. While this approach does not extend the language per se, it permits writing numerical algorithm using “nice” notation which is then automatically translated into regular Go. It also has the advantage of providing full control over the underlying implementation of multi-dim. slices. A complete prototype implementation can be found in https://github.com/griesemer/dotGo2016).

    Summary

    The proposed design of multi-dim. slices is a natural extension of Go’s existing one-dim. slices. From a language point of view, the design appears backward-compatible with Go 1; and it does address many goals of the proposal. That said, the asymmetry of indexing operations requires non-obvious work-arounds when implementing numerical algorithms which runs counter one of the primary goals ( #6282 (comment) ) of this proposal.

  2. I agree with the summary above. Two quick comments (especially for those thinking of making a new proposal)

    • I think any proposal that seeks to extend Go slices will have the same downsides as my proposal. The asymmetry is fundamental, but also I think it is difficult to reduce the scope of the changes without harming the benefits brought by the change. As a simple example, removing unshape and reshape makes it harder to interface multi-dim slices with data streams and C code
    • Another alternative suggestion is to modify Go to allow index operator methods. This would be similar to the talk by @griesemer, except an actual change to the Go spec, and not just a rewriter program.

    Thanks to @griesemer for the significant effort invested in this issue.

  3. Thank you @griesemer — a really good summary of the challenges and benefits.

    To elaborate on my 👍 to @btracey‘s comment above, I especially want to get behind index-operator methods: I suspect that moving index-operator syntax from rewriter-land to native Go would buy considerable power, and would allow libraries to handle more of the heavy-lifting when our implementation preferences diverge (e.g. axis-reordering operations can exist in a library, and needn’t exist in native implementation).

  4. This issue is closed (and the proposal declined) for good reason. If you’re looking for similar functionality, please see the gonum packages (gonum.org)

Comments are closed.