并发 Hash Map 的实现
Lua 中的短字符串做了 string interning 的处理,即在同一个虚拟机内,值相同的字符串只存在一份。这可以极大的提高用字符串做 key 的 hash 表的查询速度。因为字符串比较的时间复杂度从 O(n) 下降到 O(1) ,比较查询的 key 和 hash 表内的 key 是否一致,只需要对比一下对象的指针是否相同即可。
我在解决多 Lua 虚拟机共享字符串对象这个问题时,合并了不同的 Lua 虚拟机中的短字符串表。让同一进程所有虚拟机共享一个短字符串表( SSM )。
我最初在实现 SSM 的时候,考虑到多虚拟机 GC 的复杂性,采用了只增不减的方案。即让部分短字符串进入 SSM ,设置一个上限,避免 SSM 无线膨胀。但 Lua 并没有把经过 interning 处理的字符串作为独立类型,目前只用字符串长度作为区分,也就是无法和不 interning 的短字符串共存。所以,那些已存在本地虚拟机短字符串表中的字符串,就不从 SSM 中获取对象。
修改过 Lua 的 string interning 算法是这样的:
查看字符串是否存在于本地字符串表 (LSM) 如果存在,就立刻返回。这一步和原版 Lua 一致。
查看字符串是否存在于 SSM ,如果存在,就返回。
检查是否 SSM 上限已到,如果不能再增加新字符串,把字符串添加到 LSM ,返回。
将字符串添加到 SSM ,返回。