云风的 BLOG: 一个简单的 C string 库

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 代码的。 :)

Comments

泪奔，终于看懂咯！

Posted by: 无闻 | (17) October 23, 2013 04:25 PM

看起来挺复杂的但是好像还不错哦 http://www.haobitou.com#03

Posted by: 好笔头业务云笔记 | (16) September 24, 2013 03:27 PM

实在不能接受随随便便加spin lock。如果想给别人提示哪里加锁来保证thread-safety，哪怕是个no-op的macro也好。这样看似thread-safe其实不一定好麻烦的……

Posted by: Liu Liu | (15) September 24, 2013 08:45 AM

utf8适合用于传输和保存，但是在内存里进行字符串处理的话则非常麻烦。在内存中还是用USC2来处理最方便，完全不用考虑变长字符的问题。

Posted by: qiaoje | (14) September 22, 2013 11:33 AM

这种设计过于复杂了，实现复杂，使用也复杂，性能不确定。我还是喜欢redis里面的sds.c的设计，简单的带长度的字符串，并且可以和char *兼容。

Posted by: 难易 | (13) September 21, 2013 02:14 PM

说C++ string不好，你们能造出个比string好的轮子吗？

Posted by: 路人甲 | (12) September 18, 2013 05:40 PM

泛化的string和UTF类字符串不是一个概念,各有各的优势和使用范围: 前者的目的就是每个字符是固定的类型,提供了便捷的随机访问能力,一般用于在内存中保存,如果考虑到大于16位unicode的字符,就只能考虑全局32位定长的字符, 而UTF8字符串更适合存储,保存到网络或磁盘,没有字节顺序问题,节约空间,不过UTF16却缺失了这些好处,存在的意义不大, 估计这也是windows使用UCS2作为核心字符串的编码而不是UTF8的原因,虽然我个人还是更倾向于UTF8一统天下, STL的string在我看来,仅仅看作字符数组而已,实用功能还欠缺的多,但还是符合STL的制作理念,自己做开发可以不用它,但不能因为自己理念的不同而说STL设计的不好

Posted by: dwing | (11) September 18, 2013 10:07 AM

我觉得basic_string使用char和wchar来区分实在太不帅气了。应该用字符编码来区分。类似这种 basic_string; 最好就连文件流也使用这种形式。

Posted by: hkt | (10) September 18, 2013 09:15 AM

在现实需求中基于 char 的 string 是要处理变长字符集的，实际上 wstring 也是，只是很多人忽视了 utf-16 实际上也是变长字符集这个事实，把它简化成等宽字符串了而已。而 Utf-8 处理变长字符的方式和 utf-16 的很不一样，这是模版很难解决的。更别说其它编码方案了。最终，一个完善的，使用于开发者平台的 string 类很可能还得从 std::string 扩展到诸如 utf8string 这样的类去实现，底层提供的那点范化根本微不足道。

Posted by: cloud | (9) September 17, 2013 11:11 PM

我们活在一个现实的世界。对于 String 类型，内部使用多宽的字符，选择实在有限，且一个系统使用 char 还是更宽的字符，是和系统平台的选择强相关的。约束越强的需求，越容易精确简洁高效的实现，所以我认为泛化需求的 basic_string 模版是一种画蛇添足。高效这点在模版中可以用特例化来解决，但这仿佛是绕了一大圈回到了原点。即使是 string 和 wstring 有再多的相同点，本也可以由不同平台的人分别维护的。我也同样认为 stl 把简单的连续内存抽象成可随机访问的容器，再套上迭代器去操作它是完全没有必要的抽象。越是靠近底层（我指远离上层业务逻辑）就应该越精确的贴近机器模型，而不是架设在各种抽象之上。这无关是用面向对象还是用范型的抽象方法。

Posted by: Cloud | (8) September 17, 2013 10:58 PM

@Cloud 没理解我的意思, std::string 和 std::wstring 如果不用 std::basic_string 来抽象, 那么二者大部分代码都是重复代码, 除了char和wchar_t基本没什么区别如果一个项目只是自己重写的string或者wstring, 这没什么不好, 但STL的所有用户不可能只用string或只用wstring, 还可能有32位字符的用户, 我并不是偏袒 basic_string 的做法, 但STL的原则使之只能这么做

Posted by: dwing | (7) September 17, 2013 10:46 PM

@dwing 我的意思是, std::string 基于一个模板来实现不好。倒不是因为性能问题,我也不觉得,如果有一个非模板实现的 std::string 也不会高效到哪去。同样，也不是用起来不方便。反正也不会有人直接用 std::basic_string 。我是说不必要的泛化多数情况下是不必要的。同时用 std:string 和 std::wstring 更没有必要。如果有应用需要在 UTF-16 和 UTF-8 间转换，也是应该在 std::string 内提供专门的方法的。

Posted by: Cloud | (6) September 17, 2013 10:15 PM

std::string不是模板类,它只是模板类basic_string的一种实例,string和wstring都是很常用的,STL作为一种泛化的库,抽象出basic_string模板类是很正常的做法. 不过STL为了尽可能的泛化,也导致方便性和性能不够好,尤其是C++用户经常在乎性能,所以C/C++重造轮子的事也无可厚非.

Posted by: dwing | (5) September 17, 2013 10:04 PM

@Cloud 这些性质，不会减少code的灵活性？甚至导致更复杂的设计？

Posted by: coder_L | (4) September 17, 2013 09:20 PM

@coder_L 我觉得重载构造函数，以及隐式类型转换都很容易隐藏掉不该隐藏的细节, 加大维护的困难。所以我现在更喜欢 Obj-C 中那样的构造函数，以及 golang 中禁止函数重载的设计。 btw, 我也不喜欢 std::string 设计成模板类。在同一个项目中，几乎只会使用一种字符类型的方案。

Posted by: Cloud | (3) September 17, 2013 09:02 PM

支持下

Posted by: xing | (2) September 17, 2013 09:00 PM

云风，你还记得全C++标准库string类的所有构造函数么？今天重看《C++ primer》，感叹了半天。记不住勒

Posted by: coder_L | (1) September 17, 2013 08:56 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

一个简单的 C string 库

Comments

Post a comment