6 ms·

I don't know much Go but what does it mean to "accidentally" append to an immutable array? Are there just no particular guards for arrays and they are saying so

by gleenn 4y ago

I don't know much Go but what does it mean to "accidentally" append to an immutable array? Are there just no particular guards for arrays and they are saying something which should be treated as immutable?

UncleEntity 4y ago
I know even less go but it sounds like it prevents accidentally writing past the end of the array by making a copy and appending to that.
tedunangst 4y ago
There are no immutable arrays. If you have a slice of capacity ten with four elements, you can write a fifth element to it. If you reduce the capacity to four, then a new slice must be allocated to store five elements. The backing store for a slice is just a pointer. The rule is you don't give people pointers that you don't want them to write to.
- andrewstuart2 4y ago
  That's just not true. There are immutable arrays in length. [4]int cannot be appended to. The backing of all slices are array types and array doubling is used for appends that go beyond the capacity. https://go.dev/ref/spec#Array_types https://go.dev/ref/spec#Array_types
  - tedunangst 4y ago
    Yeah, that was a mistake.
  - yencabulator 4y ago
    No array can change its length, the length is part of the type. There really are no "immutable array"s.
Groxx 4y ago
Append mutates or copies-and-appends based on the capacity of the slice it's given. And since slicing an array or a slice gives you just a view, not a copy, it can cause "spooky action at a distance" and mutate things you didn't expect, especially if it was a slice with extra capacity of data used somewhere else. Which is what this article is describing. Plus the knowledge of the change in length (to see the appended data) is only visible with the returned slice (a new view with the larger length), but the underlying data is changed either way. It's not often a source of errors, but when it is it can be extremely hard to diagnose.
- DougBTX 4y ago
  So in other words, appending to a slice may overwrite data in the middle of a different slice?
  - Groxx 4y ago
    Yep. Depending on how the slice was constructed, not how it is used. Slices (largely) behave like this in most languages, Go's contribution is mostly that slices and append are ubiquitous, so pretty much every Go coder is exposed to it. Prior to generics, literally any alternative was so much more work they essentially haven't been used. That may change in the future now that we do have (very simplistic) generics, but only time will tell.
    - iainmerrick 4y ago
      Slices (largely) behave like this in most languages Is that really the case? I can’t think of many languages that let you construct a view into the middle of array, pass that view as an argument to a function call, and allow that function to add new values into your array via the view. In Python or JS, for example, the “slice” would just be a brand new array, right?
      - Groxx 4y ago
        If the slice syntax creates a copy, I would argue that it's simply syntactic sugar for array copying, not actually producing a slice (i.e. there is no slice type). But yes, `somefunc(ary[1:])` in Python produces a copy, not a reference to the underlying value. You could build a more "true" slice class, but the builtin stuff doesn't do that. JavaScript is similar. Java however has `List<>.sublist` which largely behaves like Go: https://docs.oracle.com/javase/8/docs/api/java/util/List.html#subList-int-int- https://docs.oracle.com/javase/8/docs/api/java/util/List.htm... . Sometimes these kinds of things are also referred to as "views". Go calls them slices though, and this is a Go article. edit: C# apparently has "spans": https://learn.microsoft.com/en-us/archive/msdn-magazine/2018/january/csharp-all-about-span-exploring-a-new-net-mainstay https://learn.microsoft.com/en-us/archive/msdn-magazine/2018...
TwentyPosts 4y ago
Go has no way to ensure "const correctness". If you pass around a slice (which you'll be doing a lot, since it's essentially Go's equivalent of a vector), everyone can modify the slice however they please. It's just a fat pointer. So yes, something which should be treated as immutable. The way Go works here easily leads to bugs, especially when concurrency is involved and slices get captured or used by goroutines. If you send a slice to a function, they essentially receive a pointer pointing at the same block of memory as in your calling function. They can modify it. If they append to the slice, however, and surpass the capacity of the slice they received, then their slice gets reallocated and doesn't point at the same block of memory anymore. In other words, if you receive a slice, append to it, and then change the first value of the slice, then this might modify a slice (or array) somewhere completely different, depending on whether your append surpasses the allocated capacity of the slice or not. Welcome to Golang.
- Groxx 4y ago
  But also strings are actually immutable sometimes (at the very least when hardcoded), and they can be converted to a `[]byte` slice that looks mutable, but panics when modified. AFAIK no other slice-like data in Go behaves like this. Fun!
  - wyager 4y ago
    This is a pretty good vignette of how Go is designed. "Users don't need this feature (immutability, polymorphism, etc.), let's not include it. Ah crap, turns out we actually need it for a core language feature. Is there a lesson we can take away here? Nah, just make an ad-hoc implementation of the functionality in this one place."
    - Groxx 4y ago
      "X for me but not for thee" is very much the vibe Go gives me, yeah. I mean, I have completely replaced my adhoc Python use with it and I'm much happier. But it's terrifying to use to build large systems.
chrsig 4y ago
Here's a succinct demonstration: https://go.dev/play/p/Li6_Rpe2R5L https://go.dev/play/p/Li6_Rpe2R5L Basically: a slice is a triple of {ptr to allocation, number of elements used, size of allocation} the slices will share the same underlying allocation. By specifying the third parameter in the slice function, you set the capacity equal to the number of elements in your slice. This forces the next append to reallocate and copy the contents into a new region. Without bounding the capacity when creating a new slice, the append operation could possibly continue using the same allocation, shared with the original slice. It could possibly resize and copy as well. It depends on how full the slice is, and is an implementation detail subject to change between versions.
- ErikCorry 4y ago
  Here another illustration of how slices sometimes alias each other, sometimes not. https://mobile.twitter.com/erikcorry/status/1561635841495236610 https://mobile.twitter.com/erikcorry/status/1561635841495236...
  - secondraft 4y ago
    and yet another one (thanks to Erik): https://github.com/tlk/go-wat/blob/41cc21294a953dc7ad07a9b40a2486acf816b8e1/main.go#L27 https://github.com/tlk/go-wat/blob/41cc21294a953dc7ad07a9b40...
Izkata 4y ago
Sounds like they're just badly describing copy-on-write. The original slice uses no extra memory because as long as you treat it as immutable it won't actually make a copy. As soon as you try to modify it, then the copy is made and the extra memory used.
- deleted 4y ago
  [deleted]
- mook 4y ago
  Yes-ish; because go has no immutable slices, it's just copy-on-realloc. Which is if course obvious if realize that's what it's actually doing…
- masklinn 4y ago
  > Sounds like they're just badly describing copy-on-write. It’s not quite copy-on-write, and what it’s really describing is a workaround / safeguard. The problem is that by default Go slices will have as large a capacity as they can based on the parent, this is a problem if you return a slice to a still-in-use slice or array, and the caller decides to use that slice as a vector (either because the contract is not well documented or because they fucked up): appending to the “borrow” will happily go and stomp over the backing array, which may be holding in-use data of an other slice or the original array. By forcing the slice to have no extra capacity, if a caller tries to append it’ll force a “fork” by realloc-ing and avoid the issue.

by gleenn 4y ago

UncleEntity 4y ago

I know even less go but it sounds like it prevents accidentally writing past the end of the array by making a copy and appending to that.

tedunangst 4y ago

There are no immutable arrays. If you have a slice of capacity ten with four elements, you can write a fifth element to it. If you reduce the capacity to four, then a new slice must be allocated to store five elements. The backing store for a slice is just a pointer. The rule is you don't give people pointers that you don't want them to write to.

andrewstuart2 4y ago
That's just not true. There are immutable arrays in length. [4]int cannot be appended to. The backing of all slices are array types and array doubling is used for appends that go beyond the capacity. https://go.dev/ref/spec#Array_types https://go.dev/ref/spec#Array_types
- tedunangst 4y ago
  Yeah, that was a mistake.
- yencabulator 4y ago
  No array can change its length, the length is part of the type. There really are no "immutable array"s.

Groxx 4y ago

Append mutates or copies-and-appends based on the capacity of the slice it's given. And since slicing an array or a slice gives you just a view, not a copy, it can cause "spooky action at a distance" and mutate things you didn't expect, especially if it was a slice with extra capacity of data used somewhere else. Which is what this article is describing. Plus the knowledge of the change in length (to see the appended data) is only visible with the returned slice (a new view with the larger length), but the underlying data is changed either way. It's not often a source of errors, but when it is it can be extremely hard to diagnose.

DougBTX 4y ago
So in other words, appending to a slice may overwrite data in the middle of a different slice?
- Groxx 4y ago
  Yep. Depending on how the slice was constructed, not how it is used. Slices (largely) behave like this in most languages, Go's contribution is mostly that slices and append are ubiquitous, so pretty much every Go coder is exposed to it. Prior to generics, literally any alternative was so much more work they essentially haven't been used. That may change in the future now that we do have (very simplistic) generics, but only time will tell.
  - iainmerrick 4y ago
    Slices (largely) behave like this in most languages Is that really the case? I can’t think of many languages that let you construct a view into the middle of array, pass that view as an argument to a function call, and allow that function to add new values into your array via the view. In Python or JS, for example, the “slice” would just be a brand new array, right?
    - Groxx 4y ago
      If the slice syntax creates a copy, I would argue that it's simply syntactic sugar for array copying, not actually producing a slice (i.e. there is no slice type). But yes, `somefunc(ary[1:])` in Python produces a copy, not a reference to the underlying value. You could build a more "true" slice class, but the builtin stuff doesn't do that. JavaScript is similar. Java however has `List<>.sublist` which largely behaves like Go: https://docs.oracle.com/javase/8/docs/api/java/util/List.html#subList-int-int- https://docs.oracle.com/javase/8/docs/api/java/util/List.htm... . Sometimes these kinds of things are also referred to as "views". Go calls them slices though, and this is a Go article. edit: C# apparently has "spans": https://learn.microsoft.com/en-us/archive/msdn-magazine/2018/january/csharp-all-about-span-exploring-a-new-net-mainstay https://learn.microsoft.com/en-us/archive/msdn-magazine/2018...

TwentyPosts 4y ago

Go has no way to ensure "const correctness". If you pass around a slice (which you'll be doing a lot, since it's essentially Go's equivalent of a vector), everyone can modify the slice however they please. It's just a fat pointer. So yes, something which should be treated as immutable. The way Go works here easily leads to bugs, especially when concurrency is involved and slices get captured or used by goroutines. If you send a slice to a function, they essentially receive a pointer pointing at the same block of memory as in your calling function. They can modify it. If they append to the slice, however, and surpass the capacity of the slice they received, then their slice gets reallocated and doesn't point at the same block of memory anymore. In other words, if you receive a slice, append to it, and then change the first value of the slice, then this might modify a slice (or array) somewhere completely different, depending on whether your append surpasses the allocated capacity of the slice or not. Welcome to Golang.

Groxx 4y ago
But also strings are actually immutable sometimes (at the very least when hardcoded), and they can be converted to a `[]byte` slice that looks mutable, but panics when modified. AFAIK no other slice-like data in Go behaves like this. Fun!
- wyager 4y ago
  This is a pretty good vignette of how Go is designed. "Users don't need this feature (immutability, polymorphism, etc.), let's not include it. Ah crap, turns out we actually need it for a core language feature. Is there a lesson we can take away here? Nah, just make an ad-hoc implementation of the functionality in this one place."
  - Groxx 4y ago
    "X for me but not for thee" is very much the vibe Go gives me, yeah. I mean, I have completely replaced my adhoc Python use with it and I'm much happier. But it's terrifying to use to build large systems.

chrsig 4y ago

Here's a succinct demonstration: https://go.dev/play/p/Li6_Rpe2R5L https://go.dev/play/p/Li6_Rpe2R5L Basically: a slice is a triple of {ptr to allocation, number of elements used, size of allocation} the slices will share the same underlying allocation. By specifying the third parameter in the slice function, you set the capacity equal to the number of elements in your slice. This forces the next append to reallocate and copy the contents into a new region. Without bounding the capacity when creating a new slice, the append operation could possibly continue using the same allocation, shared with the original slice. It could possibly resize and copy as well. It depends on how full the slice is, and is an implementation detail subject to change between versions.

ErikCorry 4y ago
Here another illustration of how slices sometimes alias each other, sometimes not. https://mobile.twitter.com/erikcorry/status/1561635841495236610 https://mobile.twitter.com/erikcorry/status/1561635841495236...
- secondraft 4y ago
  and yet another one (thanks to Erik): https://github.com/tlk/go-wat/blob/41cc21294a953dc7ad07a9b40a2486acf816b8e1/main.go#L27 https://github.com/tlk/go-wat/blob/41cc21294a953dc7ad07a9b40...

Izkata 4y ago

Sounds like they're just badly describing copy-on-write. The original slice uses no extra memory because as long as you treat it as immutable it won't actually make a copy. As soon as you try to modify it, then the copy is made and the extra memory used.

deleted 4y ago
[deleted]
mook 4y ago
Yes-ish; because go has no immutable slices, it's just copy-on-realloc. Which is if course obvious if realize that's what it's actually doing…
masklinn 4y ago
> Sounds like they're just badly describing copy-on-write. It’s not quite copy-on-write, and what it’s really describing is a workaround / safeguard. The problem is that by default Go slices will have as large a capacity as they can based on the parent, this is a problem if you return a slice to a still-in-use slice or array, and the caller decides to use that slice as a vector (either because the contract is not well documented or because they fucked up): appending to the “borrow” will happily go and stomp over the backing array, which may be holding in-use data of an other slice or the original array. By forcing the slice to have no extra capacity, if a caller tries to append it’ll force a “fork” by realloc-ing and avoid the issue.