云风的 BLOG

前两天写了 快速字符串对象比较 ，我把这个想法提交到 Lua 的邮件列表，建议 Lua 的未来版本去掉长短字符串，不做 string interning ，用这个方法解决字符串比较的性能问题。Lua 的主要维护者 Reberbo 表示了兴趣，同时也提出了几点问题。

其中一个问题是，Lua 未必运行在 64bit 平台上，所以并没有直接使用 64bit 整数类型。而如果使用 32bit id 就无法简单的通过自增来保证 id 永远唯一。

我就这个问题考虑了几天，提了好几个解决方案，其中一个方案我最为满意，在这里重新用中文记录一下。

我们可以把 32bit id 分为两个区，0 到 0x7fffffff 为 old 区，0x80000000 到 0xffffffff 为 young 区。

一开始，id 从 0x80000000 开始分配，所有的新增字符串都属于 young 。

每次 GC ，在 sweep 阶段，把所有的 young id 重新分配到 old 区。这样，每轮只改变当轮新增的 id 。由于 gc 是分步进行的，sweep 过程也可能新增 id ，所以在 sweep 阶段开始时，让新增 id 直接放在 old 区，也就是说， sweep 阶段只会把 id 从 young 变成 old ，或直接增加 old ，不会产生新的 young id 。

sweep 结束后，再把新增 id 重新调回 0x80000000 。

在比较字符串时，如果字符串值相同，但 id 不同，把较大的 id 变成较小的那个。这样，如果两个 id 一个是 young 一个是 old ，young id 也会变成 old id 。

在这个算法下，old id 的自增速度就会大大的减慢。因为：一轮 gc 中，临时字符串会被回收掉，不占用 old id 的空间；比较过程很有可能把新增的 young id 变成 old id ，不会等到 sweep 阶段再分配新的 old id 。

如果 old id 快用完了，这种情况虽然罕见，但出现了还是有方法的。一个确保方案是用一个原子过程，遍历所有的字符串，把所有的 old id 重新排列到 young 区。因为 old 区全部空出来了，这样上面正常的 gc 流程又能正确工作了。

Posted by 云风 at 11:15 AM | Permalink | Comments (9)

这段时间在想办法解决多个 lua 虚拟机间共享对象的问题。这里的一个核心问题是，lua 的短字符串做了 interning ，虚拟机在比较两个字符串时只需要比较字符串对象指针即可。而多个 lua vm 如果想共享数据，必须解决这个问题。前段时间实现的 并发 Hash Map ，和 共享表 就是在这方面做的努力。

随着 lua 5.4 的临近，我最近尝试了在 lua 5.4 的 alpha 版上做类似的 patch 。但是 lua 5.4 对 gc 的修改极大，这让我尝试去找其它的办法来做这件事。

我觉得，如果允许 vm 在处理短字符串比较时，不严格遵守 interning 的约定，那么就不再需要对 gc 流程做改造了。这样，从外部共享来的字符串，只要做全量值比较，依然可以得到正确的结果。

这样的修改固然对 lua 的代码影响极小，但很可能会有很大的性能损失。毕竟，字符串比较从原来的 O(1) 一次指针比较，变成了复杂得多的 memcmp O(n) 。而这明显是 vm 的性能瓶颈所在。

我首先想的是把 lua 字符串对象 TString 从一个连续结构体改造成包含一个指针的间接引用。也就是说 TString 里不再直接包含字符串数据，而引用另一块数据块。如果首次比较两个 TString ，我们可以先比较内部的数据指针，不同的话再进一步比较数据内容。如果数据内容相同，就把两个内部指针合并成同一个。下次比较就可以通过比较指针完成。

但是，在多线程环境下，简单的引用计数却很难管理好这个内部数据块指针的生命期。我想了很久的无锁算法，感觉无解。可如果加锁，损失的性能或许更大，甚至大于直接比较短字符串的内存（毕竟最多才 40 字节）。

今天，我突然想到另一个巧妙地方法，非常值得一提。

我们可以给每个 TString 对象增加一个 64bit id 。一般情况下，这个 id 都是 0 。当我们需要把一个字符串共享出去时，则用简单的原子自增的方式分配一个唯一 id 给它。由于 id 有 64bit 所以不需要考虑 id 用完的情况。

当我们比较两个 TString 时，先比较 id 是否相同。如果 id 不同，再用 memcmp 做全量比较，如果最终结果相同，我们就把 id 较小的那个 TString 的 id 修改成较大的那个。

如果 id 相同，则可以认为两个 TString 的值相同，不需要进一步做 memcmp。

比如，在 A B 两个虚拟机中，都有字符串 "foo" ，它们都把自己共享出去。一开始 A 中的 foo id 为 1 ，B 中的 foo id 为 2 。

在 C 这个虚拟机中，一开始也有字符串 foo ，id 为 0 。当我们第一次将 C 本地的 foo 和 A 引入的 foo 比较后，C 的 foo 的 id 会修改为 1 。再次比较就不再需要 memcmp 。如果其后和 B 引入的 foo 比较，本地的 foo 的 id 会变成 2 ，再次遇到 A 的 foo ，则会把 A 的 id 也提升为 2 。

即使 A B 共享的 foo 在多线程下，被不同的虚拟机共享，也不需要加锁，因为 id 永远是向上提升，最终都会稳定下来。而且这个 id 仅仅是作为一个比较的参考而已。

通常这个方法，值相同的对象，在经过第一次比较后，以后的每次比较都可以通过一个 id 比较得到结果；值不同的对象，它们的 hash 值也几乎不可能相同，所以再后续的 hash 值比较中也能得到结果。

Posted by 云风 at 08:24 PM | Permalink | Comments (9)

其实我不是很在意代码的版式，比如到底用空格缩进还是 Tab ；花括号应该放在行末还是另起一行；以及，当需要用多个单词命名的时候，是用下划线分割还是驼峰。自己写的时候，自然有个习惯，但是项目中如果有多人参与，我也不在意大家各用各的。

毕竟是外在的东西，对代码结构没什么影响。甚至不太影响可读性。反而不同的风格容易区分出作者，阅读的时候更容易追溯到人，甚至比在 git 上看 blame 还方便一点。

前两天纠结这个命名法的问题，是因为在 bgfxidl 这个项目上，bgfx 的作者希望用 idl 描述并生成宏定义。我在设计对应的 idl 语法时涉及了到底采用下划线命名还是驼峰命名的选择。

因为 bgfx 的 idl 在之前的其它部分采用的是驼峰命名法，然后生成 C 接口的时候再转换为下划线命名。所以自然而然的，就想继续采用驼峰命名法。

但稍有不同的是，bgfx 目前的宏定义只有 C 风格的版本，也就是下划线命名的。只是计划在未来可以生成出一半采用驼峰命名法的 C++ 常量版本。在没有 idl 时，维护两个版本成本太高，故而只有 C 风格的宏一个版本。

所以，这次并没有两个版本的命名可以参照。

我在使用驼峰命名这一系列宏的时候，发现了驼峰命名法对于带数字的名称表示其实是有歧义的。可以说是一种缺陷，我之前自己的项目以 C 语言居多，一贯使用下划线命名法，没有意识到这点。这个问题有点意思，值得记录一下。

在下划线命名法里，单词间隔是非常明确的，用一个独立的字符分割。但是英文字母本来就区分大小写，似乎可以用大写字母来间隔单词，这样多单词连写在一起时更为紧凑，驼峰命名法看起来似乎更好看一些。

但是，有两种例外情况。

第一，是多个单词的首字母连起来的缩写，习惯上我们使用全大写表示。例如 RGB ，是 RedGreenBlue 的缩写，但是我们几乎不会用全称。那么 RGB 到底应该是一个单词还是三个单词呢？

即，如果把含有 RGB 的驼峰命名的词转换为下划线命名，到底应该是 r_g_b 还是保留为 rgb 或是 RGB 。我认为一定不会是 r_g_b ，因为它已经是缩写了，不应该再用下划线间隔开。至于用小写 rgb 还是大写 RGB 可以商榷。

所以，对于连在一起的大写字母，我倾向于它们是一个单词。

但是缩写 RGB 和下一个单词连写的时候就会造成麻烦。比如 RGBBitmap 怎么分词？这样就需要再加一条规则，小写字母串一定和它之前的一个大写字母是一个词。

当然，还有一种做法是把缩写词的后几个字母也小写，把 RGB 写作 Rgb 。这些也很明确，只是不太符合日常习惯。

第二，是数字怎么处理。数字没有大小写之分，所以不方便断词。不过通常数字也不会单独成词，例如 3d ，这明显是一个词。

一开始，我想把数字全部当作是大写字母，这样方便用正则表达式转换。比如 D3D12 就可以看成是全大写字母，很自然的把它分成一个词。只是数字不可以单独和后面的小写字母串放在一起成词。

但我发现了 Int32 这种词。其实我们在下划线命名中，习惯上是不会写作 int_32 的。也就是说 int32 其实是一个词而不是两个。我们无法依靠数字前面是小写字母还是大写字母来决定如何分词，比如 Create3d 这里的 3d 和 Create 就是要断开的。

最终，我在 bgfxidl 项目中采用了下划线和驼峰混用的表示方案。把数字全部看作小写字母，除非在数字前加上一个下划线，这样后面一个数字可以看作大写（用于分割一个单词）。

对于 idl 需要转换为驼峰命名时，我们简单的把 idl 的名称中下划线去掉即可；需要转换为下划线分割的时候，则按大写字母或下划线加数字来分割。

比如在 idl 中写 Texture_2d，转换为驼峰命名时为 Texture2D ，转换为下划线的宏则为 TEXTUTR_2D。

Format_8x1 的驼峰命名为 Format8x1 ，下划线版本为 FORMAT_8X1。

Uint10 的驼峰命名为 Uint10 ，下划线版本为 UINT10 。

Posted by 云风 at 11:07 AM | Permalink | Comments (10)