为什么奇数的分片容量与偶数的行为不同 [英] Why does slice capacity with odd numbers differ from behavior with even numbers

问题描述

我注意到，当容量是奇数时，切片的容量会有不同的表现。更具体地说：当一个元素被添加到切片时，当原始容量是偶数时切片的容量被加倍。但是，当原始容量是奇数时，容量会增加1，然后增加一倍。例子：

  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）
  

假设这不是一个bug，这种行为的原因是什么？

链接到游乐场： http://play.golang.org/p/wfmdobgCUF

解决方案

< h2>简短回答

它正在调整分片容量以填充已分配的内存块。

长答案

让我们来看一下Go1.5.1的源代码：

https://github.com/golan g / go / blob / f2e4c8b5fb3660d793b2c545ef207153db0a34b1 / src / cmd / compile / internal / gc / walk.go＃L2895 告诉我们 append（l1，l2 ...）扩展为



  s：= l1 
。 - 帽子; n> 0 {
s = growslice_n（s，n）
} 
s = s [：len（l1）+ len（l2）] 
 memmove（& s [len（l1） ]，& l2 [0]，len（l2）* sizeof（T））
  

我们感兴趣的是， growslice_n ，在那里定义： https://github.com/golang/go/blob/f2e4c8b5fb3660d793b2c545ef207153db0a34b1/src/runtime/slice.go#L36

再深入一点，我们发现：

  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 
 
 
 
 $ b / * [...] * / 
 
 capmem：= roundupsize（uintptr（newcap）* uintptr（ et.size））
 newcap = int（capmem / uintptr（et.size））
  

roundupsize 定义在那里： https://github.com/golang/go/blob/f2e4c8b5fb3660d793b2c545ef207153db0a34b1/src/runtime/msize.go#L178

  //返回mallocgc将分配的内存块的大小，如果您要求大小。 
 func roundupsize（size uintptr）uintptr {
 if size< _MaxSmallSize {
 if size< = 1024-8 {
 return uintptr（class_to_size [size_to_class8 [（size + 7）>> 3]]）
} else {
返回uintptr（class_to_size [size_to_class128 [（size-1024 + 127）>> 7]]）
} 
} 
 if size + _PageSize<大小{
返回大小
} 
返回圆形（大小，_PageSize）
} 
  

它在那里推出： https://groups.google。 com / forum /＃！topic / golang-codereviews / bFGtI4Cpb_M

当增长片考虑分配内存的大小时块。

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

解决方案

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.

这篇关于为什么奇数的分片容量与偶数的行为不同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！