{"action":"created","issue":{"url":"https://api.github.com/repos/golang/go/issues/13253","labels_url":"https://api.github.com/repos/golang/go/issues/13253/labels{/name}","comments_url":"https://api.github.com/repos/golang/go/issues/13253/comments","events_url":"https://api.github.com/repos/golang/go/issues/13253/events","html_url":"https://github.com/golang/go/issues/13253","id":116942756,"number":13253,"title":"Proposal: strided slices","user":{"login":"ianlancetaylor","id":3194333,"avatar_url":"https://avatars.githubusercontent.com/u/3194333?v=3","gravatar_id":"","url":"https://api.github.com/users/ianlancetaylor","html_url":"https://github.com/ianlancetaylor","followers_url":"https://api.github.com/users/ianlancetaylor/followers","following_url":"https://api.github.com/users/ianlancetaylor/following{/other_user}","gists_url":"https://api.github.com/users/ianlancetaylor/gists{/gist_id}","starred_url":"https://api.github.com/users/ianlancetaylor/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ianlancetaylor/subscriptions","organizations_url":"https://api.github.com/users/ianlancetaylor/orgs","repos_url":"https://api.github.com/users/ianlancetaylor/repos","events_url":"https://api.github.com/users/ianlancetaylor/events{/privacy}","received_events_url":"https://api.github.com/users/ianlancetaylor/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2015-11-14T18:11:44Z","updated_at":"2015-11-15T11:09:07Z","closed_at":null,"body":"This proposal is intended as an alternative approach to the ideas discussed in https://golang.org/cl/16801 for #6282.  This is for discussion only at this stage.\r\n\r\nIn Go a slice can be seen as a view into an array of some type T.  The slice defines the start and length of the view.  A slice also has a capacity, but that is mainly relevant when building an array.  Once the size of an array is determined, a slice is a view into that array.\r\n\r\nThis is inconvenient for people who want to deal with multi-dimensional data.  Arguments for this can be found in the links above, and I won't rehearse them here.  What I want to propose here is a different approach to multi-dimensional data.\r\n\r\nGo is a relatively low level language that pays attention to memory layout.  The case we are discussing here is a multi-dimensional view of data that is in fact laid out linearly in memory.  For cases where the data is not laid out linearly, one would naturally use a slice of slices, or some data structure involving pointers.\r\n\r\nI propose adding a new type to the language: a strided slice.  A strided slice of `T` is represented as `[*]T`.  A strided slice has a backing array just as a regular slice does.  However, the strided slice also has a stride, an integer.  Each element of the strided slice is not a single element of the backing array, but the number of elements described by the stride.  Indexing into a strided slice thus produces a slice.\r\n\r\nA strided slice is created from an array or slice using a strided slice expression, whose syntax is `*[stride]`.  The strided slice starts at the beginning of the array or slice, and its length is determined by dividing the length of the array or slice by the stride using a truncating division.  A strided slice has no capacity (or, if you prefer, the capacity equals the length).  Given an array `[N]T` or slice `[]T`, a strided slice expression produces a strided slice of type `[*]T`.\r\n\r\nIn the type `[*]T` `T` can itself be a strided slice.  For convenience we speak of the _arity_ of a strided slice.  The arity of `[*]T` is 1 if `T` is not a strided slice.  Otherwise, it is the arity of `T` plus 1.  The arity is the number of strides in the strided slice.  To be clear: `[]int` is a normal slice, which could be said to have arity 0.  `[*]int` is a strided slice of arity 1.  `[*][*]int` is a strided slice of arity 2.\r\n\r\nIn the following let's suppose we have an array or slice `a` of type `T`.  Let's suppose we write `ss := a*[S]`, giving us a strided slice of stride `S` and arity 1.\r\n\r\nA strided slice can be used in an index expression.  The result is type `[]T`.  The expression `ss[i]` is equivalent to `a[i*S:(i+1)*S:(i+1)*S]`.  Bounds errors are checked just as for that slice expression.  This value is not addressable and is not an lvalue.  In fact, that is true of all expressions on a strided slice.\r\n\r\nA strided slice can be used in a slice expression with two elements, producing a value of type `[*]T`.  The expression `ss[i:j]` is equivalent to `a[i*S:j*S]*[S]`.\r\n\r\nA strided slice can be used in a strided slice expression, producing a value of type `[*][*]T`, which is a strided slice of arity 2.  The expression `ss*[S2]` produces a strided slice whose first stride is `S2` and whose second stride is `S`.\r\n\r\nNow we discuss how these operations work on a strided slice of arity `N` where `N > 1`.  Again the type is `[*]T`, but `T` is itself a strided slice.  Assume we have `ss := a*[S]*[S2]*[S3]...` for some sequence of `S2 S3...`.\r\n\r\nThe expression `ss[i]` produces a slice of strided slices of type `[]T`.  It is equivalent to `a[i*S:(i+1)*S]*[S2]*[S3]...`.\r\n\r\nThe expression `ss[i:j]` produces a value of type `[*]T`.  It is equivalent to `a[i*S:j*S]*[S]*[S2]*[S3]...`.\r\n\r\nThe expression `ss*[S0]` produces a value of type `[*][*]T`.  This produces a strided slice of arity `N + 1` whose first stride is `S0`, with following strides `S`, `S2`, `S3`, ....\r\n\r\nA strided slice may be used in a range statement.  There are two forms.  In the usual form, the range produces two values: an index into the strided slice and the result of the equivalent index expression (which will be a slice or strided slice).  In the longer form, it may be used with exactly `N + 2` values.  The first value is the index using the outermost stride, then the index of the next stride, and so on.  The penultimate value is the index into the normal slice that is the result of indexing into the final strided slice.  The final value is the value in the underlying array.\r\n\r\nThe predeclared function `len` applied to a strided slice returns the number of valid indexes.  For a strided slice of arity 1 and stride `S` and backing array `a`, this is `len(a)/S` using a truncating division.\r\n\r\nThe predeclared functions `cap` and `append` may not be applied to a strided slice.\r\n\r\nA new predeclared function `stride` returns the stride of a strided slice, a value of type `int`.\r\n\r\n## Examples\r\n\r\nHere are a couple of examples of using strided slices.\r\n\r\n    // A 4x3 matrix.\r\n    a := []int{1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3}\r\n    for i, j, v := range a*[4] {\r\n       fmt.Printf(\"%d %d %d \", i, j, v)\r\n    }\r\n\r\n    // Matrix multiplication.\r\n    // m1 is d1 x d2, m2 is d2 x d3, producing d1 x d3 matrix.\r\n    func matmult(m1, m2 []int, d1, d2, d3 int) []int {\r\n        r := make([]int, d1 * d3)\r\n        ss1 := m1*[d2]\r\n        ss2 := m2*[d3]\r\n        ssr := r*[d3]\r\n        for i := 0; i < d1; i++ {\r\n            for j := 0; j < d3; j++ {\r\n                for k := 0; k < d2; k++ {\r\n                    ssr[i][j] += ss1[i][k] * ss2[k][j]\r\n                }\r\n            }\r\n        }\r\n        return ssr\r\n    }\r\n\r\n## Implementation\r\n\r\nA strided slice of arity 1 has a backing array, a length, and a stride.  Thus the internal representation looks exactly like a normal slice, with the capacity field replaced by a stride field.\r\n\r\nA strided slice of arity 2 has a backing array, a length, and two strides.  In general, the internal representation of a strided slice of arity N is\r\n    struct {\r\n        array *T\r\n        len int\r\n        stride [N]int\r\n    }\r\n\r\nThe compiler always knows the arity of any given slice, so implementing the index and slice expressions is straightforward.\r\n\r\n## Rationale\r\n\r\nStrided slices provide a general way to implement multi-dimensional arrays with no limit on the number of dimensions.  They provide a flexible way to access linear data in multiple dimensions without requiring hard coded sizes or explicit multiplication.  They are a natural extension of the slice concept into multiple dimensions."},"comment":{"url":"https://api.github.com/repos/golang/go/issues/comments/156802482","html_url":"https://github.com/golang/go/issues/13253#issuecomment-156802482","issue_url":"https://api.github.com/repos/golang/go/issues/13253","id":156802482,"user":{"login":"somadivad","id":8932697,"avatar_url":"https://avatars.githubusercontent.com/u/8932697?v=3","gravatar_id":"","url":"https://api.github.com/users/somadivad","html_url":"https://github.com/somadivad","followers_url":"https://api.github.com/users/somadivad/followers","following_url":"https://api.github.com/users/somadivad/following{/other_user}","gists_url":"https://api.github.com/users/somadivad/gists{/gist_id}","starred_url":"https://api.github.com/users/somadivad/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/somadivad/subscriptions","organizations_url":"https://api.github.com/users/somadivad/orgs","repos_url":"https://api.github.com/users/somadivad/repos","events_url":"https://api.github.com/users/somadivad/events{/privacy}","received_events_url":"https://api.github.com/users/somadivad/received_events","type":"User","site_admin":false},"created_at":"2015-11-15T11:09:07Z","updated_at":"2015-11-15T11:09:07Z","body":"The following are a couple of features that are important in machine learning applications, and that I would be interested to understand whether strided slices can support. (These features are supported by numpy ndarrays and torch tensors, for example.)\r\n- The ability to manipulate the \"shape\" of the multi-dimensional array on the same underlying data. For example, given a 30 slice, to construct a 5*6 slice on the same data; given a 5*6 slice, to construct a 6*5 slice which represents the transpose. These are all operations which amount to having different strides on the same data.\r\n- The ability to subslice along any dimension, not only the first. For example, given a h*w slice, to select either a h' * w subslice or a h * w' subslice or a h' * w' subslice."}}