快速字符串对象比较
这段时间在想办法解决多个 lua 虚拟机间共享对象的问题。这里的一个核心问题是，lua 的短字符串做了 interning ，虚拟机在比较两个字符串时只需要比较字符串对象指针即可。而多个 lua vm 如果想共享数据，必须解决这个问题。前段时间实现的 并发 Hash Map ，和 共享表 就是在这方面做的努力。
随着 lua 5.4 的临近，我最近尝试了在 lua 5.4 的 alpha 版上做类似的 patch 。但是 lua 5.4 对 gc 的修改极大，这让我尝试去找其它的办法来做这件事。
我觉得，如果允许 vm 在处理短字符串比较时，不严格遵守 interning 的约定，那么就不再需要对 gc 流程做改造了。这样，从外部共享来的字符串，只要做全量值比较，依然可以得到正确的结果。
这样的修改固然对 lua 的代码影响极小，但很可能会有很大的性能损失。毕竟，字符串比较从原来的 O(1) 一次指针比较，变成了复杂得多的 memcmp O(n) 。而这明显是 vm 的性能瓶颈所在。
我首先想的是把 lua 字符串对象 TString 从一个连续结构体改造成包含一个指针的间接引用。也就是说 TString 里不再直接包含字符串数据，而引用另一块数据块。如果首次比较两个 TString ，我们可以先比较内部的数据指针，不同的话再进一步比较数据内容。如果数据内容相同，就把两个内部指针合并成同一个。下次比较就可以通过比较指针完成。
但是，在多线程环境下，简单的引用计数却很难管理好这个内部数据块指针的生命期。我想了很久的无锁算法，感觉无解。可如果加锁，损失的性能或许更大，甚至大于直接比较短字符串的内存（毕竟最多才 40 字节）。
今天，我突然想到另一个巧妙地方法，非常值得一提。
我们可以给每个 TString 对象增加一个 64bit id 。一般情况下，这个 id 都是 0 。当我们需要把一个字符串共享出去时，则用简单的原子自增的方式分配一个唯一 id 给它。由于 id 有 64bit 所以不需要考虑 id 用完的情况。
当我们比较两个 TString 时，先比较 id 是否相同。如果 id 不同，再用 memcmp 做全量比较，如果最终结果相同，我们就把 id 较小的那个 TString 的 id 修改成较大的那个。
如果 id 相同，则可以认为两个 TString 的值相同，不需要进一步做 memcmp。
比如，在 A B 两个虚拟机中，都有字符串 "foo" ，它们都把自己共享出去。一开始 A 中的 foo id 为 1 ，B 中的 foo id 为 2 。
在 C 这个虚拟机中，一开始也有字符串 foo ，id 为 0 。当我们第一次将 C 本地的 foo 和 A 引入的 foo 比较后，C 的 foo 的 id 会修改为 1 。再次比较就不再需要 memcmp 。如果其后和 B 引入的 foo 比较，本地的 foo 的 id 会变成 2 ，再次遇到 A 的 foo ，则会把 A 的 id 也提升为 2 。
即使 A B 共享的 foo 在多线程下，被不同的虚拟机共享，也不需要加锁，因为 id 永远是向上提升，最终都会稳定下来。而且这个 id 仅仅是作为一个比较的参考而已。
通常这个方法，值相同的对象，在经过第一次比较后，以后的每次比较都可以通过一个 id 比较得到结果；值不同的对象，它们的 hash 值也几乎不可能相同，所以再后续的 hash 值比较中也能得到结果。
Comments
这个字符串对象内部即保存字符串指针，又保存一个64位ID.如果你指针是64位的，那一个对象就16个字节了，字符串对象按道理说应该是粒度比较小的对象。很容易使用海量TSTRING，你这个比较费内存，即使你做了相同字符串复用。
Posted by: A | (9) July 23, 2019 10:34 AM
为什么ID不同还需要memcmp来比较下呢？就不能ID同就是相等，不同就不相等吗
Posted by: A | (8) July 23, 2019 10:29 AM
这个方法非常通用啊, 不仅适用于字符串.
Posted by: cat | (7) June 26, 2019 08:58 AM
即使是原子自增，也会造成这个共享的id所在的cache line被多个处理器访问。会不会成为并发的瓶颈呢？
Posted by: wks | (6) June 25, 2019 09:18 PM
向下合并更好。
这里之所以用的向上合并，因为我暂时对 lua 的修改保留了本地的 interning 表。我让 local 的字符串都是 0 ，其它外部的字符串大于 0 。我希望在本地字符串和外部字符串比较之后，可以通过向上合并提升。当然这个细节也可以修改。
Posted by: Cloud | (5) June 18, 2019 02:38 PM
有点像并查集的思路
向下合并感觉会好一点，大部分串很快就稳定了，而向上的话每次出现一个新的id，要把所有瞳字符串都改一遍
Posted by: resty | (4) June 18, 2019 12:04 PM
虽然不需要锁, 但比较id不同时,memcmp前要加memory barrier才能保证正确性吧.
Posted by: dwing | (3) June 18, 2019 11:12 AM
常规hash的优势在字符串较短的情况下没有任何体现
其实唯一编号就是一种hash
而且是一种碰撞率为0的hash
常规hash的优势在大数据量零知识验证等等
Posted by: threezhiwang | (2) June 18, 2019 10:11 AM
虚拟hash，仅用作比较
其实指针也是一种hash
按此逻辑
任意数据都可以用这样的方法来比较
如果数量超64bit，可以N个id来标识
哈哈
Posted by: joe wulf | (1) June 18, 2019 12:46 AM