C 语言缺乏原生的 string 类型的支持,这使得字符串管理非常烦琐。我在 2006 年左右的一个项目中,我根据项目实际情况,简化了 C string 库,把大部分 string 都做了string interning,并直到进程退出再释放 string interning pool 。
但这种用法毕竟不够通用。
今天读到 facebook 开源的libPhenom,里面也实现了一个简单的 string 库。我有些想法。
libphenom 的 string 库核心想针对问题是尽量的减少堆上内存的动态分配。它把大部分临时字符串都放在栈上处理,也提供了用户自定义串空间的方法。我觉得这个方向是不错的,但是其实大可不必提供太多的弹性,只要尽量让临时字符串存在于栈上即可。而另一个很重要的功能,也就是 string interning 我认为更有实用性。
string interning 可以实现 symbol 类型,对于类似 json/xml 的解析来说非常有意义。可以节约许多内存,而且可以加快 symbol 的比较和 hash 速度。不过对所有字符串无差别的做 interning 有可能因为外部输入多变也被攻击。对 interning 的字符串做引用计数也会降低性能。
我的想法是,只对短字符串做 interning ,这和 Lua 5.2.2 的策略一致。但是我们可以不再回收 interning pool ,所有短字符串都一直保留在内存中。大部分情况下,这样处理风险不大。
临时字符串一律放在栈上,这可以减少动态内存分配。除非字符串太长,有可能栈溢出才放在堆里去。
如果用户需要长期持有字符串,或是需要把当前栈上的字符串返回,那么再转移到堆上也不晚。堆上的字符串可以使用引用计数来管理,这样对于长字符串的传递,就可以省去逐字节拷贝的代价,又可以及时的回收。
有了这些特性,在此基础上实现 hashmap 等数据结构性能就会比较高。
为了简化生命期管理,如果一个字符串被引用次数太多,也可以把它变成一个永久字符串。一般来说,动态字符串是很难被数万次的引用的。
常量字符串也很重要,尤其是常量字符串比较短时更加重要。这样,经过 interning 的常量字符串和其它变量进行比较时,开销比较小。C 语言的模块没有默认初始化流程,所以只能用 static 变量加惰性初始化来模拟。
我今天花了几个小时实现了这么个玩具,主要是验证一下 string 库的 API 设计构想。目前开源在 github 上了,有兴趣的同学可以看一眼。但注意:这只是一个玩具库,我没有用在任何已有的项目上。库里面写了不少线程安全有关的代码,也完全没有被验证过。
好在库篇幅很小,如果有哪些好心的同学想完善它,尽管提交 pull request 。我会一起 review 代码的。
原文链接: [url=http://www.udpwork.com/redirect/10691]http://blog.codingnow.com/2013/09/cstring.html[/url]