« January 2017 | Main | March 2017 »

February 21, 2017

绕过 c api 直接访问 lua 表

今天试了一下一个想法:绕过 lua 提供的 C API 直接去访问 lua 的表结构,提供在性能及其重要的环境高效访问数据结构的方法。

例如:我们需要在 lua 和 C 中共享一个 vector 3 结构,有两种实现方法:一、把 C struct 实现为 lua 中的 userdata ,然后给 userdata 加上 metatable 以供 lua 中访问内部数据;二、在 lua 中使用一个 table 实现这个 vector3 结构,类似 { x = 0.0 , y = 0.0, z = 0.0 } 这样;然后在 C 里通过 c api (lua_rawget/lua_gettable/lua_getfield) 来访问里面的数据。

前一种方法会导致在 Lua 中访问成本加大、而后一种方法增加的是 C 中访问数据的成本。如果我们只在少数性能敏感的地方通过 C 去操作数据结构,那么第二种方法看起来更简单灵活一些。这样,不需要 C 介入的地方,是没有额外开销的。毕竟、通过 metamethod 索引 userdata 的成本比直接索引一个普通的 table 要重的多。

但是、第二种方法会导致 C 访问数据的成本较大。我们采用 C 代码去处理 vector 数据结构,一定是考虑到性能热点,在语言边界上损失性能感觉不太划算。我觉得或许可以采取一个技巧来加快它。

对于标准的 Lua 实现,构造好的 hash 表,在不添加新 key 的前提下,读写已有的 key ,value 所在的 slot 是不变的。如果我们能记住 slot 的位置,那么就可以绕过 hash 过程、也不需要把 key (这里是一个 string)压栈,直接读写值了。

而且,对于同一个 lua_State 从一个空表开始,按一致的次序写入相同的 key ,内部数据结构也一定相同。我们可以利用这一点,为同类结构一次性生成索引表。

我写了一小段代码验证我的想法,感觉是可行的:https://gist.github.com/cloudwu/09fca725cb9177d809790b6a7ecdac20

你可以先创建一个 4 个 slot 的 hash 表,key 分别是 x y z __vector 。这第 4 个 key __vector 是一个标记,表示这是个规整过的数据结构,x y z 都是浮点数,且一定在固定的 slot 里。

void vector_init(lua_State *L, struct vector_offset *vo) 可以用来生成 slot 号的结构 struct vector_offset 。每个 lua_State 只用生成一次,然后就可以永久保存在 C 的数据结构中。

然后我们用 vector_get 可以获得内部数据结构 Table * ,这个结构定义在 lobject.h 中,是一个内部 h 文件,这里可以借用一下。之后,就可以用宏 X Y Z 去访问这个 Table * 了。

vector_get 中,会检查指定的 table 是否是规整化的 vector 结构,如果不是,就把 x y z 三项读出来,清空 table ,再写回去,并填上 __vector 标记。此处检查 __vector 标记是个很轻量的操作。


这个方案适用于 Lua 5.3 ,我没有在老版本的 Lua 上试过,但想必也是可以用的。它的好处是不需要修改任何 Lua 的实现代码、只需要引入 Lua 本身的内部 h 文件即可。所以利用这组 api 实现的 lua 库是可以和其它库兼容共存的。

February 17, 2017

为什么 Windows 的文件系统会有盘符,使用反斜杠分割路径

今天同事在公司群里贴了张屏幕截图,上面有30+ 个盘。从 C: 排到 Z: , 然后还有 CC: CD: ,调侃问 Windows 能管理多少个盘。

图应该是 P 出来搞笑的,除去 A B 盘保留给已经淘汰的软驱用外,windows 超过 Z 盘后就不在能增加了。如果有更多储存设备,则需要用把设备挂接在空目录上(ntfs 支持)。

为什么 Windows 会有盘符这个诡异的东西呢?

按如非必要、勿增实体的原则,只用路径就够了呀。物理分区完全可以隐藏在文件系统之后,在 Unix 系的操作系统中,分区是用挂接点的方式挂接在虚拟文件系统中的(ntfs 其实也支持)。如果是为了方便记忆和保持用户习惯,完全可以把分区顺着挂接到 /c /d /e /f 下。如果你在 windows 下安装 mingw/msys 它就是这样处理 C 盘、D 盘 …… 的。

答案要从历史中找。

Windows 的前身是 微软的 Dos 系统。我见过的最古老的 MS Dos 是在我同学家的一台旧 IBM PC/XT 上。10M 的硬盘、只有 256K 内存,配置的系统是 PC(MS) Dos 2.0 。

知道这个 2.0 版的 Dos 比它的前身最大的改进是什么吗?它比 MS DOS 1.0 多支持了硬盘,以及层级目录结构。

同时期的主流电脑是 Apple ][ ,它的原生操作系统(Apple Dos)是不支持硬盘的,软盘上只有一个根目录。MS Dos 1.0 也一样。

除了 IBM PC,Apple ][ ,那个年代个人电脑品牌其实非常多。比如我的第一台电脑就是港产的 Z80 机器(laser 310 )。当时 8 位机上最流行的个人操作系统是一个叫做 CP/M 的系统。不过当时流行直接用汇编写程序,这个 CP/M 必须跑在 Z80(8080) 的指令集上。当年 Apple ][ 上流行过一种叫做 Z80 卡的扩展件,就是为了可以跑 CP/M 系统。

微软起家为 IBM 的 8086 系列 PC 写操作系统时,就借鉴了 CP/M 的一些东西,其中就有盘符这个东西。在没有硬盘,及内存小于软盘容量的年代,配置两个软盘驱动器是最方便的,所以就有了 A B 两个盘符(方便数据对拷)。每个文件都可以写成 A:FILENAME.EXT 的形式。这就是盘符的由来。

btw, 早年 IBM 想和 CP/M 合作没谈成,后来 PC 流行后,CP/M 又反回来兼容了 MS-DOS 跑在 PC 系统上,改名字叫 DR-DOS ,应该很多同学有印象。

MS DOS 发展到 2.0 时,由于 IBM 给 PC/XT 增加了 10M 的硬盘,所以盘符就被扩展到了 C: 表示硬盘。储存空间的增加导致了必须增加文件目录结构。可为啥微软选择了反斜杠,而不是 Unix 系列中已经很广泛的 / 呢?

这是因为,MS Dos 已有的很多命令行工具。当时微软做开发的人有 DEC 的背景,DEC 的操作系统上是用 / 做命令行参数分割符,而不是 Unix 系列用的 - ,就这样沿用到了 MS Dos 里。btw, 我读大学时第一次接触 Linux ,感觉输入最不习惯的就是用 - 而不是 / 。

为了防止混淆,目录风格符就不能再使用 / 了,DEC 系统中用的是点 "." ,可 MS Dos 学了 CP/M 用 . 做文件后缀名分割,所以就用了让后代程序员深恶痛绝的反斜杠 \ 。

ps. C 系列的语言中,\ 是字符串转义符,写在字符串里你需要写 \\ ,特别麻烦。


今天发现本 Blog 用的虚拟主机 linode 降价了,现在只要 5$ 一个月。去后台调一下即可。Linode 用 7年了,感觉非常好。

如果有同学也有兴趣租一个境外的 vps ,可以点这个链接 ,或者填我的 referral code : 538bab39bc1265a2ce54115d1f86e2bc81e4d133 。

February 14, 2017

跟踪数据结构的变更

这两个月,我的主要工作是跟进公司内一个 MMORPG 项目,做一些代码审查提出改进意见的工作。

在数月前,项目经理反应程序不太稳定,经常出一些错误,虽然马上就可以改好,但是随着开发工作推进,不断有新的 bug 产生。我在浏览了客户端的代码后,希望修改一下客户端的 UI 框架以及消息分发机制等,期望可以减少以后的 bug 出生概率。由于开发工作不可能停下来重构,所以这相当于给飞行中的飞机换引擎,做起来需要非常小心,逐步迭代。

工作做了不少,其中一个小东西我觉得值得拿出来写写。

我希望 UI 部分可以严格遵守 MVC 模式来实现。其实道理都明白,但实际操作的时候,大部分人又会把这块东西实现得不伦不类。撇开各种条条框框,纸上谈兵的各种模式,例如 MVC MVP MVVM 这些玩意,我认为核心问题不在于 M 和 V 大家分不清楚,而是 M 和 V 产生联系的时候,到底应该怎么办。联系它们的是 C 还是 P 或是 VM 都只为解决一个问题:把 M 和 V 解耦。

我们的底层使用的是 Unity3D 及它的 UGUI ,UGUI 提供了 UI 需要的显示控件对象,我们开发的业务逻辑则是围绕这些对象开发的。

由于在移动设备上内存有限,项目又做了一系列的对象管理工作,UI 控件并不一定常驻内存,会根据需要加载或删除。又由于这是一个网络游戏,UI 操作和反馈经常需要和服务器打交道,又许多异步操作。故而有一段时间频发的 bug 来自于异步操作访问了被删除的控件对象。

我认为其根本原因在于 M 和 V 没有很好的解耦。

对于 UGUI 引擎提供的控件,应该完全封装在 View 中;而业务数据则应该全部放在和这些控件无关的数据结构即 Model 中。而 Model 改变引起的 View 更新逻辑,如果即不存在于 Model 的方法中,也独立于 View 之外的话,那么这类 Bug 应当是不会产生的。


在迭代的代码中,我们要求 Model 必须是一个纯粹的数据结构,也不一定和显示(View)结构一一对应。比如玩家的 HP 在 Model 中只是一个字段,但可能反应在 View 里的多处地方;而 View 里某个呈现的状态也可以是 Model 中多个字段的复合结果。

业务代码应该可以任意修改 Model ,不必关心 View 是否有效,理论上及时界面控件全部不存在,甚至是一个文本界面,代码也应该可以正常工作。修改 Model 的行为不需要立刻去更新 View ,即修改 M 和更新 V 不需要也不应该是一个同步行为。它们在框架中是两个明确独立的执行阶段,执行流程会清晰的多。

这就类似网页前端,你的业务部分可以提交完整的网页 DOM ,然后浏览器更新 DOM 呈现成图像。当然,如果 UI 结构很复杂的话,每帧次都提交全新的完整 DOM 效率很低,如果可以筛选出每次的差异,根据差异来更新控件,效率就高的多了。


去年底,我写了这么一个 lua 模块:https://github.com/cloudwu/tracedoc

它可以构造一张 lua 表对象,并跟踪对这张表的所有修改。调用 commit 方法可以比较和上次 commit 的版本间的差异,并生成差异集。

这个差异是指的最终叶节点的值差异,比如如果原来的表里有一个字段是 a.x = { 1, 2} ;如果你重新写 a.x = {1, 2} 对 a.x 重新赋值,因为新的值还是 { 1, 2} ,模块会认为没有变化。

在表里只可以存放 lua 原生数据类型:数字、字符串、布尔量。表内可以用 table 创建子结构,但子表的 key 只能是数字或字符串。表里也可以存放对象的引用,但必须用 table + metatable 的形式。所有带 metatable 的 table 都被识别为对象,不会递归比较内部细节。

为了方便 UI 框架的使用,还允许使用者定义一组映射函数,当变更集变更的时候,调用变更数据节点在表内的路径串对应的预定义函数。

这样,方便使用者实现对应的数据绑定特性。


除了在 UI 框架中的应用,这个模块还可以用于 skynet 服务器服务间的数据同步。

比如,我们可以为每个玩家创建一个 agent 服务管理玩家的数据,但多个玩家在一个场景中战斗时,场景服务也需要读写每个玩家的部分数据。

即使对数据做精心的划分:分为玩家私有数据(例如背包)和玩家交互数据(例如玩家的战斗 buf ,属性等),把它们分开存放在 agent 和场景服务中。依然也有一定的需求两类数据间发生交互。

如果我们在设计上能保证一组数据是存在一个写入者,其它服务都是读取者,我们可以把数据放在拥有写入权的地方,而其它地方都是这份数据的副本。

数据体和数据副本间的同步就可以利用上面这个模块。

在分布式系统中,不存在完全的状态同步,但共享状态需要保证版本的原子性,也就是说如果你的一次数据修改若涉及多个字段,那么需要保证读取方每次都读到这组数据不同字段的同一个版本,而不能是 a 是上个版本, b 是下个版本。

如果采用这个模块,我们可以定期对数据表做 commit ,生成差异集发送到副本所在的服务,让它每次都原子性的 patch 差异集。这样持有副本方就一定能保证读到的是一个完整的版本了。至于版本落后数据源一小段时间,则是在设计范畴内的了。