My name is Herman, and I am here to bust some popular myths about the GO language. The one for today is, “Slice capacity doubles after appending.”

Having served as a hiring manager in over 500 interviews, I often joke, “Juniors claim that slices’ capacity just doubles, Middles say that it doubles, but after reaching a certain length behavior changes…, Seniors say that it doubles, but after reaching a certain length…, but after a specific go’s release formula was changed… All of these explanations are valid as answers, but in reality, everything is a lie!”

Let’s examine the code:

| Output: len=18, cap=36

As we can see, if we create a slice with a length and capacity of 17 and then append to it, we receive a slice with a capacity of 36. However, 17 * 2 equals 34! Moreover, 17 is smaller than 256, which is the threshold in the growslice function in version 1.21.

Let’s dive deeper! We’ll create a function that indicates how many times the capacity doubles and how many times it doesn’t.

| Output: 44

As we can see, the slice capacity doubles only 44 times out of 1000! What’s even more intriguing is that the mythical ‘threshold’ doesn’t always function as expected!

| Output: len=337, cap=672

Wow, 336 * 2 is indeed 672! However, it exceeds the threshold (256) and the result “should be” lower. Alright, let me present some more interesting examples, and then we can dig into the underlying mechanics to understand why it appears so confusing based on our current understanding.

Moreover, why do we always default to using int64? Let’s experiment with something different.

| Output: 28

Ah, now we see it’s related to the data type! Let’s further explore this insight.

| Output: 1

Which iteration is it that gives us this result, you ask? It’s the second one, with both capacity and length equal to 1.

| Output:

| slice: len=1, cap=1

| slice: len=2, cap=2

| slice: len=3, cap=3

| …

It just adds one to the cap every time.

Now we have enough evidence to understand that the capacity doesn’t always double, but only in specific cases. So, how does it work?

Let’s take a closer look at the ‘growslice’ function.

The function calculates the new capacity for the slice. In the initial section of the function, we observe the ‘default’ behavior of capacity growth: if the capacity is lower than the threshold, it will be set to double the current capacity. Otherwise, there is a formula for a smoother growth:

However, the most intriguing segment lies below, within the switch statement based on the size of the slice’s elements. Here, the `capmem` variable shows the amount of memory required to accommodate the new capacity of elements in the slice. This is where the complexity arises. We cannot simply allocate an arbitrary amount of memory, as ‘malloc’ doesn’t operate in that manner. Instead, ‘malloc’ allocates memory based on specific size classes. You can find these size classes here. By the way this code is generated, you can read a source here. The Go team decided to align the memory allocated for the new capacity with these size classes to optimize memory usage. If we request ‘malloc’ to allocate memory for 34 elements of 8 bytes each, it will allocate 288 bytes (36 * 8), because the calculated result depends on the specific size-class. The underlying logic is located here.

As we can see depending on the amount of memory needed to be allocated, amount maps it to one of size classes and then size class maps to the actual amount of memory. In this particular case allocated memory is enough to store 2 additional elements. So why should we lose these elements? Let’s simply add them to our slice. These calculations aim to align the capacity with the amount of memory allocated by ‘malloc’.

As you can observe, the formulas and computation methods vary for different types: those that are equal to the pointer’s size (dependent on the architecture), those with a size of 1 byte, those with a size that is a power of 2, and everything else. However, the concept remains the same across all these cases: calculate the minimum amount of memory required and align it with the results of ‘malloc’s work as closely as possible.

But what about empty structs? The size of an empty struct is 0, which leads to a special case for it.

For slices containing empty structs, slices serve as counters for these empty structs. There’s no need to allocate any memory for ‘data’ in such slices. Consequently, the concept of capacity doesn’t apply; it’s always equal to the current length of the slice.

Lastly, I should mention how `append` functions when we add multiple elements:

Keep in mind that the rules we discovered above are working for this case too. Demonstration.

| Output: 8

Conclusion:

So, now we can finally answer correctly on “how does slice cap grow”. Slice just tries to double the capacity, but reality is tougher.

Now we can show that calculation is based on a lot of factors, not only reaching threshold or not:

• It depends on element type(their size)
• It depends on architecture (bitness i.e. pointer size)
• It depends on current len and cap of slice
• It depends on size of slice(`roundupsize` part)
• It depends on current implementation of ‘malloc’
• It depends on number of elements we append

Author: Herman Samolazov