Slice with a Pinch of Salt?

Go is unlike any other language. Often programmers have a muscle-memory of doing certain things in a certain way in their native language — like Python, Ruby, Javascript, etc. — and they try to re-apply the same in Go, and end up feeling skeptical about the whole idea. Well, Go is different! It is swift like others, but is also capable as a system programming language.

One such case is the Slice [1] specification in Go.

Most languages, like Python, create another copy of the underlying array when any of the slices pointing to it does a write. This is classic Copy-on-Write (CoW) operation.

Go takes a more lean and lazy approach in doing this. It keeps modifying the same underlying array until the capacity of a slice is reached. What do we call this, Copy-on-Capacity-Overload (CoCO)?

Yes, this could be a weird semantic, and seems to be implementation specific. Strangely, the spec only defines limited behavior (as below), and does not say much on how multiple slices may or may not refer to same underlying array depending on when the append hits capacity. More on this after the examples.

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large underlying array that fits both the existing slice elements and the additional values. Otherwise, append re-uses the underlying array. [1]

Let us first see how Python behaves when it comes to slices. Below is an example in IPython shell.

In [1]: a=[0, 0, 0, 0, 0]

In [2]: b=a[:4]

In [3]: a
Out[3]: [0, 0, 0, 0, 0]

In [4]: b
Out[4]: [0, 0, 0, 0]

In [5]: b.append(1)

In [6]: a
Out[6]: [0, 0, 0, 0, 0]

In [7]: b
Out[7]: [0, 0, 0, 0, 1]

In steps 5, 6 and 7, it is quite evident that a Copy-on-Write has happened. Both slices represent different underlying array as soon as the append is done to a slice.

Now, let us look at the Go behavior with slices. The output is more interesting, the code is plain simple. May want to jump to the output!

You can try hands-on on the code at Go Playground.

The output is self-explanatory showing the allocation of new underlying array when the capacity of the current underlying array is reached.

Go Slice Example: Copy-on-Capacity-Overload

Slice a len=7 cap=7 [0 0 0 0 0 0 0]
Slice b refers to the 2, 3, 4 indices in slice a. Hence, the capacity is 5 (= 7-2).
b := a[2:5]
Slice b len=3 cap=5 [0 0 0]

Modifying slice b, also modifies a, since they are pointing to the same underlying array.
b[0] = 9
Slice a len=7 cap=7 [0 0 9 0 0 0 0]
Slice b len=3 cap=5 [9 0 0]

Appending 1 to slice b. Overwrites a.
Slice a len=7 cap=7 [0 0 9 0 0 1 0]
Slice b len=4 cap=5 [9 0 0 1]

Appending 2 to slice b. Overwrites a.
Slice a len=7 cap=7 [0 0 9 0 0 1 2]
Slice b len=5 cap=5 [9 0 0 1 2]

Appending 3 to slice b. Here, a new copy is made as the capacity is overloaded.
Slice a len=7 cap=7 [0 0 9 0 0 1 2]
Slice b len=6 cap=12 [9 0 0 1 2 3]

Verifying slices a and b point to different underlying arrays after the capacity-overload in the previous step.
b[1] = 8
Slice a len=7 cap=7 [0 0 9 0 0 1 2]
Slice b len=6 cap=12 [9 8 0 1 2 3]

Here, in the last verification-step, it feels a bit spooky that any modification to b is no more causing modification to the underlying array pointed to by a. A logical expectation would be that: when b hits the limit, a and b both point to the same newly allocated underlying array, instead of a continuing to point to the older one. This transparent renewal of underlying memory is strange and could be very difficult to debug when encountered — it could lead to an unseen race-condition, too.

Now, what could be the reason for prevailing such a semantic? The answer could be in the design-goals of the language: Concurrency. This nature of the slice-semantics does the reallocation of memory only for the slice that requested extra memory. All other slices, need not be blocked on this operation since they do not point to same memory any more. This does seem to have lesser lock-contention, and hence, added performance compared to other languages. If sufficient care is taken by maintaining proper idioms while programming, this could be advantageous — for example, using slices for merely opening a “window” on the array, such that an “in-built append” is almost never performed on such a slice, and only a “safe Append” is called when absolutely needed.

Other languages too have this powerful concept of slice, but Go keeps it simple and silly, giving all the liberty and raw-power to the programmer by not hiding everything under the hood. One might argue that Go does not have the Slice abstraction with total and complete transparency, and that it is bad API. But, that’s how it is at least in today’s date. On a positive note, it gives more control and visibility to the programmer on how the data is getting handled in the memory that is essential for system programming.

Thus, Go provides a lower-level abstraction of the slices. The power of this is that the programmer can provide his/her own dynamic arrays implementation. One way of doing this is: When an append is going to spill over, create a new slice of twice the size, copy the elements in old slice to new slice, append the new data to the new slice, and return the new slice. The old slice will be purged by the garbage-collector when no reference is left pointing to it. This is how dynamic arrays are implemented in other languages behind the scenes!

One such implementation (safe Append) [2]:

A few more gotchas! A slice cannot be grown beyond its capacity. Attempting to do this results in runtime panic same as accessing index out of array bounds. Also, negative slices of reversed ranges cannot be created to access earlier elements.

Happy coding!

References:

[1] The Go Programming Language Specification [link]

[2] Effective Go [link]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s