如何高效维护10万至100万量级游戏对象的脏对象/脏索引列表

最优方案：BitArray + 脏索引列表组合实现 #

这是目前游戏开发领域处理脏标记最常用的高性能方案，完美解决重复校验和遍历开销的矛盾：

• 核心实现逻辑
  1. 初始化两个容器：和对象总数量长度一致的BitArray IsDirty（每个位对应一个对象的脏状态，默认值为false代表干净），以及一个List<int> DirtyIndexes用来存储脏索引
  2. 标记对象为脏时，先检查IsDirty[index]的值：如果为false，就将其设为true，同时把index添加到DirtyIndexes中；如果已经为true，直接跳过即可
  3. 每帧处理完所有脏对象后，遍历DirtyIndexes把对应位置的IsDirty[index]重置为false，再清空DirtyIndexes进入下一帧的逻辑
• 性能收益
  • 重复校验开销接近零：BitArray的位访问是CPU原生支持的操作，比HashSet的哈希计算、哈希冲突校验的速度快至少一个数量级，完全可以支撑单帧十万次级别的标记请求
  • 后续遍历无额外开销：DirtyIndexes里存储的都是无重复的脏索引，处理时直接遍历即可，不需要加任何过滤逻辑
  • 重置成本极低：不需要遍历全量的BitArray，仅需要遍历当前帧的脏索引列表做状态重置，脏索引越少重置速度越快

极端场景备选方案 #

如果你的业务场景中单帧脏索引占总对象的比例超过30%，可以直接改用状态数组遍历方案：

• 用长度和对象总数一致的byte[] IsDirty存储状态（byte比int内存占用更小，CPU缓存命中率更高），标记脏的时候直接把对应位置设为1，不需要判断重复
• 处理的时候直接全量遍历对象数组，仅处理状态为1的对象即可，全量遍历10万级别的数组在现代CPU上的开销不到0.1ms，比高频添加脏索引的开销更低

内容的提问来源于stack exchange，提问作者TCZ8