引擎为什么自己写队列：六十行queue.lua的性能账

Lua 的 table 是个好东西，好到很多人忘了它不擅长什么。直到有一天，同屏两千个技能特效的服帧率雪崩， profiling 一看，时间全烧在 table.remove(t, 1) 上——出一次队，整个数组搬家一次。996 引擎在 util/queue.lua 里自己写了个六十行的队列，今天从这六十行讲起，把"为什么不用现成的"讲透。

这个队列在引擎里的地位比它的人数气重得多：技能系统的 ID 池、动画加载队列 _animLoadQueue、各种待办缓存，全是它在撑。它是那种典型的"基础设施里的基础设施"——业务代码里看不到它的名字，但它下班了半个引擎跟着瘫痪。读这种代码的收益也最大：它没有一行多余的东西，每个字段、每次置 nil、每句注释都是踩过坑之后的沉淀，六十行能顶别人六百行的信息密度。

一、先看病历：table.remove 的隐形税

Lua 的官方文档写得明白：table.remove(t, 1) 是 O(n) 操作——删掉第一个元素，后面所有元素集体前移一位。队列是队列嘛，天真写法一秒出队两千次，就是两千次全员搬家。搬家本身不致命，致命的是搬家引发的连锁：数组内存重排、迭代器失效风险、GC 压力上涨。有个服做过对比测试：把 launch 缓存从 table.remove 改成双指针队列，同屏特效 800 个时帧时间从 11 毫秒降到 3 毫秒——三分之二的帧时间花在"搬家"上，代码一行业务逻辑都没变。

有人会抬杠：table.insert 和 table.remove(t) 不带位置参数时只动尾部，是 O(1)，用"尾进尾出"的栈式写法不就行了？对，但要的是队列——尾进头出。游戏里的排队场景几乎全是公平队列：技能发射请求按点击顺序播、加载任务按提交顺序处理，插队会产生可感知的时序 bug。所以头出是刚需，头出的 O(n) 就是刚需的代价，直到双指针出现才两清。选择数据结构前先把"进出方向"想清楚，这一步想明白，一半的容器选型就不用纠结了。

引擎的答案是一对指针：

function queue:push(d)
    self._data[self._border] = d      -- 新元素写在 border 位
    self._border = self._border + 1
end

function queue:pop()
    local ret = nil
    if self._index < self._border then
        ret = self._data[self._index]     -- 从 index 位取
        self._data[self._index] = nil     -- 取完置nil，防引用滞留
        self._index = self._index + 1     -- 只挪指针，不搬元素
    else
        self:reset()                      -- 空了：换新表
    end
    return ret
end

入队写 _border 位，出队取 _index 位，两个指针只会向前走，元素永远原地不动。push 和 pop 全是 O(1)，一次赋值一次加法，没有任何隐性成本。size() 就是两指针的差值，front() 取 _index 位、back() 取 _border - 1 位，全是指针算术。

_data[self._index] = nil 这一行也值得划线：取走元素后把槽位置空，是把引用交还给 GC 的礼貌动作。Lua 的表一旦塞过对象引用，槽位不复位就永远抓着对象不放——很多"内存缓慢上涨"的诡异案例，根子都是忘置 nil 的槽位。

置 nil 的收益可以量化给大家看。假设队列里存的是技能行为对象，每个连带引用的特效节点占 2KB 内存，一条队列每小时进出五千次、忘置 nil 的概率十分之一，一天下来就有上万条本该释放的引用悬在表里。GC 的标记阶段要把这些死引用挨个走一遍，回收器干的全是无用功，表现就是"游戏开久了全局卡顿越来越频繁"——不是泄漏，是慢性梗阻。置 nil 这半行代码，治的就是这个病。我们组内有一条机械性的评审规则：所有容器类的取用代码，取完必须置空，看到 local v = t[k] 后面没有 t[k] = nil 的，直接问一句"这个槽位的生命周期到哪结束"。

二、reset 的哲学：换表比扫地便宜

空队列再 pop 会触发 reset()：

function queue:reset()
    self._index = 0
    self._border = 0
    self._data = {}
end

function queue:clear()
    if self:empty() then
        for i = self._index, self._border do
            self._data[i] = nil       -- 已经空了还逐格清一遍（历史上留剩逻辑）
        end
    end
    self:reset()
end

reset 的手法值得品：指针归零加整表换新。旧表连同里面所有 nil 洞一起交给 GC，新表从下标 0 干净起步。为什么不逐格清理复用旧表？因为 Lua 的表底层是哈希加数组的混合结构，经历过大量增删的表内部布局碎片化，"复用旧表"省的那点分配开销，抵不过碎片化带来的查找退化。整表换新看似浪费，实则是 GC 时代最干净的清屏方式——反正旧表反正要回收，让它整体走，别一块一块抠。

这个"换新"的时机也有讲究：只在排空的瞬间换。排空意味着旧表上所有业务引用都已经出队完毕，此时换表零风险；有元素在队列里就换表，那些引用就全成了孤儿。时机选对，激进的手法就是安全的；时机不对，再保守的手法也出事。你以后做任何"重建容器"的优化（清空背包重建、重置技能树），都套这个判断：此刻容器里还有没有活着的引用？没有，大胆换；有，先通知完再换。

clear() 里那个 if self:empty() 的分支我每次读都乐：已经空了的队列，再逐格 nil 一遍属于脱裤子放屁，然后无条件 reset 又把表换了，前面那步清理纯属于无效功。这大概率是早期版本的残留逻辑。我把这段写出来不是教大家挑引擎毛病，是想说一件更重要的事：引擎代码也有历史包袱，读源码要有自己的判断，别把每一行都当圣旨供着——但改不改另说，改之前想清楚收益，六十行的小文件里这点冗余不值得动它，动了反而引入回归风险。"看出问题"和"值得修"是两码事，工程判断力的分水岭就在这。

flowchart TD
A[push v] --> B[_data[_border]=v]
B --> C[_border+1]
C --> D{业务方需要出队}
D --> E[_index < _border?]
E -->|是| F[取 _data[_index]]
F --> G[槽位置 nil 帮GC]
G --> H[_index+1]
H --> I{_index == _border? 空了}
I -->|下次pop| J[reset: 指针归零 + 换新表]
I -->|否| D
E -->|否| J

三、真实战场：技能 ID 池

这套队列在引擎里最经典的用武之地是 skillManager 的行为 ID 池：

-- skillManager.lua
self._behaviorIDPool = Queue.new()     -- 回收池：用队列管理可复用ID
self._behaviorIDCount = 0

-- 用完的行为ID进队列等复用
function skillManager:RecycleBehaviorID(behaviorID)
    self._behaviorIDPool:push(behaviorID)
end

技能特效的行为对象生命周期极短（一个飞行道具零点几秒），每次都要发 ID、用完回收。ID 从哪来？池里有回收的就 pop 一个复用，没有才从 _behaviorIDCount 自增发新号。这个模式和对象池（动画档案池、下载任务池）是同一思想的两个维度：对象池复用"东西"，ID 池复用"名字"。名字也要钱吗？要——behaviorID 作 key 挂在 _behaviors 表里，ID 无限自增会让表的哈希桶越来越散，回收复用让活跃 ID 集合始终紧凑。

分配端的逻辑对着 Tick 那段源码能拼出全貌：清理环节把失效行为的 ID 逐个 RecycleBehaviorID 塞回队列，LaunchSkill 需要新 ID 时先问队列。一进一出，ID 的活跃集合被压在"当前实际存在的特效数"以内——上限就是那个 SKILL_BEHAVIOR_LIMIT = 200。两百个 ID 常年循环使用，_behaviors 表的键空间永远紧凑，pairs 巡检的开销恒定。这套"发号—回收—复用"的循环和视野管理那篇的"同格发号"是亲兄弟，引擎里凡是"短命对象 + 频繁生死"的场景，最后都长成这个样子。

配合前面讲过的 _launchCache 出队循环（数字下标 for 而非 pairs），整套技能系统的每条高频路径都是数组级访问。200 个特效上限的硬顶压着，队列的进出频率可预期，这就是"敢用最简数据结构"的底气：数据结构的奢侈程度，永远由访问频率和规模上限说了算。

下面这个演示把两个指针摆上了台面：点 push 看 _border 右移、点 pop 看槽位变 nil 且 _index 追赶，勾上自动流水模拟 Tick 消费节奏，清空队列看"换新表"的 reset 时刻：

skill-queue-ring-1003c

四、坑与边界：队列不是筐

坑一：at() 越界静默返回 nil。 queue:at(index) 取相对位元素，越界不报错只给 nil。这既是 Lua 的天性也是陷阱：调用方拿 nil 当"不存在"处理没错，但当"默认值"用时就是 bug 温床。规范：at 的返回值必须显式判 nil，别喂给后续算术。

这里展开讲一个真实事故。某二开在技能排队逻辑里用 at(1) 取队头，队伍空时拿到 nil，后续代码 nil + 1 直接报错闪退。修的时候实习生加了句 or 0 兜底——错误被藏住了，但队列为空时本该"不处理"，现在变成"处理 0 号"，0 号恰好是某个特殊技能 ID，玩家全员会放出一个不存在于技能栏的技能。这个二次事故的教训比第一次贵十倍：nil 的正确处理是改变流程（跳过本轮），不是造一个默认值继续跑。判空后跳过，还是判空后给默认值，两种写法的差别是"防御"和"掩盖"的差别，评审时看到 or 0、or "" 这类兜底要多问一句：这个默认值走下去了，后面会发生什么？

坑二：只进不出是无界膨胀。 队列没有容量上限，push 多 pop 少就闷头长。资源下载器的队列有 DOWNLOAD_MAX 消费者兜底，动画的 _animLoadQueue 有加载完成回调消费，每个队列都必须回答"谁在消费、消费速度跟得上吗"。新加队列时把这个答案写进注释，答不出来的队列就是未来的内存事故。

坑三：遍历队列请用 at。 有人图省事直接 pairs(queue._data) 遍历，把 nil 洞和已出队的历史残留全扫了一遍，还依赖了下标连续性这种内部实现。队列暴露的公共接口就是为封装服务的，size 加 at 的循环才是正路。封装不是学术洁癖，是给未来换实现留后路——哪天把 _data 换成环形数组，走公共接口的调用方一行不用改。

再补一个队列周边的实用技巧：front 和 back 的搭配使用。front 看队头不弹出，用来"偷看"下一个要处理的任务决定要不要继续处理；back 看队尾，用来去重——入队前先看队尾，和刚入队的是同一个任务就跳过，鼠标事件连发时的去重就是这么做的。一对"只看不拿"的接口让队列从纯 FIFO 变成了可以窥探的数据流，很多时序问题在入队前就掐死了，比出队后再判空干净得多。API 设计时多给一个只读视图，调用方能少写一半的防御代码，这个经验通用于所有容器类设计。

五、常见疑问

问：为什么用两个数字指针不用 head/tail 链表？
Lua 里链表靠表模拟，每个节点一个表，增删是 O(1) 但内存和 GC 开销比连续结构大得多。双指针数组队列在小规模高频场景全面胜出——引擎的选择永远是"数据规模说话"，几十个元素的队列上链表属于杀鸡用牛刀。

问：队列会不会一直向后走导致下标爆炸？
不会，reset 在每次排空时换新表，下标永远从 0 起步。真正的风险是"长期只剩一两个元素来回进出"——index 和 border 缓慢增长，要很多天才会到不可接受的程度，而 reset 机制在排空时就归位了。这是设计里藏着的自愈能力。

问：我自己的项目该不该抄这个队列？
先量场景：每秒出队超过百次、且用 table.remove(1)，抄，立竿见影；一天出队几十次的，table.remove 完全够用，引入自定义结构徒增理解成本。优化要对着 profiling 做，别对着文章做——包括这篇。

问：size 会因为 nil 洞算错吗？
不会。size 是 _border - _index 的纯指针算术，跟表里存了什么无关。这正是指针化管理的优势：长度信息不依赖内容巡检，O(1) 且永远正确。对比用 #t 取长度的写法，带 nil 洞的表 # 返回值是未定义行为，同一个表可能返回不同答案——引擎自己维护计数、不信 # 的做法，在掉落物那篇也出现过，这是老引擎的一条铁律。

👉 完整课程入口：996 全套课程体系（千余节课录） ｜ 想跟浮生梦老师系统学的，看 LUA 高并发商业架构路径。