June 17, 2019

快速字符串对象比较

这段时间在想办法解决多个 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 的性能瓶颈所在。

阅读全文 "快速字符串对象比较" »

June 10, 2019

下划线命名和驼峰命名

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

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

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

阅读全文 "下划线命名和驼峰命名" »

May 18, 2019

为什么说执行 996 工作制的脑力劳动者非蠢即坏

抱歉我用了这么个吸引眼球的标题。但我其实是想分析一下 996 工作制度到底存在怎样的问题。注意,我说的是身体力行执行 996 工作制的人,而非要求员工进行 996 工作的老板,这是两类人,今天我想骂的是前一类。

如果让我给执行 996 工作制下个定义,我想不能把全身心投入到工作和事业上的工作方式等同。它并不指工作时长;而是指刻意的制度性的把工作安排在非正常工作时间段。对待工作,不是以是否完成计划内的工作为衡量标准;而是本末倒置的先预设工作时长,然后想办法填满这些工作时间。

对于我最熟悉的游戏软件行业,它的工作本应该是脑力劳动为主。尤其对于程序员来说,主要的工作应该是在你的脑子里通过思考完成的,如果你的工作效率受限于每天不停的敲打键盘、移动鼠标、那么就变成了一项体力劳动。不久的将来,猴子和 AI 都能替你把事情干了。体力劳动或许可以通过制度性的延长工作时间来加快进程,可硬生生的脑力劳动变成体力劳动,只能用蠢来解释了。

如果工作的重点是通过大脑思考完成的,那么就不在乎你在什么时间,坐在哪里进行这些思考。甚至入睡前的那段时间都能想很多,限制每天在办公室坐上 10 多小时没有任何意义。那为什么说起来简单,996 反而成了国内程序员工作的普遍状态呢?我以最大的善意揣测人性,若他们不是心眼坏的话,那只能是大多数从业程序员能力欠缺了。

从游戏行业看,投资做游戏的人最期盼的是什么?并不是压榨你用更短的时间把游戏做出来,而是你能给个明确的计划时间表,在这个时间内保证质量的完工。这个时间可以比较长,但只要计划是明确的,就能估算出未来的收支情况。成功的游戏利润率非常之高,如果游戏能成功,用暴力手段压缩制作时间而减少的成本简直无足轻重。所以,游戏产品上线前,一改再改,无限延长开发时间反而是常态。

健康的项目,计划的落实是第一位的。那么最影响计划安排的是什么?不是工作时长,而是开发中的不确定因素:

阅读全文 "为什么说执行 996 工作制的脑力劳动者非蠢即坏" »

May 16, 2019

通过对缓存测速提取信息的旁路攻击

最近爆出对 Intel 系 CPU 的新的安全漏洞。MDS 攻击 可绕过安全屏障,取得同一个核心上运行的其它进程(或其它虚拟机)处理的数据。安全界的建议是暂时关闭超线程,避免泄露信息。

我对这个安全漏洞颇感兴趣,花了一些时间研究,弄明白了来龙去脉。

其实,新的 MDS 攻击的思路继承至更早发现的 Meltdown 攻击方式。除了原始论文,我找到了 这篇 blog 把其原理介绍的非常清晰。

如果不介意我可能有理解偏差,那么可以看看下面我对其原理做的一点中文复述:

阅读全文 "通过对缓存测速提取信息的旁路攻击" »

May 11, 2019

Windows 下 UTF-16 的坑

最近帮多个活跃的开源项目改了同一个 bug : 完善 Windows 下的 Unicode 支持。

问题源于 Windows 和其它平台不同,它有悠久的历史包袱。和现代大多数操作系统对 Unicode 支持的共识不同,它的 API 不是基于 UTF-8 而是基于 UTF-16 的,且还遗留了一套过去对 ANSI 支持的兼容 API 。

最近我接触的几个活跃开源项目,都是西方人主导开发的,他们维护者似乎对 UTF-16 均有所误解,或是懒得做全面的支持。我认为罪魁祸首就是微软自己把 ANSI 编码称为 MBCS 多字符编码字符集,和 WideChar 宽字符集对应起来,暗示 WideChar 是单字编码。而事实上 UTF-16 方案应该成为 MWCS 才合理。

Unicode 虽然常用的只有 BMP ,也就是 U+0000 到 U+FFFF 部分的字符集。但是随着 Emoji 的普及,SMP 也变得非常常见了。其实 Unicode 目前的标准有 17 的 Plane ,需要 21bit 才能表示完全。而很多人直观的觉得,UTF-16 每一个字 ( 2 字节 )表示一个码点。这是不对的,像 Emoji ,一些罕见汉字(SIP)需要用两个字来表示。这个叫做 surrogate pair ,对于 Unicode ,U+D800 到 U+DFFF 这个区段是不存在的,专门用于实现 UTF-16 中的 surrogate pair 。

阅读全文 "Windows 下 UTF-16 的坑" »

April 14, 2019

并发 Hash Map 的实现

Lua 中的短字符串做了 string interning 的处理,即在同一个虚拟机内,值相同的字符串只存在一份。这可以极大的提高用字符串做 key 的 hash 表的查询速度。因为字符串比较的时间复杂度从 O(n) 下降到 O(1) ,比较查询的 key 和 hash 表内的 key 是否一致,只需要对比一下对象的指针是否相同即可。

我在解决多 Lua 虚拟机共享字符串对象这个问题时,合并了不同的 Lua 虚拟机中的短字符串表。让同一进程所有虚拟机共享一个短字符串表( SSM )。

我最初在实现 SSM 的时候,考虑到多虚拟机 GC 的复杂性,采用了只增不减的方案。即让部分短字符串进入 SSM ,设置一个上限,避免 SSM 无线膨胀。但 Lua 并没有把经过 interning 处理的字符串作为独立类型,目前只用字符串长度作为区分,也就是无法和不 interning 的短字符串共存。所以,那些已存在本地虚拟机短字符串表中的字符串,就不从 SSM 中获取对象。

修改过 Lua 的 string interning 算法是这样的:

  1. 查看字符串是否存在于本地字符串表 (LSM) 如果存在,就立刻返回。这一步和原版 Lua 一致。

  2. 查看字符串是否存在于 SSM ,如果存在,就返回。

  3. 检查是否 SSM 上限已到,如果不能再增加新字符串,把字符串添加到 LSM ,返回。

  4. 将字符串添加到 SSM ,返回。

阅读全文 "并发 Hash Map 的实现" »

April 11, 2019

不同虚拟机间共享不变的 Table

这几年,我一直在寻找不同 Lua 虚拟机间共享大量不变的结构化数据的方法。因为这对于游戏这类数据驱动的软件是非常重要的需求。我们现在正在运营的游戏“风之大陆”,服务器上的策划生产出来的数据表格,转换为 Lua 源文件后,就已经达到了 300M 之巨,全部加载到 Lua 虚拟机中,会消耗 700M 内存。

我为这个需求实现过好几套方案:最初是 Sharedata 这个模块,后来又实现了一个叫 DataSheet 的替代品。

过去的方案用的思路都是把数据表放在 C 对象中 。Lua 中建立一个 proxy 对象去访问它。C 对象可以跨虚拟机共享,proxy 对象则在不同的虚拟机中各创建一份。

阅读全文 "不同虚拟机间共享不变的 Table" »

Misc

Categories

Archives

Recent Comments