带猜测的二分查找算法
我想用 C 实现一个内存紧凑的 ECS 框架，希望数据结构足够的简单，且能管理海量的对象。所以我让每个 component 就是一个不包含任何引用的 struct ，并带有一个 32bit 的 id 。并把这样的一个数据结构放在一块连续内存中。
这个 id 没有对外暴露的 API （不是 entity id ），可以在运行过程中调整。如果两个不同类型的 component 有相同的 id ，即认为它们同属一个 entity 。id 的作用是管理 component 的生命期，以及在遍历 component 时，可以找到同个 entity 上其它的组件。
对于我的应用场合来说，最多的操作是遍历单类 component 的集合。这种操作在这个数据结构下特别简单，就是 for 循环遍历一个简单的数组。但有些系统会需要在处理一个 component 时，找到它归属的 entity 上的兄弟组件。由于我不想用额外的内存建立这些 component 间的联系，所以这个开销就会特别大。如果不做任何优化，查找是 O(n) 的，n 为组件的数量。这显然不能接受。
第一步优化，我让组件在组件集数组中保持有序，按 id 排序。id 本身在分配的时候是单调递增的，所以只要 32bit id 不回绕就能一直保持有序。一旦回绕，我们重排一下即可。对于有序的数组，用二分查找可以减少到 O(log N) 的时间复杂度。
如果 N 特别大（十万以上）时，还是比较慢的。那么，有没有可能对二分查找做进一步优化呢？我做了一点尝试。
因为在我的系统中，通常是顺序处理某类 component 的，处理顺序会保证 id 是单调递增的（本身按 id 排序）。所以，每次用当前的 id 去另一个有序的 component 集合中查找时，这些查找之间有较强的相关性。比如，正在处理的集合中 id 是 1 3 5 7 9 ，而它需要查找的另一个集合中 id 则是 1 4 5 9 10 ；我们做完一次查找后，下一次查找的位置就在上一次位置靠后一点的附近。利用上这个信息，就有可能提高查找的性能。
我把这个方法称为带猜测的二分查找。即：在二分查找开始前，先猜测一下目标值大致所在的范围。如果恰巧落在范围内，查找虽然还是 O(log N) ，但 N 有可能被极大的缩小。但这个猜测逻辑也不宜过于复杂，我采用的策略是，把目标范围设定在上次成功找到的位置到这个位置向后 64 个 slot 之间。
我做了一些简单的评测，发现在 N 在百万量级时，加入猜测可以比直接二分查找快 2~3 倍左右；当 N 在十万量级时，可以快 70% 左右；在一万量级时，依然有 10% 的收益。
Comments
见上一篇 https://blog.codingnow.com/2021/07/lua_ecs.html
Component 在运行时不可增减。
Entity 可以删除，但删除需要等帧末才生效。
Posted by: Cloud | (10) March 7, 2022 03:52 PM
组件集如果是有序数组的话，那么组件的增删是不是也会导致重排？如果增删频繁的话，这个开销感觉应该不会很小，不知道是不是有什么特别的处理方式可以减少或者避免维持有序带来的开销？
Posted by: Anonymous | (9) March 7, 2022 11:56 AM
这里用 vEB tree 意义不大。理论上复杂度是 O(log log M) 但此处的 M 是整个 id 空间，对于 32bit 的空间来说，log M 就已经有 64K 了。它的下限太大，得不偿失。更不用说数据结构的复杂度。
本质上 vEB tree 也就是递归分桶装。我认为它只在特定情况下比其它树结构好，但结构本身却没能简化。
Posted by: Cloud | (8) September 18, 2021 12:59 PM
如果输入规模足够大，是否可以考虑用van emde boas tree呢？增删改查是O(loglog U).
Posted by: Zerman | (7) September 18, 2021 12:05 PM
"组件在组件集数组中保持有序，按 id 排序"
是如何在“对老id的增删组件时”保持高效的呢？
Posted by: Vincent | (6) July 5, 2021 09:22 PM
@Liu Liu
eytzinger order 是把一个排序二叉树排列到一个数组里，这对 id 的值非均匀分布时的确优于连续排列的二分查找（因为可以更快的检索到目标区间）。但我认为维持一个 eytzinger order 是非常昂贵的，而且在我的情景中，新的 id 的值总是大于旧值，这无异于需要一个更复杂的平衡树。
二分查找并不慢，但是它是稳定的 O(log N) 复杂度。当千量级时就是 10 次比较，而百万量级的时候则是 20 次；我这里引入的额外参数（finger）是希望在百万量级时比较次数在 10 次以下。
@caskeep
我这几年尝试过许多数据结构，包括 “维护entity于component的关系”。
这次的指导思路是，去掉所有冗余（的索引）信息。
我认为，索引之所以需要，是因为我们希望尽可能的在获取信息的时候能够 O(1) 访问到。但实际上，OOD 中，最关键的要素是用恰当的次序处理数据，回避不必要的随机访问。所以，追求任何场景的 O(1) 是没有必要的。找到关键路径，让这条路径上的访问保持 O(1) 就够了。而且 O(1) 只表明数量级，同样是 O(1) ，不同的数据结构（布局）的处理成本还是有差别的。
当无法确定复杂能带来多大好处前，保持简单最重要。
另外，索引之所以为索引，它不表达数据，而是只是为了缩短检索数据的时间。维护索引的（时间和复杂度）成本往往被忽略了。我倾向于不维护持久的索引信息，索引相关的结构以不侵入数据区比较好。
Posted by: Cloud | (5) June 14, 2021 08:27 AM
最近刚刚开始接触Data Oriented Design，我也在尝试实现自己的ecs系统，遇到不少思路与实现的问题。
对于这样建立entity于component的关系的方式没有想过，之前的思路总是使用额外的内存结构维护entity于component的关系，感谢开阔了我的思路。
其他的一点想法是：
1.binary search如果需要有序，是否可以使用类似slopMap或者radixSort的方式代替？毕竟都是连续的内存，data locality性能都很好？
2.在Data-oriented design (2018) by Richard Fabian一书中提出过以及在CpuCacheLine（64Bytes）上做的skipList的优化，位于chatper 6，使用每次cacheLine剩余的”量“携带额外的skipList信息（这些信息位于cpu的L1cache上，访问基本上是免费的），利用这些信息完成定向”跳跃“，实现性能提升。是否可以通过这样的信息，及时使算法复杂度提升，但是实际的运行时间却降低了？
刚刚入门，如果理解错误，感谢告知！
Posted by: caskeep | (4) June 13, 2021 01:02 PM
二分慢也有可能是数据布局的原因？大家都说还是eytzinger快点 https://cglab.ca/~morin/misc/arraylayout-v2/
Posted by: Liu Liu | (3) June 13, 2021 12:17 PM
作点补充，学术上把这种叫finger search。
Posted by: Anonymous | (2) June 12, 2021 09:17 PM
期待开源
Posted by: Oracle | (1) June 11, 2021 06:31 PM