« skynet 1.6.0 | 返回首页 | 触摸屏上的一些交互设计问题 »

间断储存的字符串

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

内存管理和其它资源管理有明显的不同。管理内存有点像切蛋糕,从整块蛋糕上切下需要的那块,但归还的时候却因为支离破碎难以合并起来满足后续用途。举个极端的例子:如果内存堆有 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们等有特殊属性的内存,如被引用次数有保证、无对外引用的情况,换用引用计数或其他策略管理,我也是想过动过手,但没改出来(还在查运行时爆炸)就离职了【悲

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

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

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

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

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

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

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

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

除非必要,不要去做操作系统应该做的事。(J2SDK的名言。)

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

jemalloc 能给出详细的数据,可以在不同的项目中嵌入 jemalloc 查看具体数据。

jemalloc 会报告申请的内存总量(allocation), 管理这些内存额外使用的元信息(metadata), 实际使用的物理内存数量(mapped) ,占用的虚拟空间数量(resident) ,以及占用的物理内存中暂时保留下来供未来一段时间使用,而避免频繁 map 的空间(retained) 。

但即使开启最激进的回收策略,mapped 还是会远超过 allocation 。这就是无法避免的碎片率。

事实是,4K 的页中,如果管理不当,会充斥着大量碎片。

比如你分配了 128 块 32 字节的数据,用最优秀的管理算法,紧凑的填满了 4K 页。然后间隔着释放了其中 64 块。即每个 32 字节占用后面都有 32 字节的空余(外部碎片)。

从外部看,你释放了一半的内存 2K ,但实际上,你无法再从这 4K 页中分配出任意大于 32 字节的内存。 这 2K 内存对于超过 32 字节的应用场景就消失了。

或者,你分配 20 字节,管理器出于减少碎片方便再利用的角度,分配给你 32 字节,那么在这 20 字节回收之前,有 12 字节(内部碎片)也无法被再利用。

无论是上面哪种碎片(内部/外部)的,在实际应用场合中,都轻易超过 30% 的实际内存用量。这和 32bit 还是 64bit 架构无关。

> 如果内存堆有 2G 大小,如果碰巧在正中间分配了几个字节而从未释放,这个堆就被永久的分成了两个不足 1G 的分片。之后再无可能从这个 2G 大小的堆中分配出 1G 的内存块。

实际物理内存占用只有中间一个4K大小的页而已, 浪费的只是虚拟空间.
而且现代的分配器, 不会在分配1G的堆上分配几个字节, 而是分成很多个档位的池去管理, 实际浪费真的不多.

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的。

内存碎片在 64bit 架构下不在于虚拟地址空间耗尽而 OOM 崩溃;而是多消耗了 50% 以上的物理内存。

在手机操作系统下,物理内存超标也意味着系统会自动杀掉进程。

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

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

存储紧凑,读写任意位置为 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)

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

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

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

Post a comment

非这个主题相关的留言请到:留言本