Hacker News Reader

Comment by SamReidHughes | Hacker News Reader

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.

View on HN

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