间断储存的字符串

1,801次阅读

绝大部分的基础数据结构都是定长的，很容易针对优化它们的内存管理。但字符串是一个例外。

内存管理和其它资源管理有明显的不同。管理内存有点像切蛋糕，从整块蛋糕上切下需要的那块，但归还的时候却因为支离破碎难以合并起来满足后续用途。举个极端的例子：如果内存堆有 2G 大小，如果碰巧在正中间分配了几个字节而从未释放，这个堆就被永久的分成了两个不足 1G 的分片。之后再无可能从这个 2G 大小的堆中分配出 1G 的内存块。

改进内存分配算法或许可以减轻内存碎片的危害，但即使是在此方面做了相当多努力的 jemalloc ，其表现也大大低于一般用户的预期。以我的经验，一个 16G 的内存堆，对于长期运行，需要大量反复分配释放内存的程序，通常能做到 10G 左右的峰值有效内存占用就不错了。这里说的有效内存使用，指你调用 malloc 传入的字节数之和。根据应用程序使用内存的方式不同，这个数字会有很大的不同。

60% 的内存使用率其实已经很好了，但还是会有很多人问，我的内存都去哪了？

尽可能的规范数据结构的大小，并针对它特别管理内存，提高内存使用有效率的方法之一。这相当于分层管理资源，而不是不问青红皂白全部放在一个全局堆中。等长的数据结构在回收之后可以直接再利用，这可以消除大部分的外部内存碎片。

btw, 定长的数据结构对持久化也更友好。

这篇 blog 想探讨的字符串类型，指的是一串不变的、连续的、用以表达某种内在含义的数据。具体可以对应到 Lua 的 string 类型。

初看起来，字符串一定要求内存连续。但仔细推敲的话，这并不是必须的。它只需要对外表达出一串字节就够了。大部分对字符串的功能要求只是表达它的唯一性，对于 Lua 来说，string 视为一个 atom 就可以了，具体由哪些字节构成不那么重要。进一步的要求是这个 atom 可以参与排序，可以用于 table 的 key 。这些都不需要涉及实现上的细节，甚至不需要随机访问内部数据。

对于 Lua 来说，例外是它有很大一部分需求是通过 C 接口和外部交换数据。当内部的类型和外部交换信息时，会把它视为一块连续内存：

const char *lua_tolstring (lua_State *L, int index, size_t *len);

这个 API 决定了，我们必须把一个字符串连续储存在虚拟机内部的固定位置。Lua 未能实现移动式 gc (在 gc 整理内存时，移动内部对象在内存中的实际位置），无法把短小的字符串直接储存在 Value 中（必须以额外的 GCObject 形式），皆是这个原因。

如果我们能改变一下这个交换信息的接口，可能就能获得更大的弹性。比如这样：

const char *lua_tolstring (lua_State *L, int index, size_t *len, char tmp[]);

多传入一个 buffer 数组，允许 API 实现时可以把内部的字符串数据复制进这个外部 buffer。*len 变成一个 inout 参数，输入这个 buffer 的大小，输出字符串的实际大小。使用的时候，tmp[] 通常可放在 C stack 上。Lua 也未必使用这个 buffer。

接下来的工作就是设计新的字符串数据结构了。我想，采用 2+14 字节一小段，64K 小段构成一个大组，是一个不错的选择：

struct stringid_page {
unsigned short header[0x10000];
unsigned char data[0x10000][14];
};

这样，一个整页是 1M 内存，里面最多可以储存 64K 段字符串。2x64K 的 header 用于连接段与段，14x64K 的空间储存实际内容。

对于很短的字符串，它只使用一个段。对应的 header 上的数字指向自己。例如，如果是第 0 段，header[0] 也是 0 ，表示只有这一段；如果字符串较长，需要占用多个段，那么 header 就记录下一段的编号，直到最后一个段的编号指向自己。

管理算法如果倾向于分配出连续的段，那么字符串依旧是连续的（因为 header 和 data 是分离的）。

还剩下一个问题。如何表达字符串的长度呢？如果缺失这个信息，字符串长度就只能是 14 的倍数。常见的做法是额外记录一个字符串长度信息。但我觉得更好的方法是采用 0 结尾，但最好能支持字符串内部也有 0 （二进制安全）。我们可以在最后一个段中，字符串的末尾填充上 00 + n 个 FF。这里 n 的范围 [0,13] 。

如此，在同一个 page 中，用一个 16bit 整数就能索引一个字符串，该字符串的最大长度为 ( 64K * 14 -1 ），超过 900K ，可以满足绝大部分需要了。如果我们支持多个 page ，可以把 page id 和索引编码在一个 32bit 整数里。

我花了一点时间写了一个简单的实现验证这个想法。

https://github.com/cloudwu/stringid

在这个实现中，我还增加了引用计数，方便重复引用相同的字符串。字符串不同于更复杂的 GC 对象，它只能被引用，而不会引用其它对象。引用计数比标记扫描使用更少的内存（标记扫描需要额外的标记位，以及链表指针）。

这些代码不能直接替换 Lua 的字符串实现，但我想可能有类似的运用场合。如果我去实现一个类似 redis 的内存数据库，或许我会选用这样的数据结构。它有更紧凑的内存模型，而且更方便持久化。