« October 2022 | Main

November 21, 2022

间断储存的字符串

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

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

November 17, 2022

skynet 1.6.0

最近半个月,因为广州防疫政策,我一直居家办公。找了点时间,给 skynet 做了一年一度的 release 。

这次的 1.6.0 版,相比去年的 1.5.0 版,没有太大的变化。主要是平时积累的一些 bugfix 。它所依赖的第三方库,例如 Lua , jemalloc 我都更新到了最新的版本。

值得一提的是,mongo 的 driver 也更新了。因为 mongo 在最新的版本中已经淘汰了旧的 wire protocol ,如果再不更新,就无法连接新版 mongo server 了。具体讨论可以参看 PR #1649 。因为 mongo 自己的设计原因,我们无法给出一个同时兼容新老版本协议的方案。从这点来看,我个人认为 redis 的底层协议设计就稳定的多。 这么多年更迭基本不需要修改。

这些年,我一直在追踪 Lua 的更迭。我认为 Lua 的源代码是最值得一读的开源代码。作者的编码风格相当严谨,几乎每处细节都严格准循标准,而不仅仅只保证在现有环境下正确。这份严谨也并非从一开始就固有的,是这二十多年来逐步形成的。

我的硬盘上留有几乎所有 Lua 发行版的源代码,经常对比阅读。自从 Lua 在 github 上镜像了开发仓库后,我就习惯阅读它的每一个 commit ,经常能学到一些东西。

比如最近的这个:把 stack 的扩展从 free / copy / alloc 改成了 realloc 。

因为 realloc 可能会移动内存,引用 stack 内的地址的指针需要重新计算。如果以我通常的做法,求出新老地址的偏移量,然后加在新地址指针上就好了。

但是 Lua 的作者选用了另一种方案:在 realloc 生效之前,将指针转换为 stack 的 offset ;realloc 之后再转换为新指针。它这样做的原因是:

In ISO C, any pointer use after the pointer has been deallocated is undefined behavior. So, before the reallocation, all pointers are changed to offsets, and after the reallocation they are changed back to pointers.

就是说,ISO C 对使用被释放的指针的行为是未定义的。这里指的是使用,而不仅仅是解引用。我相信现存的硬件上,对释放的指针地址本身做计算都是安全的,但这种正确性从标准来说,还是属于未定义的行为。

记得前段时间在 Lua 的邮件列表中还看到过关于指针的另一处讨论:Lua 的作者解释为什么没有用 memset 0 初始化包含有指针的数据结构。他说,从标准的定义看,NULL 未必是数值 0 。所以必须用 = NULL 去初始化指针。

November 09, 2022

被干眼症结膜炎困扰的这几年

这几年我一直被干眼症和结膜炎困扰。疫情之前,每次洗澡后就双眼通红。但似乎并无其他影响,也没怎么在意。后来慢慢的,眼睛就容易发干,经常疲劳。严重的时候眼睛几乎睁不开。最受影响是在开车的时候,因为无法休息眼睛,特别难受。到晚上环境光线不足的时候,感觉远处看不清楚。

然后,视力突然断崖式下降。三年时间,每年体检,从 1.2 直落 0.7 左右。而我在 35 岁之前一直是双眼 1.5 的视力。本来 2020 年就想约眼科医生看看的,因为疫情去看五官科不方便就一直拖着,直到 2021 年底才去看了医生。

初步诊断结果是结膜炎、干眼症、视疲劳。另外,验光结果表明我有 150 度近视加 50 度散光。因为并不影响日常生活,便没有配眼镜。而且,我的视力是时好时坏。从办公室眺望珠江对面的楼顶招牌时,有时那些字清晰可见,有时则是重影。我感觉如果以后能解决干眼症和结膜炎的话,视力能稳定一些。

在医院开的眼药水用完后,我便自己在网上网购一些进口的眼药水。尝试了好几种,最后觉得德国产的海露(Hylo Gel)最舒服,几乎不刺激眼睛;只要隔两个小时滴一次,便可以缓解视疲劳。所以就在家中和办公室各常备一瓶。

不过,结膜炎似乎今年更严重了。现在每天早上起来眼镜都充满血丝。而且视线略模糊。需要滴过眼药水,休息大约半小时才能恢复正常。前两个月又尝试了日本参天的一种据说消除红血丝的眼药水(金色包装的 Sante FX V+)。第一次用的时候有点不习惯。滴下去刺激感特别强烈,几乎睁不开眼,但闭眼几秒后感觉非常舒服。从镜子中看,血丝确实消退很快,视力状况也好了不少。

但是最近一次去医院,医生叮嘱说,参天这款主要是收缩血管,会让眼睛形成依赖性。如果以后结膜炎好转,但此眼药水还是会保持依赖,建议我不要再用了。


这两天因为驾照需要更新,体验要求视力在 0.9 (4.9) 以上。我的裸眼视力已经无法达到,便又挂了中山眼科的号,让医生看看病情,顺便重新验光配一副眼镜对付视力检查。

本来挂的 500 块的专家特需号,正巧碰上了疫情防控就取消了。推迟一天重新挂号,还是教授的号,但是只要 20 :) 运气不错。

这次的诊断依旧是干眼症和结膜炎。但这次医生多开了许多治疗结膜炎的药水。我给医生看了我一直在用的眼药水,便没有开同类的。同时,建议我买了一副湿房镜,平时在屏幕前工作时佩戴,缓解干眼症的问题。

有点意外的是,这次验光比去年的近视度数从 150 降到了 125 。按网上的说法,近视是不可逆转的,估计是去年验光不准确吧?验光师同时叮嘱我,只在需要看远处时才用佩戴眼镜,日常工作尽量不用。


另外,昨天有网友推荐我一款法国产的 Cationorm 人工泪液,他用过比 Hylo Gel 针对干眼症更好 。我在京东和淘宝上均未找到代购。有海外的朋友说帮我买两盒试试。