云风的 BLOG: 间断储存的字符串

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

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

Comments

C语言池化字符串，可以说是（未被广泛认可的？）C语言程序员的浪漫了（虽然有rope（数据结构），看到这标题我第一时间想到的是logn条长度为2^i的分片在类似buddy分配器上组成的串（可能太骚对字符串、普通table的key们等有特殊属性的内存，如被引用次数有保证、无对外引用的情况，换用引用计数或其他策略管理，我也是想过动过手，但没改出来（还在查运行时爆炸）就离职了【悲

Posted by: farter | (22) January 24, 2023 11:03 PM

最近发现一个狠的东西，Lua的IDE，ZeroBraneStudio，简单估计了一下，有60%以上的代码是用Lua完成的，超过了30万行Lua程序。

Posted by: rawa459 | (21) November 26, 2022 06:06 AM

还有一个问题，比如编译器准备开辟一个新的1G的内存空间，如果是UnixV的x86的移植版本内核，本质上这部分是不连续的，可以是很多段的内存片段，但是从编译器寻址的角度是连续的。win95~winxp系统也是这样的，比如一个exe文件，100M,把它加载进入内存立刻复制成为bin文件，再放到磁盘，变成了200M甚至更多。

Posted by: rawa459 | (20) November 26, 2022 04:13 AM

另外，我再重复一次一个问题，可能是你的疑惑（2014），易语言和aauto都是抄袭的delphi，这件事我亲自证实了。

Posted by: rawa459 | (19) November 26, 2022 01:25 AM

我以为你会问，C#哪里比java优秀，关于字符串处理方面，好吧，我估计错了，哈哈。

Posted by: rawa459 | (18) November 26, 2022 01:06 AM

好吧，我闪了，我发的这些其实跟主题关系相当的密切，之所以C++现在在高端领域有这么强的统治力，就是因为通过配置空间（内存），1M的RAM可以运行，1T的RAM一样可以运行原理类似的程序。

Posted by: rawa459 | (17) November 26, 2022 01:00 AM

@rawa459 请不要灌版。不要发和主题无关的留言。如果你有什么要表达的观点，可以自己写 blog 。

Posted by: Cloud | (16) November 25, 2022 07:34 PM

现在中国大力的推广openRISCv，我没有仔细看具体的构架细节，但是从我再2009年对于openrisc1200的研究来看，这种芯片的内存管理（mmu）略微比mips好一些，X86的硬件寻址指令有4中，软寻址有7种（后来的9种），ARM的寻址硬件是2种（立即数和偏移（寄存器）），软寻址是9种，mips是一种，就是线性寻址（软可以也是9种），把所有的内存视为一个数列。openRISC1200最理想的定制情况，也就基本达到arm7或者arm7的寻址能力和速度。Lua这种语言可以用在openRISCv芯片上，也许还有一个成长空间，类似当年的forch。

Posted by: rawa459 | (15) November 25, 2022 12:26 AM

如果全世界的程序，都是基于arm芯片来设计（x86年代就做到了，Wintel联盟市场占有率90%），那就没有任何操作系统内核层面的问题，内存管理是操作系统内核和CPU（严格来说是L2高速缓冲）打交道的层面，之所以出现这么多的问题，就是很多程序是移植过来的，有的是unix迁移到linux的工具链（TK/TCL）,有的是win各种版本迁移过来的，这个跟wine执行可不一样，我指的是移植，还有的是IBM的，SUN的，HPUX的，等等等，出现内存的浪费这都是最小的问题，不然交叉编译器也不会把j2ee干趴了。

Posted by: rawa459 | (14) November 24, 2022 11:28 PM

除非必要，不要去做操作系统应该做的事。（J2SDK的名言。）

Posted by: rawa459 | (13) November 24, 2022 11:06 PM

linux的系统的硬件的实际能力千差万别，这个内存适配东西，我觉得只是针对哈佛结构的arm的mmu有意义，对于x86和intel64位平台意义不大，段、页、平坦，这些内存寻址和分配概念，源自386DX芯片，那个时候IBM的巨型机使用的是ECC校验内存来保证内存不出错，而事实上386DX用千分之一的成本做到了这一点，你可以使用软件，也就是OS内核来做到ECC同样的事，win95大量的使用的是段偏移寻址，极小的内存，性能强大的让对手却步，同时期的Unix的X86移植版本，成为美国历史上最成功的商业工作组系统（scoUnix和很多公司的x86Unix版本），这奠定了intel击垮IBM的基础。

Posted by: rawa459 | (12) November 24, 2022 10:41 PM

jemalloc 能给出详细的数据，可以在不同的项目中嵌入 jemalloc 查看具体数据。 jemalloc 会报告申请的内存总量(allocation), 管理这些内存额外使用的元信息(metadata), 实际使用的物理内存数量(mapped) ，占用的虚拟空间数量(resident) ，以及占用的物理内存中暂时保留下来供未来一段时间使用，而避免频繁 map 的空间(retained) 。但即使开启最激进的回收策略，mapped 还是会远超过 allocation 。这就是无法避免的碎片率。

Posted by: Cloud | (11) November 24, 2022 10:22 PM

事实是，4K 的页中，如果管理不当，会充斥着大量碎片。比如你分配了 128 块 32 字节的数据，用最优秀的管理算法，紧凑的填满了 4K 页。然后间隔着释放了其中 64 块。即每个 32 字节占用后面都有 32 字节的空余（外部碎片）。从外部看，你释放了一半的内存 2K ，但实际上，你无法再从这 4K 页中分配出任意大于 32 字节的内存。这 2K 内存对于超过 32 字节的应用场景就消失了。或者，你分配 20 字节，管理器出于减少碎片方便再利用的角度，分配给你 32 字节，那么在这 20 字节回收之前，有 12 字节（内部碎片）也无法被再利用。无论是上面哪种碎片（内部/外部）的，在实际应用场合中，都轻易超过 30% 的实际内存用量。这和 32bit 还是 64bit 架构无关。

Posted by: Cloud | (10) November 24, 2022 10:02 PM

> 如果内存堆有 2G 大小，如果碰巧在正中间分配了几个字节而从未释放，这个堆就被永久的分成了两个不足 1G 的分片。之后再无可能从这个 2G 大小的堆中分配出 1G 的内存块。实际物理内存占用只有中间一个4K大小的页而已, 浪费的只是虚拟空间. 而且现代的分配器, 不会在分配1G的堆上分配几个字节, 而是分成很多个档位的池去管理, 实际浪费真的不多.

Posted by: dwing | (9) November 24, 2022 09:26 PM

java是1995年设计成型的，不知道后来甲骨文进行了多少彻底的改进，但是改进这个东西并不简单，java发起GC的条件，在默认情况下是物理内存，超过80%，自动发起GC，GC工作的两种模式是标记（Lua只有这一种），还有就是root链分析（这个在C++里叫父进程强制），后来微软抄袭java，发布了C#和dotnet计划，对于java的某些问题进行了改进，微软在这方面最大的工作量其实是C++和dotnet的结合，革新了WPF函数库（原来是MFC），现在由于novell公司，和我说的那个人的贡献，（微软自己也完成了OS迁移到ARM上的项目）现在ARM上有完整的dotnet和C++工具链，这是区别于苹果的LLVM的。

Posted by: rawa459 | (8) November 24, 2022 07:39 PM

内存碎片在 64bit 架构下不在于虚拟地址空间耗尽而 OOM 崩溃；而是多消耗了 50% 以上的物理内存。在手机操作系统下，物理内存超标也意味着系统会自动杀掉进程。

Posted by: Cloud | (7) November 24, 2022 04:04 PM

现在64位程序的虚拟内存空间足够大到内存碎片的问题没那么严重了. 而且一些比较先进的分配器会把短分配和长分配的堆空间分开管理.

Posted by: dwing | (6) November 24, 2022 10:11 AM

我一直想不通，Miguel de lcaza这个人为啥对于开源的dotnet解释器有如此大的热情，并且持之以恒这么久，今年年初我想通了，原因并不是在于C#，而是在于C++，要想在安卓上编译和执行C++代码，不是一件简单的事，如果能够完美的运行dotnet虚拟机，那么C++的问题也就迎刃而解，这是除去苹果的LLVM解决方案之外，巧妙的利用了微软的C++工具链，虽然mono并不尽人意，吃内存太大，但是毕竟这个环境构建一个基于安卓，区别于javaSDK的C++编译和执行环境，这是这个家伙这么大劲头的根本原因。

Posted by: rawa459 | (5) November 23, 2022 04:48 AM

存储紧凑，读写任意位置为 O(n); 从中插入，删除字符为 O(n); 字符串连接，分割为 O(n). 看下来，是一个为了连续读取(整块读取)和存储紧凑为目的的数据结构。字符串的间断存储在编辑器里用的很广泛. ocaml 的 toplevel, utop. 其编辑器引擎 zed 的字符串管理，用的是 rope 数据结构。读写任意位置，从中插入，删除字符，字符串连接，分割的操作均为 O(log N), 存储没那么紧凑，速度却是飞快。 https://github.com/ocaml-community/zed/blob/master/src/zed_rope.ml https://en.wikipedia.org/wiki/Rope_(data_structure)

Posted by: kandu | (4) November 22, 2022 09:52 AM

你说的这个问题，是世界性的难题，比如谷歌的搜索服务器，会把全世界数以万兆T的URL缓存在阵列服务器上，然后尽最大可能迅速地给用户搜索结果，但是，Lua这种规模的语言，得心应手的处理这件事，这根本是不可能的。

Posted by: rawa459 | (3) November 21, 2022 04:31 PM

很多人骂微软，事实上对于字符串的处理和正则表达式的迅速计算，C#比java优秀的多，这种技术成属于大约2003年，就已经做到远远超越java语言了。

Posted by: rawa459 | (2) November 21, 2022 04:17 PM

哈哈，在2020年，一个不知名的论坛跟李开复争论过java的string的问题，短的字符串，比如URL或者几千字的源码，这倒是没什么，但是如果一个java的string是1亿个字符，那么java会怎样存储这个string对象，其实这种情况，java的string的属性栈就满了，他只能存储大约1G内存这么大的子串表，其他的子串，会在你使用的时候再去计算。因为1G字节全是字符串，也就是10亿个字符而已。string的子串预存是按照正则表达式来计算的。

Posted by: rawa459 | (1) November 21, 2022 04:12 PM

云风的 BLOG

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

间断储存的字符串

Comments

Post a comment