Re: [go-nuts] Understanding some gotchas with linking slices together via indexing

[Konstantin Khomoutov]

On Tue, Nov 01, 2022 at 09:38:20PM -0700, Brian, son of Bob wrote:

> Can anyone explain these gotchas (demo )?  
> I've tried reading articles on this [one , 
[...]
> but they don't go into enough detail.


Because that's an intro ;-)

Try reading the next one in the series: https://go.dev/blog/slices

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/20221103144412.7rmrpggsk5gmneir%40carbon.

Re: [go-nuts] Understanding some gotchas with linking slices together via indexing

[Brian, son of Bob]

Thanks!  This has been super informative!

On Thursday, November 3, 2022 at 1:48:49 AM UTC+8 Marvin Renich wrote:

> * Brian, son of Bob  [221102 00:49]:
> > Can anyone explain these gotchas (demo <
> https://go.dev/play/p/g40KMK-zsNk>)? 
> > I've tried reading articles on this [one <
> https://go.dev/blog/slices-intro>, 
> > two 
> > <
> https://codeburst.io/a-comprehensive-guide-to-slices-in-golang-bacebfe46669>] 
>
> > but they don't go into enough detail.
>
> Burak gave a very good, succinct answer to your question. I will give a
> more verbose explanation.
>
> [Short summary at bottom.]
>
> Go does not have a concept of "linked" slices, and does not use that
> terminology. Instead, slices have an _underlying array_, sometimes also
> called a slice's _backing array_. More than one slice can have the same
> backing array, so that changing an element of one slice might change an
> element of another slice.
>
> However, the underlying array for a slice can be changed at any time by
> assignment to the slice, as opposed to assignment to a slice element;
> and this does _not_ change the underlying array for other slices that
> currently use the original underlying array from the first slice. This
> is the primary difference between your concept of "linked slices" and
> the actual behavior of Go.
>
> If you think of a slice as a "view" into its (always fixed-size)
> underlying array, rather than a "variable sized array" you will probably
> have an easier time understanding its behavior. That is, the underlying
> array cannot change size, but the view into it can.
>
> var a = [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} // an array
> var s = a[1:5:7] // a slice with backing array a
> var t = a[3:6] // another slice with the same backing array
> var u = s[2:5] // like t, but limited by the capacity of s
>
> +---+---+---+---+---+---+---+---+---+---+
> a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
> +---+---+---+---+---+---+---+---+---+---+
> ^ ^ ^
> s first last cap
> ^ ^ ^
> t first last cap
> ^ ^ ^
> u first last cap
>
> s[2] = 13 // now t[0] is 13
>
> Assuming x is a slice that has length 5 and capacity 10, the results of
> the following expressions all have the same backing array:
>
> x
> x[:]
> x[0:]
> x[:len(x)]
> x[1:]
> x[:4]
> x[2:4]
> x[3:8]
> x[3:5:7]
>
> The playground link https://go.dev/play/p/tbm97ueCSdP demonstrates that
> all these have the same backing array by creating all the slices as
> named variables, then modifying one element of one of the slices, and
> showing that all the slices have had that corresponding element changed.
>
> In fact, all Slice Expressions as defined at
> https://go.dev/ref/spec#Slice_expressions in the Go Language
> Specification return a slice with the same underlying array as the
> original slice.
>
> There are only a small number of ways to create a slice:
>
> 1. A slice literal.
> 2. The built-in make function.
> 3. A slice expression (as defined in the language spec) applied to a
> slice, array, or pointer to array.
> 4. Assignment or argument passing or returning a result.
> 5. The built-in append function.
>
> Each of these (at least conceptually; the compiler can optimize away
> unnecessary allocations) creates a new slice value (i.e. internal
> structure containing pointer into underlying array, length, and
> capacity). For 1 and 2, a new underlying array is always created. For
> 3 and 4, the underlying array does not change.
>
> The tricky case is 5, where the append function can return a new slice
> with the same underlying array as its first argument, or it may create a
> new underlying array.
>
> This is where capacity comes in. If the original slice has enough
> capacity to hold all the appended elements, the backing array elements
> are modified and the result is a slice with the same backing array. If
> the original slice does not have enough capacity, a new backing array is
> created, and the old slice elements followed by the new slice elements
> (the remaining arguments to append) are copied into it.
>
> Note well that the expression «x = append(x, 9, 8, 7)» is not the same
> as a conceptual «x.append(9, 8, 7)»; that is, it is not appending to the
> variable named x, it is creating a new slice using the value of x and
> then assigning that new slice to x. Whether the new slice has the same
> underlying array as the original depends on the capacity of the
> original.
>
> In your original message, you say that x[0:] and x[:len(x)] are not
> "linked" to x. You are basing that on whether or not append(y, 4)
> modifies x. However, these do share the same backing array as x, but
> append(x[:len(x)], 4) does not (if len(x) == cap(x)). What you are
> seeing is that when len(x) == 3 and cap(x) == 3, and you assign y =
> x[:len(x)-1], then len(y) == 2, but cap(y) == 3, so y has enough
> capacity to append one element, but not two.
>
> The condensed takeaway:
>
> Go does not have any concept that remotely resembles what you are
> thinking of as "linked" slices.
>
> 

Re: [go-nuts] Understanding some gotchas with linking slices together via indexing

[Marvin Renich]

* Brian, son of Bob  [221102 00:49]:
> Can anyone explain these gotchas (demo )?  
> I've tried reading articles on this [one , 
> two 
> ]
>  
> but they don't go into enough detail.

Burak gave a very good, succinct answer to your question.  I will give a
more verbose explanation.

[Short summary at bottom.]

Go does not have a concept of "linked" slices, and does not use that
terminology.  Instead, slices have an _underlying array_, sometimes also
called a slice's _backing array_.  More than one slice can have the same
backing array, so that changing an element of one slice might change an
element of another slice.

However, the underlying array for a slice can be changed at any time by
assignment to the slice, as opposed to assignment to a slice element;
and this does _not_ change the underlying array for other slices that
currently use the original underlying array from the first slice.  This
is the primary difference between your concept of "linked slices" and
the actual behavior of Go.

If you think of a slice as a "view" into its (always fixed-size)
underlying array, rather than a "variable sized array" you will probably
have an easier time understanding its behavior.  That is, the underlying
array cannot change size, but the view into it can.

var a = [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} // an array
var s = a[1:5:7] // a slice with backing array a
var t = a[3:6] // another slice with the same backing array
var u = s[2:5] // like t, but limited by the capacity of s

 +---+---+---+---+---+---+---+---+---+---+
  a  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
 +---+---+---+---+---+---+---+---+---+---+
   ^   ^   ^
  s  first   last cap
   ^   ^   ^
  t  first   last cap
   ^   ^   ^
  u  first   last cap

s[2] = 13 // now t[0] is 13

Assuming x is a slice that has length 5 and capacity 10, the results of
the following expressions all have the same backing array:

x
x[:]
x[0:]
x[:len(x)]
x[1:]
x[:4]
x[2:4]
x[3:8]
x[3:5:7]

The playground link https://go.dev/play/p/tbm97ueCSdP demonstrates that
all these have the same backing array by creating all the slices as
named variables, then modifying one element of one of the slices, and
showing that all the slices have had that corresponding element changed.

In fact, all Slice Expressions as defined at
https://go.dev/ref/spec#Slice_expressions in the Go Language
Specification return a slice with the same underlying array as the
original slice.

There are only a small number of ways to create a slice:

  1.  A slice literal.
  2.  The built-in make function.
  3.  A slice expression (as defined in the language spec) applied to a
  slice, array, or pointer to array.
  4.  Assignment or argument passing or returning a result.
  5.  The built-in append function.

Each of these (at least conceptually; the compiler can optimize away
unnecessary allocations) creates a new slice value (i.e. internal
structure containing pointer into underlying array, length, and
capacity).  For 1 and 2, a new underlying array is always created.  For
3 and 4, the underlying array does not change.

The tricky case is 5, where the append function can return a new slice
with the same underlying array as its first argument, or it may create a
new underlying array.

This is where capacity comes in.  If the original slice has enough
capacity to hold all the appended elements, the backing array elements
are modified and the result is a slice with the same backing array.  If
the original slice does not have enough capacity, a new backing array is
created, and the old slice elements followed by the new slice elements
(the remaining arguments to append) are copied into it.

Note well that the expression «x = append(x, 9, 8, 7)» is not the same
as a conceptual «x.append(9, 8, 7)»; that is, it is not appending to the
variable named x, it is creating a new slice using the value of x and
then assigning that new slice to x.  Whether the new slice has the same
underlying array as the original depends on the capacity of the
original.

In your original message, you say that x[0:] and x[:len(x)] are not
"linked" to x.  You are basing that on whether or not append(y, 4)
modifies x.  However, these do share the same backing array as x, but
append(x[:len(x)], 4) does not (if len(x) == cap(x)).  What you are
seeing is that when len(x) == 3 and cap(x) == 3, and you assign y =
x[:len(x)-1], then len(y) == 2, but cap(y) == 3, so y has enough
capacity to append one element, but not two.

The condensed takeaway:

Go does not have any concept that remotely resembles what you are
thinking of as "linked" slices.

Slices are "views" into a fixed-size array.

Different slices may be views 

Re: [go-nuts] Understanding some gotchas with linking slices together via indexing

[burak serdar]

On Tue, Nov 1, 2022 at 10:49 PM Brian, son of Bob 
wrote:

> Can anyone explain these gotchas (demo )?
> I've tried reading articles on this [one
> , two
> ]
> but they don't go into enough detail.
>
>
> *Slight gotcha #1: arr[:N] only creates a linked slice when N < len(arr)
> and arr[N:] only creates a linked slice when N>0.*
> E.g. `y` is linked here:
> y := x[:len(x) - 1]
> and here:
> y := x[1:]
>
> But not here
> y := x[:len(x)]
> or here:
> y := x[0:]
>

There is no "linked" slice. A slice is simply three values: pointer to an
array, length, and capacity. If x is a slice, then

y:=x[j:k]

means

y.array = [j]
y.cap=x.cap-j
y.len=k-j

So x[0:] is simply equal to x, and x[1:] is a slice that doesn't have the
first element of x.



>
> Also AFAICT, it's impossible create a link to an empty/nil slice unless
> you use pointers.  And I'm not sure if it's possible to create a linked
> slice that looks at all of the elements in the original without using a
> pointer.
>
> I kind of understand where the Go designers were coming from since it is
> probably more efficient to avoid copying all the time.  Though by that
> logic, I'd still think x[0:] would create a linked slice.
>

This is not about efficiency. An array is a fixed-length data structure,
and if you pass arrays around, you'll get copies of it. A slice is a view
of an array.


>
>
> *Gotcha #2: Appending to a linked slice affects the original slice but not
> the other way around*
> E.g. if `y` is linked to `x` via `y :=  x[1:], then:
> - appending to `y` *might* affect x (see Gotcha #3!)
> - appending to `x` won't affect `y`
> If there is a link, why does it not work both ways?
>

Appending to a slice will append the element to the underlying array if the
slice has capacity. Otherwise, it will allocate a larger array, copy the
old one into the new array, and append to the new array. Because of this,
if you do:

x:=append(y,elem)

If y has enough capacity, then both x and y will point to the same array
that will contain elem. If not, a new array will be allocated, elem will be
appended to it, and x will point to that new array while y will continue to
point to the old array.



>
>
> *Gotcha #3: Using variadic args to append to a linked slice doesn't affect
> the other one*
> If `y` is linked to `x` via `y :=  x[:len(x) - 1], then
> - append(y, 1) affects x
> - append(y, 1, 2) doesn't affect x
> I really don't get this one.
>

This is same as the above case.


>
>
>
> Thanks for any insights!
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/7e2b82cc-f5f4-4fe4-ba73-0ff4dead66f7n%40googlegroups.com
> 
> .
>

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/CAMV2Rqr8oJUnO7chga32VK83rP3XQduEfTJnm%3DjwZCno1nFdpw%40mail.gmail.com.