惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

B
Blog RSS Feed
D
Darknet – Hacking Tools, Hacker News & Cyber Security
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
G
Google Developers Blog
MyScale Blog
MyScale Blog
Google DeepMind News
Google DeepMind News
J
Java Code Geeks
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
C
Check Point Blog
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
P
Proofpoint News Feed
D
Docker
Jina AI
Jina AI
博客园 - 三生石上(FineUI控件)
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
Help Net Security
Help Net Security
Google DeepMind News
Google DeepMind News
L
LINUX DO - 最新话题
T
Tailwind CSS Blog
N
Netflix TechBlog - Medium
Forbes - Security
Forbes - Security
MongoDB | Blog
MongoDB | Blog
Attack and Defense Labs
Attack and Defense Labs
Webroot Blog
Webroot Blog
A
About on SuperTechFans
Schneier on Security
Schneier on Security
Hacker News - Newest:
Hacker News - Newest: "LLM"
Microsoft Azure Blog
Microsoft Azure Blog
F
Fortinet All Blogs
IT之家
IT之家
The Last Watchdog
The Last Watchdog
腾讯CDC
Microsoft Security Blog
Microsoft Security Blog
Project Zero
Project Zero
B
Blog
Recorded Future
Recorded Future
博客园_首页
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
S
SegmentFault 最新的问题
Security Archives - TechRepublic
Security Archives - TechRepublic
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
H
Hacker News: Front Page
T
Threatpost
H
Heimdal Security Blog
Cloudbric
Cloudbric
Google Online Security Blog
Google Online Security Blog
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
V
V2EX
云风的 BLOG
云风的 BLOG
V
Visual Studio Blog

蛮荆

如何获取更多的免费服务器 Kubernetes 调度器队列 - 设计与实现 Kubernetes 调度器 - 核心流程 Kubernetes Networking Model & CNI Kubernetes 控制器管理总结 Kubernetes CronJob 设计与实现 Kubernetes Job 设计与实现 Kubernetes HPA 设计与实现 Kubernetes Deployment 滚动更新实现原理 Kubernetes GC 设计与实现 Kubernetes Pod 驱逐 - 设计与实现 Kubernetes Daemonset 设计与实现 Kubernetes ReplicaSet 设计与实现 Kubernetes EndPoint 设计与实现 Kubernetes Informer 设计与实现 降本增效之应用优化 (三) 日志存储与检索 Kubernetes Pod 设计与实现 - 创建流程 Kubernetes 探针设计与实现 Unix 编程艺术名句摘录 Kubernetes - CRI 概述 Golang 编译速度为什么这么快? Kubernetes Pod 设计与实现 - Pause 容器 Kubernetes - kube-proxy 代理模式工程优化 Kubernetes 应用最佳实践 - 优雅关闭长连接 Kubernetes Service 类型和会话亲和性 Kubernetes 为什么需要 Ingress Kubernetes 架构 - 控制平面和数据平面 降本增效之应用优化 (二) 大报表 Go 语言如何获取 CPU 利用率 降本增效之应用优化 (一) Redis 业务规则引擎演变过程简述 微服务中的熔断算法 漏桶算法和令牌桶算法 jsonparser 为什么比标准库的 encoding/json 快 10 倍 ? zap 高性能设计与实现 HTTP Router 算法演进 fastcache 高性能设计与实现 Web 常见的三个安全问题 ants Code Reading Go 线程安全 map 方案选型 布隆过滤器 死锁、活锁、饥饿、自旋锁 sync.Pool Code Reading Go 内存管理概述 Go netpoll Code Reading goroutine 泄漏与检测 time/Timer Code Reading GMP Scheduler Code Reading Go channel 的 15 条规则和底层实现 为什么 Linux “一切皆文件” context.Context Code Reading runtime/HACKING.md Goland 最佳实践 互联网开发与金庸武学 为什么 Redis 6.0 引入多线程模型? Kubernetes 应用最佳实践 - 金丝雀发布 容器中如何正确配置 GOMAXPROCS ? singleflight Code Reading sync.Map Code Reading sync.Cond Code Reading sync.WaitGroup Code Reading sync.RWMutex Code Reading sync.Mutex Code Reading sync.Once Code Reading Go 无锁编程 sync/atomic Code Reading goroutine 交替打印奇偶数 GODEBUG Go 并发模式 Go 汇编 UUID 通用技术选型 Kubernetes 应用最佳实践 - 水平自动伸缩 Go 高性能 Tips fasthttp 为什么比标准库 net/http 快 10 倍 ? 技术文章配图指南 ChatGPT 初体验 Docker 网络原理概览 iptables 的五表五链 Kubernetes 应用最佳实践 - 亲和性和污点容忍度 Go 的反射与三大定律 Docker 官方提供的最佳实践 Go 语言内置的设计模式 HTTP1 到 HTTP3 的工程优化 Kubernetes 应用最佳实践 - Sidecar 模式 Kubernetes 应用最佳实践 - init 容器和钩子函数 为什么 recover 必须在 defer 中调用? 为什么 defer 的执行顺序和注册顺序不同? Go map 设计与实现 Go 语言中的零拷贝 Go Delve 云原生和边缘计算简介 Kubernetes Pod 服务质量等级 Kubernetes 应用最佳实践 - 探针 Kubernetes 应用最佳实践 - 资源请求和限制 CDN 原理 Kubernetes 应用最佳实践 - 开篇 缓存策略和模式 Go 内存模型 Kubernetes 核心概念 软件版本语义化
Go 切片扩容底层实现
2023-03-10 · via 蛮荆

2023-03-10 Golang Go 源码分析 读代码

概述

切片 在使用过程中,值得注意的地方就是扩容导致的性能问题,实际开发中,我们一般会通过 容量预分配 来规避这个问题。

本文主要研究下 切片扩容 的内部实现。

内部实现

接下来,我们来探究一下 切片 的内部实现,文件路径为 $GOROOT/src/runtime/slice.go,笔者的 Go 版本为 go1.19 linux/amd64

切片 的运行时数据结构。

type SliceHeader struct {
	Data uintptr    // 引用数组的指针 (指向一片连续的内存)
	Len  int        // 切片的长度
	Cap  int        // 切片的容量
}

makeslice

切片 结构的运行时创建函数,编译器会将 切片的初始化操作 (不管是调用 make 函数还是字面量的方式) 转换为 makeslice 调用。

func makeslice(et *_type, len, cap int) unsafe.Pointer {
	mem, overflow := math.MulUintptr(et.size, uintptr(cap)) // 内存空间 = 元素大小 * 容量
	
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		// 注意: 当调用 make([]T, bignumber) 是,产生 'len out of range', 而非 'cap out of range'
		// 'cap out of range' 当然也是正确的,但是 cap 没有 len 提示更清晰
		// See golang.org/issue/4085.
		
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

	return mallocgc(mem, et, true)  // 执行具体的内存分配
}

// 返回 a * b 的结果以及结果是否溢出
// 编译器会根据不同的目标平台计算对应的值
func MulUintptr(a, b uintptr) (uintptr, bool) {
	if a|b < 1<<(4*goarch.PtrSize) || a == 0 {
		return a * b, false
	}
	overflow := b > MaxUintptr/a
	return a * b, overflow
}

growslice

growslice 函数主要用来处理调用 append 函数时引发的切片扩容。

// 它接收元素类型、旧的切片和新的【所需最小容量】,然后返回一个至少拥有【所需最小容量】的新切片,并将旧切片的数据复制到新切片中
// 新切片的 length 会被设置为旧切片的 length,而不是新请求的 capacity
// 这是为了方便编码,旧切片的长度可以立即用于:计算在追加过程中写入新值的索引位置
func growslice(et *_type, old slice, cap int) slice {
	...

	if cap < old.cap {  // 不能缩容
		panic(errorString("growslice: cap out of range"))
	}

	if et.size == 0 {
		// append 不应该创建一个带有 nil 指针但是 len 长度非零的切片
		// 假设 append 不需要保存 old.array 
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}

	newcap := old.cap 
	doublecap := newcap + newcap
	if cap > doublecap {
		// 如果期望容量大于当前容量 2 倍,使用期望容量
		newcap = cap
	} else {
		const threshold = 256
		if old.cap < threshold {
			// 如果当前容量小于 256,容量翻倍
			newcap = doublecap
		} else {
			// 如果当前容量大于等于 256: 
			// 检查 0 < newcap 以检测溢出并防止无限循环
			for 0 < newcap && newcap < cap {
				// 平滑过度: 从 [小切片的容量翻倍扩容] 到 [大切片的 1.25 倍扩容] 
				// 也就是说,刚开始时 (容量小) 直接翻倍,慢慢地到后面 (容量越来越大), 最终扩容的倍数因子是 1.25
				// 这个公式给出了两者之间的平滑过渡, 一直扩容到满足条件为止
				newcap += (newcap + 3*threshold) / 4
			}
			// 当新的容量计算溢出时,将新容量设置为期望容量
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

	// 上述代码片段仅会确定切片的大致容量,除此之外,还需要根据切片中的元素大小进行内存对齐
	// 当切片元素所占字节大小为 1, 2, 8 的倍数时,运行时使用如下代码内存对齐
	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	
	// 专门用于 et.size 公共值
	//  对于 1,不需要任何调整
	//  对于 goarch.PtrSize (64 位是 8, 其他的以此类推), 编译器会将乘法/除法优化为一个常数的位移
	//  对于 2 的幂,使用可变位移
	switch {
	case et.size == 1:
        ...
		
		newcap = int(capmem)
	case et.size == goarch.PtrSize:
		...
		
		newcap = int(capmem / goarch.PtrSize)
	case isPowerOfTwo(et.size):
		...
		
		newcap = int(capmem >> shift)
	default:
		...
		
		newcap = int(capmem / et.size)
	}

	// 除了 capmem > maxAlloc 之外,还需要检查溢出,溢出用于触发 32 位体系结构上的段错误
	// 示例程序如下
	//
	// type T [1<<27 + 1]int64
	//
	// var d T
	// var s []T
	//
	// func main() {
	//   s = append(s, d, d, d, d)
	//   print(len(s), "\n")
	// }
	
	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

	var p unsafe.Pointer
	if et.ptrdata == 0 {
		p = mallocgc(capmem, nil, false)
		// 调用 growslice 的 append() 将会覆盖 old.len 到 cap 之间的数据 (cap 将是新的长度) 
		// 仅仅清除不会被覆盖的部分
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		// 注意: 不能使用 rawmem (可以避免内存转换为零值),因为这样 GC 可以扫描未初始化的内存
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			// 只隐藏旧数组中的指针,因为知道目标切片 p 只包含 nil 指针 (因为它已经在分配期间被清除)
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
		}
	}
	memmove(p, old.array, lenmem)

	return slice{p, old.len, newcap}
}

slicecopy

slicecopy 函数用于将无指针元素的切片或字符串复制到切片中。

func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
	if fromLen == 0 || toLen == 0 { // 源切片或者目标切片有一个长度为 0, 直接返回
		return 0
	}

	n := fromLen    // n 等于较短的切片长度
	if toLen < n {
		n = toLen
	}

	if width == 0 { // 无需拷贝
		return n
	}

	size := uintptr(n) * width
	
	...

	if size == 1 {
		// 如果只有 1 个元素,直接转换对应指针
		*(*byte)(toPtr) = *(*byte)(fromPtr)
	} else {
		memmove(toPtr, fromPtr, size)
	}
	return n
}

小结

切片 使用 append 函数进行追加操作时,可能会引发扩容操作,对于潜在的引发多次扩容场景,初始化切片时一定要使用 预分配 机制。

切片的扩容计算方式如下

  • 如果期望容量大于当前容量 2 倍,使用期望容量
  • 否则
    • 如果当前容量小于 256,容量翻倍
    • 如果当前容量大于等于 256, 平滑扩容过渡,最终扩容的倍数因子是 1.25

扩展阅读