定长数组怎么当队列用

定长数组怎么当队列用
隔壁老康难度 ★★☆☆☆ · 前置:队列为什么会把内存吃光 | 一句话结论:一块固定的地加两个下标,把队列这件事压成一个取模;掩码换掉取模能省三成五,可无锁版本卡住人的地方在下标之外。
去年十二月,我在本机挂了一个采集脚本过夜,想弄明白它为什么越跑越占内存。写法顺手得很:一个切片,一行 append 往里塞,超过两百条就把开头切掉一格。第二天早上翻曲线,是一条一直往右上走的斜线,从几十 KB 爬到十几兆,中间没有一次回落,也没有一次抖动。我盯着它看了十分钟,因为按我写的逻辑,这个缓冲区里永远最多只有两百条。
我以为切片会自己缩。
不会。logs = logs[1:] 只是把切片头里那个地址往后挪了八字节,底下那块数组一格都没少;紧接着的 append 又要在尾巴上加东西,可起点右边剩的地被一截一截吃掉,见底就得重新要一块,把活着的那两百行整块搬过去。搬一次不贵,贵的是它跟推入次数成正比:两百万条日志就是两百万次容量判断,每隔几百次就有一次搬家,搬完扔下的旧地还得等 GC 才还。扩容的路子不难推:容量不够就按倍数翻,第 k 次搬家要一块比前一次大一半到两倍的地,把活着的元素逐个拷过去,旧的那块交给 GC。拷的总量加起来是线性的,看着划算;不划算的是那串旧数组的寿命,它们每一块都要等下一次 GC 才真的还回去,而夜里只有一个线程在干活,GC 的间隔被拉得很长,几十块旧数组就那么同时挂在堆上。
涨的不是那两百行,是它每次搬家扔下的地。
我一直用切片干这种留住最近 N 条的活,因为写起来最短,三条语句里没有一处需要想。直到把推入次数和分配次数并排打出来,我才承认最短的那几行里藏着一条增长曲线,而那条曲线我以前以为只会出现在别人写的程序里。
一块地,两个下标,走到头就回零
环形的做法是把这块地一次性要够,然后一辈子不再要。数组开出来就是 n 个槽,之后推多少条都在 n 个槽里轮着用。head 指着最老的那条,也就是下一个要出去的;tail 指着下一个能写的位置。推一条写进 tail,tail 往前走一格;出一条读 head,head 往前走一格。往前走这件事落在两个下标上是同一个式子,(i + 1) % n,写起来像一条数学,跑起来是一条除法。这两个下标加起来只占两个机器字,比任何链式结构都省,而且它们挨在一起,多半落在同一行缓存里。环开多大都不影响推一条要动几个字:动的永远只有那两个下标和 tail 指着的那一格。
走到 n 就回零,像秒针过 59。
内存里并没有一个环。数组还是那条直的,第 0 格在最低地址,第 n-1 格在最高地址,走到头之后下一个是 0,中间的地址并不连续,可下标回到了连续。环是下标的行为,不是内存的形状。这一点想通之后,剩下的都只是算术:推一次改两个数,出一次改两个数,没有一处需要问分配器,也没有一处需要等 GC 收尾。环是假的,省下来的地是真的。
1 | type ring struct { |
这段里 n 是当前条数,不是下标,有了它满和空就不用靠下标猜。满了之后这一推覆盖的是 head 那一格,也就是最老的一条,然后 head 自己往前走一格:这是覆盖,不是拒绝,调用方拿不到任何提示。我那个采集脚本要的正是覆盖,最新的一百行永远比前一秒看到的那条值钱,而最老的那条早就落在磁盘上了。
覆盖是这里唯一的语义。
满和空:三种分辨法,三种账
环形缓冲里唯一需要想清楚的地方,是 head 和 tail 靠在一起的时候到底算空还是算满。两个下标相等,两种状态长得一模一样,光看它们分不出来,而代码从上线的第一分钟起就得决定这一次是读还是写。第一种是留一格空着,规定环里最多只放 n-1 条,那么 tail 追上 head 的前一格就是满:(tail+1)%n == head 算满,head == tail 算空。代价是那一格永远用不上,你申请 1024 只得到 1023。这一格空着不只是少一格内存,它还把可用容量从 2 的幂挪成了 2 的幂减一,而掩码那条式子只认 2 的幂,两边差一,写的时候脑子里得随时记着哪个 n 是格数、哪个 n 是条数。我在这套记号上绕进去过,改完代码盯着 n 和 n-1 看了好一会儿才理清。
第二种是加一个计数。head、tail 之外再放一个 n,推加一,出减一,n == 0 是空,n == cap 是满,没有歧义,一格不浪费。
前两种省一次减法,后一种多一个字段、少一次减法。
第三种是两个计数器只增不减:head 和 tail 都换成 uint64,每次推加一,永远不回绕,取下标的时候才掩一下。空还是 head == tail,满变成 tail - head == cap,判断只用一条减法。好处在于每个计数器只有一边在写,生产者只动 tail,消费者只动 head,两个线程碰不到同一个字。
1 | type counterRing struct { |
三版我都写过。第一种最容易在边界上错,容量很小的时候尤其明显;第二种最好懂,我给自己写东西还是用它;第三种只在要跨线程的时候才显出好处,单线程里它多干的那点活换不来任何东西。
第三个只在跨线程时值钱。
九点五纳秒和六点一纳秒
三个实现放进同一个基准:容量都开 1024,循环里推一条、马上出一条,各跑三次,元素是那个 64 字节的 item。
| 实现 | 三次 ns/op | B/op | allocs/op |
|---|---|---|---|
sliceQueue |
169.2 / 156.4 / 101.6 | 334~383 | 0 |
ringQueue |
9.521 / 8.350 / 9.717 | 0 | 0 |
maskQueue |
6.172 / 5.404 / 6.060 | 0 | 0 |
最慢那行和最快那行差了十六到二十五倍,中间两行贴着走,差三点几纳秒,也就是三成五。先说九点五到六点一,两者只差一行:取模换成掩码。(tail+1) % len(buf) 里那个除数是变量,编译器不知道它是多少,只能老实发一条除法,而除法是这几条整数运算里最慢的。
恒定不等于快。可要说环形每一下都比切片快,那是假话。换一个基准,窗口只有一百来条、数组一直热在缓存里,切片版每下 5.4 到 17.2 纳秒,环形版 11.1 到 12.5 纳秒,反过来是它慢:环形一次要算两回下标,切片出队只要把切片头挪一下。它换来的东西不在秒表上,在跑了六个小时之后的那张内存图上。
二的幂是从那条除法换来的
掩码能替掉取模,靠的是二进制的性质:n 是 2 的 k 次方的时候,n-1 的低 k 位全是 1,x & (n-1) 取出来的正好是 x 除 n 的余数。n 不是 2 的幂,这条等式就不成立,而且不成立得很安静,不报错,下标看着也不越界,只在某些位置上读到一格莫名其妙的数据。
这个错法最难查。
容量就因此被绑在 2 的幂上。你想要一千格,只能开 1024,多出来的 24 格空着;真开 1000 再把掩码写成 n-1,从第一圈起就是错的。所以构造函数里得把这件事写明白,要么向上取整到 2 的幂,要么干脆只收 2 的幂,别让调用方传个 3000 进来还以为自己拿到了 3000 格。
一条 and 指令,换一条约束。一次省三点几纳秒,一秒钟一百万次才省三毫秒;这条路径一秒只走几十次的话,这点差别还不如你多打一行日志。
零点五七兆和七十五点一兆
内存这件事量起来比时间干脆。同样推一百万条,元素还是 64 字节的 item:切片队列积压到一百万条,GC 之后堆上 75.1 MB;环形队列容量定一万,推同样的一百万条,满了就覆盖最老的,GC 之后堆上 0.57 MB,里面躺着最新的那一万条。
一百三十一倍。
这个倍数没什么玄机,它差不多就是一百万和一万的比,零头是切片自己空着的那些容量。切片版把所有没人再看的旧数据留着,环形版存的永远只有窗口里那一万条;一万格乘 64 字节是六百多 KB,实测 0.57 MB,同一个量级。
数字比秒表难糊弄。
更难受的是,切片那版的堆在出队之后也不降。出队只是把 head 往前挪,那块数组还是原来那块,栈上有切片头指着它,GC 就知道它还有人要,于是不动它。你把前五十万条从逻辑上丢掉了,从内存上一条都没丢。这一条我第一次还量错过,忘了先跑一次 GC。
三十一次,和十九万九千九百零七次
三种写法,三个差得很远的数。切片队列推二十万条、中间不出队,底层数组换了 31 次容量,最终 cap=219136,这是最规矩的那种增长,翻着倍往上走,三十一次里大半挤在前面。换成边推边出、窗口一百条,同样推二十万条,指针换了 199,907 次,几乎每推一条就换一次。
这个数看着像每一条都重新分配了内存,其实不是:a = a[1:] 让切片头里那个地址每轮往后挪八字节,指针就换了一次,真正向分配器要新内存的次数比它少得多。跑完那一圈,len 是 100,cap 是 116,后面压着一截再也用不上的地。
环形那版做同一件事,容量从第一行起就是 1024,推完二十万条还是 1024,里面躺着 100 条,那块数组从 make 出来到程序结束没有挪过位置。分配次数在另一个测试里数得更直接:切片版滑动窗口推一百万条,分配 8080 次,总量 13.79 MB,跑完 len=100、cap=164;环形版同一件事,1 次,0.00 MB。
窗口放到一千、推四百万次,切片版 7481 次、87.46 MB,环形版 0 次、0 MB。
一个在长,一个没长。
下标好办,内存序不好办
前面所有的数字都是单线程跑出来的。
单生产者、单消费者听起来最省事。两个线程各干各的,这边只管 tail,那边只管 head,一个环里两个下标,一个只有这边写,一个只有那边写,好像连原子操作都不必用。
麻烦不在下标上。生产者要做两件事:把元素写进 tail 指着的那一格,然后把 tail 往前推。这两件事在源码里是上下两行,在机器上不一定按这个顺序发生。编译器有重排的自由,CPU 也有,写元素的几条指令还没落地,写 tail 的那条可能已经发出去了。消费者看到 tail 变了,回头读这一格,读到的是一个还没写完的元素,一半新的,一半是上一圈留下的。这里说的重排不是我凭经验猜的,是语言和硬件都明文允许的东西;反过来,要挡住它也只有一条路,让发布这个动作带上语义,不能靠两行代码挨得近来保证。
消费者那边反过来一样:它读到 tail 落在前面,才有资格去读元素,要是读 tail 这一步被挪到了读元素后面,它读到的还是旧格子。所以元素写完才允许发布下标,下标读到了才允许读元素。这个先后不能靠我把两行写在一前一后来保证,得靠一次带发布语义的写和一次带获取语义的读;Go 里 sync/atomic 的 Store 和 Load 是顺序一致的,用它发下标,这两道先后由它兜住。至于它在 x86 和 ARM 上各生成什么指令,这里我不展开。
读到一半的元素长什么样,取决于它有多宽、是不是对齐:一个机器字能不能一次读完,换到别的宽度上就未必。我在这里不往下推这一层,只留一条能落地的话:元素越大,越别指望不打招呼地跨线程传。
这一段我没有量过,所以它一个数字都没有。
还有一件比下标更难的事:满的判断。生产者要知道还剩几格,就得去看消费者那边的计数器;消费者要知道有没有东西,就得看生产者这边。两边都在读对方写的字,这一步用各写各的绕不过去,所以多生产者就得让它们先原子地把位置抢下来,抢到了再写,写完再发布。真要写并发版本,我会先把 race detector 挂上跑一遍,再拿几百万次推读去压它。跑对和跑快是两件可以分开验的事,前一件错了是读到脏数据,后一件错了只是没赚到。
你要的是不是最近 N 条
第一,你要的是不是最近 N 条。环形天生会覆盖,覆盖就是把最老的丢掉。要是每一条都不能丢,它从第 N+1 条起就在替你丢数据,而且一声不响。
第二,生产会不会短时间跑在消费前面。
网络断了、下游卡了、磁盘写满了,这时候只有三条路:丢最老的、丢最新的、让生产方等着。环形是第一条,也是丢得最便宜的一条;第三条会把上游一起拖住,代价通常最大,而环形不用问下游任何事。
第三,这段代码热不热。
一次省三纳秒,得在每秒几百万次的路径上才看得见;一天跑十几次的东西,环形和切片谁也感觉不出来。反过来也有亏的时候,元素很大、容量开得很大、平时只用几条,环形一次性把那块地占住,九成是空的。
空着的地方也要占内存。
我那个采集脚本后来换成了固定 256 格的环。第二天早上内存曲线是平的,我把那两百行顺着 head 一圈一圈读出来,顺序正好从旧到新,中间没有一次分配。那块地从挂上去到关机,一个字节都没有挪过,而我要看的东西一样都没少。















