Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does slice capacity with odd numbers differ from behavior with even numbers

Tags:

slice

go

I noticed that the capacity of slices behaves in a different way, when the capacity is an odd number. More specifically: When an element is added to a slice, the capacity of the slice is doubled when the original capacity was an even number. But when the original capacity was an odd number, the capacity is incremented by one and then doubled. Example:

s := make([]int, 28, 28)
s = append(s, 1) 
fmt.Println("len=", len(s), " cap=", cap(s)) // len = len + 1, cap = 2 * cap


pri := make([]int, 27, 27)
pri = append(pri, 1)
fmt.Println("len=", len(pri), " cap=", cap(pri)) // len = len + 1, cap = 2 * (cap + 1)  

Assuming this is not a bug, what's the reason for this behavior?

Link to playground: http://play.golang.org/p/wfmdobgCUF

like image 208
Jan Wy Avatar asked Oct 07 '15 14:10

Jan Wy


1 Answers

Short answer

It is rounding up the slice capacity to fill the allocated memory blocks.

Long answer

Let's have a look into the Go1.5.1 source code :

https://github.com/golang/go/blob/f2e4c8b5fb3660d793b2c545ef207153db0a34b1/src/cmd/compile/internal/gc/walk.go#L2895 tells us that append(l1, l2...) is expanded to

s := l1
if n := len(l1) + len(l2) - cap(s); n > 0 {
    s = growslice_n(s, n)
}
s = s[:len(l1)+len(l2)]
memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))

The part we are interested in, growslice_n, is defined there : https://github.com/golang/go/blob/f2e4c8b5fb3660d793b2c545ef207153db0a34b1/src/runtime/slice.go#L36

Going a bit deeper, we find this :

newcap := old.cap
if newcap+newcap < cap {
    newcap = cap
} else {
    for {
        if old.len < 1024 {
            newcap += newcap
        } else {
            newcap += newcap / 4
        }
        if newcap >= cap {
            break
        }
    }
}

/* [...] */

capmem := roundupsize(uintptr(newcap) * uintptr(et.size))
newcap = int(capmem / uintptr(et.size))

roundupsize is defined there : https://github.com/golang/go/blob/f2e4c8b5fb3660d793b2c545ef207153db0a34b1/src/runtime/msize.go#L178

// Returns size of the memory block that mallocgc will allocate if you ask for the size.
func roundupsize(size uintptr) uintptr {
    if size < _MaxSmallSize {
        if size <= 1024-8 {
            return uintptr(class_to_size[size_to_class8[(size+7)>>3]])
        } else {
            return uintptr(class_to_size[size_to_class128[(size-1024+127)>>7]])
        }
    }
    if size+_PageSize < size {
        return size
    }
    return round(size, _PageSize)
}

And it was introduced there : https://groups.google.com/forum/#!topic/golang-codereviews/bFGtI4Cpb_M

When growing slice take into account size of the allocated memory block.

like image 103
HectorJ Avatar answered Oct 13 '22 20:10

HectorJ