Then try this one on for size. Very similar, ... but not quite :
package main
import "fmt"
func main() {
// Create a slice of length 1 and capacity 2. Note: try changing this to make([]int, 1, 1) ...
a := make([]int, 1, 2)
// b "aliases" a
b := a
fmt.Printf("%v %v\n", a, b)
a = append(a, 2)
fmt.Printf("%v %v\n", a, b)
b = append(b, 5)
// Question : what does a contain now ?
fmt.Printf("%v %v\n", a, b)
}
Run the program, change the capacity in the make call to 1, and re-run.
If they were values, a and b should simply diverge, so the last line should output [0 2] [0 5].
If they were references, then the last line should output [0 2 5] [0 2 5].
So slices (and maps) are neither values nor references. They're "half-references". Their length is passed as a value, their contents as a reference. Sort of like the linux kernel iovec structures, but completely hidden.
I would say this is a bug, as it violates both ways to think about these values. But it can't be changed without changing the complexity of lists in Go ... so this isn't going to change, and therefore will be declared "not a bug".
I think it's reasonable to ask: "who is this bugging?"
When I was learning Go it took me about 5 minutes to understand how slices work, and I've never had a problem with this behaviour in my work (or my coworkers' work).
Also, it's very rare to see anyone in the #go-nuts IRC asking for help with slices, which leads me to believe that most people don't really have a problem understanding them. You yourself clearly have a solid understanding of them. The semantics are clearly defined in the spec and the internals are easy to understand if you read the docs.
No, they are values that contain a pointer. Think of a struct that contains a pointer. Is that called a 'half-reference'? Take a look at this poor man's slice example using structs and pointers, does it make more sense now?
http://play.golang.org/p/Nnx5Z6DRNo
That's not a difficult problem, the behavior is straightforwardly predictable. append says it will use the same slice until it has no more capacity. A slice reference behaves like it's a pointer, size, and capacity. If you're expecting reference b to "know" about what a has done, or vice versa, the problem is not with the language, it's with you.
> the problem is not with the language, it's with you
You're going too far there. The language already has action-at-a-distance behavior from references: they keep the array from being garbage collected. It would be both entirely possible and straightforwardly predictable to have them update to a new location, or enforce the rule you gave in your other post that there be no other users of the data when you're appending to it.
> It would be both entirely possible and straightforwardly predictable to have them update to a new location,
Only if you expected append to take linear time per usage, and literally just started using it without understanding what it does.
> enforce the rule you gave in your other post that there be no other users of the data when you're appending to it.
Another arbitrary hypothetical where you go using functions you don't understand, but for you to expect this you'd have to expect the language to punish reasonable uses of slices, like sharing the part you've already written and appending after that, and just having a local reference to one in a variable, with linear time behavior per usage. Which also makes it kind of unlikely that one ought to just assume the language works that way.
I can't understand what you wrote. Append is linear time. It could have been amortized O(1), but the Go authors decided that used too much memory so it's O(n) instead, with amortized O(1) behaviour for short slices. Amortized meaning that it's O(1) and then suddenly it's O(n) for one of the calls and then it's O(1) again for a while. But because of the size limit in increases, for large arrays it's O(n), and a fair assessment of the function would only mention the largest bound.
What do you mean that the way append functions is obvious ? Because it doesn't seem obvious to me at all. Do you mean it's obvious to C/assembly programmers ? Obvious to someone who's implemented the Go standard library ?
This means slices work well, until the growth of one slice happens too fast and then, suddenly, your program crawls to a halt (and because it's doing more work, likely requests will pile up and make the offending slice grow even faster, resulting in effectively an infinite loop, and behaviour that is indistinguishable from the scheduler freezing, because now there is ridiculous growth in the number of goroutines).
The rule you gave in the other post is that in Go, everything behaves as a value. None of the complex Go datatypes do that. Slices, maps, interfaces, channels, ... all are half-half reference-value, with curious behaviour resulting from that. Go's simplicity comes from the fact that there are very few advanced datatypes to remember, and that the language makes it utterly impossible to implement any new ones in a reasonable way. So on the one hand you don't have idiots using B+trees where an array would have sufficed, but good luck expressing matrix equations in Go.
No it doesn't. The proof for amortized O(1) only works if you double the array size on every expansion, which only happens until a "ceiling" gets hit and then the slice expands by less.
This results in O(n) complexity.
And this is assuming absense of memory pressure, if there is memory pressure it will very quickly becomes O(n^2) complexity, and god help you if it hits swap.
I had looked at append's behavior when I wrote that post, and for large slices it was increasing the size by 25% each time. That (or any proportion) gives you O(1) amortized time.
Run the program, change the capacity in the make call to 1, and re-run.
If they were values, a and b should simply diverge, so the last line should output [0 2] [0 5].
If they were references, then the last line should output [0 2 5] [0 2 5].
So slices (and maps) are neither values nor references. They're "half-references". Their length is passed as a value, their contents as a reference. Sort of like the linux kernel iovec structures, but completely hidden.
I would say this is a bug, as it violates both ways to think about these values. But it can't be changed without changing the complexity of lists in Go ... so this isn't going to change, and therefore will be declared "not a bug".