Comment by waps | Hacker News Reader

Comment by waps | Hacker News Reader

Parent Full thread

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)
  }

http://play.golang.org/p/Hf2noTyNrp

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.

> "know"

> 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.

Lots of ways to do it, wouldn't have to be linear time.

>for you to expect this

Oh, no, I wouldn't expect it to enforce a rule like that by default, but it would be a good thing to do when the behavior is so unpredictable.

>sharing the part you've already written and appending after that

You could require an immutable slice for that, in the situations where append is the most reasonable option.

Anyway I'm not trying to suggest this method. I'm just giving an example to support the idea that it could do something predictable.

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.

Append has amortized O(1) time at all slice sizes.

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.

Really ? I thought it was limited to something like a fixed number of megabytes increase per call.

Appending to a slice I get these capacities:

  cap:  1
  cap:  2
  cap:  4
  ...
  cap:  512
  cap:  1024
  cap:  1312
  cap:  1696
  cap:  2208
  cap:  3072
  cap:  4096
  cap:  5120
  cap:  7168
  ...
  cap:  192797696
  cap:  240997376

So it looks like it starts by doubling, then it gets weird between 1024 and 4096, and then it multiplies by 1.25.

Reply on news.ycombinator.com