详解Golang如何实现一个环形缓冲器
来源:脚本之家
时间:2023-01-01 14:13:57 242浏览 收藏
对于一个Golang开发者来说,牢固扎实的基础是十分重要的,golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《详解Golang如何实现一个环形缓冲器》,主要介绍了环形、缓冲器,希望对大家的知识积累有所帮助,快点收藏起来吧,否则需要时就找不到了!
背景
环形缓冲器(ringr buffer)是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构,适合缓存数据流。
在使用上,它就是一个固定长度的FIFO队列:
在逻辑上,我们可以把它当成是一个环,上面有两个指针代表当前写索引和读索引:
在实现上,我们一般是使用一个数组去实现这个环,当索引到达数组尾部的时候,则重新设置为头部:
kfifo实现
kfifo是Linux内核的队列实现,它具有以下特性:
- 固定长度:长度是固定的,而且是向上取最小的2的平方,主要是为了实现快速取余。
- 无锁:在单生产者和单消费者的情况下,是不需要加锁的。主要是因为索引in和out是不回退的,一直往前。
- 快速取余:我们都直到到达队列末尾的时候,索引需要回退到开头。最简单的实现方式就是对索引取余,比如索引in现在是8,队列长度是8,
in%len(q)
即可回退到开头,但是取余操作%
还是比较耗时的,因此kfifo使用in&mask
实现快速取余,其中mask=len(q)-1
。
无锁
上面我们说到,这个无锁是有条件的,也就是必须在单生产者单消费者情况下。这种情况下,同一时刻最多只可能会有一个写操作和一个读操作。但是在某一个读操作(或写操作)的期间,可能会有多个写操作(或读操作)发生。
因为索引in和out是不回退的,因此in一直会在out前面(或者重合)。而且in只被写操作修改,out只被读操作修改,因此不会冲突。
这里可能有人会担心索引溢出的问题,比如in到达math.MaxUint64,再+1则回到0。但是其实并不影响in和out之间的距离:
package main import ( "fmt" "math" ) func main() { var in uint = math.MaxUint64 var out uint = math.MaxUint64 - 1 fmt.Println(in - out) // 1 in++ fmt.Println(in - out) // 2 out++ fmt.Println(in - out) // 1 }
当然如果连续两次溢出,就会出现问题。但是由于数组长度是int类型,因此也没办法超过math.MaxUint64
,也就是in和out之间的距离最多也就是2^62
,因为math.MaxInt64
是2^63-1
,没办法向上取2的平方了。因此也不会出现溢出两倍math.MaxUint64
的情况,早在溢出之前就队列满了。
快速取余
前面提到取余是通过in&mask
实现的,这有一个前提条件,也就是长度必须是2的次方,因此在创建数组的时候,长度会向上取最小的2的平方。例如一个长度为8
的kfifo,在二进制表示下:
len = 0000 1000 // 十进制8,队列长度 mask = 0000 0111 // 十进制7,掩码 in = 0000 0000 // 十进制0,写索引 in & mask => 0000 0000 // 十进制0,使用 & mask in % len => 0000 0000 // 十进制0,使用 % len in = 0000 0001 // 十进制1,写索引 in & mask => 0000 0001 // 十进制1,使用 & mask in % len => 0000 0001 // 十进制1,使用 % len in = 0000 0001 // 十进制1,写索引 in & mask => 0000 0001 // 十进制1,使用 & mask in % len => 0000 0001 // 十进制1,使用 % len in = 0000 1000 // 十进制8,写索引 in & mask => 0000 0000 // 十进制0,使用 & mask in % len => 0000 0000 // 十进制0,使用 % len in = 0001 0001 // 十进制17,写索引 in & mask => 0000 0001 // 十进制1,使用 & mask in % len => 0000 0001 // 十进制1,使用 % len
可以看到,使用& mask
的效果是和% len
一样的。
然后我们做一个简单的性能测试:
package main import "testing" var ( Len = 8 Mask = Len - 1 In = 8 - 5 ) // % len func BenchmarkModLen(b *testing.B) { for i := 0; i测试结果:
BenchmarkModLen-8 1000000000 0.3434 ns/op
BenchmarkAndMask-8 1000000000 0.2520 ns/op可以看到
& mask
性能确实比% len
好很多,这也就是为什么要用& Mask
来实现取余的原因了。数据结构
数据结构和上面介绍的一样,in、out标识当前读写的位置;mask是size-1,用于取索引,比
%size
更加高效;type Ring[T any] struct { in uint64 // 写索引 out uint64 // 读索引 mask uint64 // 掩码,用于取索引,代替%size size uint64 // 长度 data []T // 数据 }Push()
Push()操作很简单,首先
r.in & r.mask
得到写索引,让写索引前进一格,然后存入数据。// 插入元素到队尾 func (r *Ring[T]) Push(e T) { if r.Full() { panic("ring full") } in := r.in & r.mask r.in++ r.data[in] = e }Pop()
Pop()操作同理,根据
r.out & r.mask
得到读索引,让读索引前进一格,然后读取数据。// 弹出队头元素 func (r *Ring[T]) Pop() T { if r.Empty() { panic("ring emtpy") } out := r.out & r.mask r.out++ return r.data[out] }性能测试
Round实现是使用
& mask
,同时长度会向上取2的平方;Fix实现是使用% size
保持参数的长度。测试代码是不断的Push()然后Pop():
func BenchmarkRoundPushPop(b *testing.B) { for i := 0; i测试结果:
& mask
的性能明显好于% size
。BenchmarkRoundPushPop-8 2544 405621 ns/op // & mask
BenchmarkFixPushPop-8 678 1740489 ns/op // % size无界环形缓冲器
我们可以在写数据的时候判断是否空间已满,如果已满我们可以进行动态扩容,从而实现一个无界环形缓冲器。
Push()
在Push()时检查到空间满时,调用grow()扩展空间即可:
// 插入元素到队尾 func (r *Ring[T]) Push(e T) { if r.Full() { // 扩展空间 r.Grow(r.Cap() + 1) } in := r.in % r.size r.in++ r.data[in] = e }grow()
扩容一般是扩展为当前容量的两倍,然后把原来数据copy()到新的数组,更新字段即可:
// 扩容 func (r *Ring[T]) Grow(minSize uint64) { size := mmath.Max(r.size*2, minSize) if size > MaxSize { panic("size is too large") } if size线程安全性
由于可能会动态扩容,需要修改out、in指针,因此需要加锁保证安全。
代码地址
https://github.com/jiaxwu/gommon/tree/main/container/ringbuffer
今天带大家了解了环形、缓冲器的相关知识,希望对你有所帮助;关于Golang的技术知识我们会一点点深入介绍,欢迎大家关注golang学习网公众号,一起学习编程~
-
505 收藏
-
502 收藏
-
501 收藏
-
501 收藏
-
501 收藏
-
365 收藏
-
369 收藏
-
194 收藏
-
213 收藏
-
382 收藏
-
163 收藏
-
370 收藏
-
201 收藏
-
102 收藏
-
467 收藏
-
469 收藏
-
148 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 508次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习
-
- 沉默的老鼠
- 这篇技术文章出现的刚刚好,楼主加油!
- 2023-01-10 16:01:18
-
- 正直的彩虹
- 很棒,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,帮助很大,总算是懂了,感谢老哥分享技术贴!
- 2023-01-10 02:44:38
-
- 激动的黑夜
- 这篇技术文章出现的刚刚好,好细啊,赞 👍👍,已加入收藏夹了,关注大佬了!希望大佬能多写Golang相关的文章。
- 2023-01-07 03:52:03
-
- 沉静的野狼
- 太细致了,mark,感谢作者大大的这篇技术文章,我会继续支持!
- 2023-01-05 15:21:45
-
- 机灵的小土豆
- 这篇技术贴真及时,太详细了,受益颇多,mark,关注作者了!希望作者能多写Golang相关的文章。
- 2023-01-05 06:41:26
-
- 壮观的面包
- 这篇技术文章太及时了,太细致了,很好,码住,关注老哥了!希望老哥能多写Golang相关的文章。
- 2023-01-04 12:06:54
-
- 寂寞的外套
- 太全面了,码起来,感谢作者的这篇文章,我会继续支持!
- 2023-01-03 20:11:25
-
- 忧虑的大象
- 很棒,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,看完之后很有帮助,总算是懂了,感谢大佬分享技术文章!
- 2023-01-01 22:49:13