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

推荐订阅源

The Last Watchdog
The Last Watchdog
K
Kaspersky official blog
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
Spread Privacy
Spread Privacy
T
Threatpost
cs.CV updates on arXiv.org
cs.CV updates on arXiv.org
cs.CL updates on arXiv.org
cs.CL updates on arXiv.org
MongoDB | Blog
MongoDB | Blog
V
Vulnerabilities – Threatpost
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
Help Net Security
Help Net Security
Microsoft Azure Blog
Microsoft Azure Blog
GbyAI
GbyAI
小众软件
小众软件
Cloudbric
Cloudbric
The Hacker News
The Hacker News
阮一峰的网络日志
阮一峰的网络日志
Vercel News
Vercel News
人人都是产品经理
人人都是产品经理
Forbes - Security
Forbes - Security
Martin Fowler
Martin Fowler
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
AWS News Blog
AWS News Blog
Stack Overflow Blog
Stack Overflow Blog
N
News | PayPal Newsroom
P
Privacy & Cybersecurity Law Blog
TaoSecurity Blog
TaoSecurity Blog
H
Hackread – Cybersecurity News, Data Breaches, AI and More
博客园_首页
A
Arctic Wolf
www.infosecurity-magazine.com
www.infosecurity-magazine.com
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
Scott Helme
Scott Helme
T
Tor Project blog
S
Secure Thoughts
Know Your Adversary
Know Your Adversary
P
Proofpoint News Feed
M
MIT News - Artificial intelligence
博客园 - 司徒正美
T
Threat Research - Cisco Blogs
C
Cyber Attacks, Cyber Crime and Cyber Security
Schneier on Security
Schneier on Security
B
Blog RSS Feed
AI
AI
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
Attack and Defense Labs
Attack and Defense Labs
Webroot Blog
Webroot Blog
Google DeepMind News
Google DeepMind News
Project Zero
Project Zero
Hacker News: Ask HN
Hacker News: Ask HN

蛮荆

如何获取更多的免费服务器 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

扩展阅读