字符串比较用 id 管理策略
前两天写了 快速字符串对象比较 ，我把这个想法提交到 Lua 的邮件列表，建议 Lua 的未来版本去掉长短字符串，不做 string interning ，用这个方法解决字符串比较的性能问题。Lua 的主要维护者 Reberbo 表示了兴趣，同时也提出了几点问题。
其中一个问题是，Lua 未必运行在 64bit 平台上，所以并没有直接使用 64bit 整数类型。而如果使用 32bit id 就无法简单的通过自增来保证 id 永远唯一。
我就这个问题考虑了几天，提了好几个解决方案，其中一个方案我最为满意，在这里重新用中文记录一下。
我们可以把 32bit id 分为两个区，0 到 0x7fffffff 为 old 区，0x80000000 到 0xffffffff 为 young 区。
一开始，id 从 0x80000000 开始分配，所有的新增字符串都属于 young 。
每次 GC ，在 sweep 阶段，把所有的 young id 重新分配到 old 区。这样，每轮只改变当轮新增的 id 。由于 gc 是分步进行的，sweep 过程也可能新增 id ，所以在 sweep 阶段开始时，让新增 id 直接放在 old 区，也就是说， sweep 阶段只会把 id 从 young 变成 old ，或直接增加 old ，不会产生新的 young id 。
sweep 结束后，再把新增 id 重新调回 0x80000000 。
在比较字符串时，如果字符串值相同，但 id 不同，把较大的 id 变成较小的那个。这样，如果两个 id 一个是 young 一个是 old ，young id 也会变成 old id 。
在这个算法下，old id 的自增速度就会大大的减慢。因为：一轮 gc 中，临时字符串会被回收掉，不占用 old id 的空间；比较过程很有可能把新增的 young id 变成 old id ，不会等到 sweep 阶段再分配新的 old id 。
如果 old id 快用完了，这种情况虽然罕见，但出现了还是有方法的。一个确保方案是用一个原子过程，遍历所有的字符串，把所有的 old id 重新排列到 young 区。因为 old 区全部空出来了，这样上面正常的 gc 流程又能正确工作了。
Comments
云风大哥，3d引擎啥时候开源？
Posted by: 汪疯 | (9) July 5, 2019 08:02 PM
为什么64位id就能保证id不唯一。
Posted by: luan | (8) July 2, 2019 04:26 PM
学习了。
Posted by: 技术人成长 | (7) June 30, 2019 08:41 PM
是的，应该直接在 old 区重排。
一开始这样设计是因为考虑到整理的工作可能是分步的，就不能在同一个区重排。后来又考虑分步操作有一些复杂因素，就加上了 原子操作 的限定。而如果保证一次做完的话，直接排在 old 区也很简单。
Posted by: Cloud | (6) June 27, 2019 04:16 PM
想了解下最后把old id重新排列到young区，为什么不就地在old区重新分配排列一次
Posted by: Riemann | (5) June 27, 2019 03:25 PM
云风大哥，那些日志的目录404了
https://blog.codingnow.com/cloud/PassedDays
https://blog.codingnow.com/2008/05/passed_days_11.html
Posted by: netease | (4) June 26, 2019 02:54 PM
好方案
Posted by: 🐠 | (3) June 26, 2019 09:38 AM
old用完了可以考虑在old上面做缩并，id还放在old里，这样old和young也不用对半分。
Posted by: resty | (2) June 21, 2019 11:55 AM
辗转腾挪，方法又简单可靠，受教了，谢谢分享
Posted by: lmx | (1) June 20, 2019 01:44 PM