间断储存的字符串

981次阅读
没有评论

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

内存管理和其它资源管理有明显的不同。管理内存有点像切蛋糕,从整块蛋糕上切下需要的那块,但归还的时候却因为支离破碎难以合并起来满足后续用途。举个极端的例子:如果内存堆有 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 的内存数据库,或许我会选用这样的数据结构。它有更紧凑的内存模型,而且更方便持久化。

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

内存管理和其它资源管理有明显的不同。管理内存有点像切蛋糕,从整块蛋糕上切下需要的那块,但归还的时候却因为支离破碎难以合并起来满足后续用途。举个极端的例子:如果内存堆有 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 的内存数据库,或许我会选用这样的数据结构。它有更紧凑的内存模型,而且更方便持久化。

 

正文完
可以使用微信扫码关注公众号(ID:xzluomor)
post-qrcode
 
评论(没有评论)
Generated by Feedzy