文章

低延迟字符串驻留(interning)

没有什么创新,就是读stringleton的介绍文章的时候在想把经典的低延迟技术用在字符串驻留上面,会不会还没人做过。

字符串驻留的接口一般是输入一个字符串,如果它已经被驻留过了(或者说,曾经有跟它完全一样的字符串被驻留过),就返回那个以前驻留的字符串地址;否则记录它的地址并原样返回。

显然,「如果它已经被驻留过」是一次读共享可变状态,「记录它的地址」是一次写共享可变状态,因此需要给状态加锁,并且快速路径起码一次读锁,慢路径还要一次写锁。

那么优化方案就是做分代。本地维护一个可变新生代,全局共享一个只读老生代。

输入一个字符串,首先去老生代里面找,找到了直接返回;否则去新生代里面找,找到了返回,没找到地址写入新生代并原样返回。

老生代没有写,不需要锁;新生代由本地独占,也不需要锁。

同一个新生代可以自己做去重。每个新生代和共享老生代之间没有重复。并发的新生代互相之间可能有重复,因此如果不同新生代返回的符号可以互相见到彼此,就要做假阳性兜底:符号中需要存储自己来自哪个新生代,如果是相同新生代,那么不同的字符串地址必然是不同的字符串;否则,就要回落到比较字符串内容的兜底路径上。哈希的问题更麻烦一些,后面再考虑。

新生代是要周期性写回老生代的。但是可以作为异步背景任务。老生代去重表可以多版本共存(但是不同版本的表对于同一内容的字符串的地址是保持不变的),不影响正确性。

本文由作者按照 CC BY 4.0 进行授权