Main

February 03, 2016

ejoy2d sprite pack 的空间优化

在 ejoy2d 里,我将 sprite 的结构信息储存在一组叫 sprite pack 的结构中。其中包括动画的 frame 数据,sprite 由若干部分组成,每个部分的变换矩阵,对应贴图的编码和坐标等等。

通常这些数据不会太大,所以我建议一次加载到内存就不再删除。而动态生成的 sprite 对象则直接引用这些数据,不必做引用计数。这些数据之间的交叉引用(可以像搭积木一样用很多部件构成复杂的 sprite )也不需要额外记录。但如果保存了大量的动画信息,或 sprite 是由非常多的小部件构成,数据量也可能非常可观。

在我们的 心动庄园 里,达到了数十 M 内存之多。前几天同事提到这个问题,我便动手做了一点简单的优化,居然省出了几十兆内存。

January 08, 2015

如何拼接 PVR 压缩贴图

2d 游戏通常都用到很多图素,由于显卡硬件特性,我们又不会把单个图素放在独立贴图中。这样会导致渲染批次过多。在移动设备上,非常影响渲染效率。

所以,游戏运行时,这些图素一般都会合并在很少几张贴图上。要么采用离线合并的方式(利用 texture packer 这样的工具),或者在运行时使用装箱算法。

最近,朱光同学一直在为 ejoy2d 编写运行时合并图素的模块。今天我们讨论了一下他做的诸多尝试。

September 03, 2013

字体勾边渲染的简单方法

我们的游戏中需要对渲染字体做勾边处理,有种简单的方法是将字体多画几遍,向各个方向偏移一两个像素用黑色各画一遍,然后再用需要的颜色画一遍覆盖上去。这个方法的缺点是一个字就要画多次,影响渲染效率。

前几年有人发明了另一种方法,google 一下 Signed Distance Field Font Rendering 就可以找到大量的资料。大体原理是把字体数据预处理一遍,把每个像素离笔画的距离用灰度的形式记录在贴图上,然后写一个专门的 shader 来渲染字体。好处是字体可以缩放而不产生锯齿,也比较容易缺点边界做勾边处理。缺点是字模数据需要离线预处理。

我们的手游项目以及 3d 端游项目都大量使用了勾边字体,我希望直接利用系统字体而不用离线预处理字体把字体文件打包到客户端中。前段时间还专门实现了一个动态字体的贴图管理模块 。btw, 苹果的平台提供了高层 API 可以直接生成带勾边效果的字模。

但是,勾过边的字模信息中同时包含了轮廓信息和字模主体信息,看起来似乎很难用单通道记录整个字模数据了。这给染色也带来了麻烦。

August 26, 2013

去掉 full userdata 的 GC 元方法

根据 Lua 文档中的说法,lightuserdata 比 fulluserdata 要廉价一些。那么,其中的区别在哪里呢?

空间开销上,fulluserdata 是一个 GC 对象,所以比 lightuserdata 要多消耗一点内存,这点内存往往对程序不造成太大的影响。

时间开销上,fulluserdata 在访问它时和 lightuserdata 并无太大区别,它们都只能通过元方法才能在 Lua 中使用。所有 lightuserdata 共用一个元表,不如 fulluserdata 灵活,在元表访问效率上却是几乎相同的。对程序性能有影响的部分在于它们对 GC 环节的开销不同。

fulluserdata 本身是一个 GC 对象,所以在扫描的时候要复杂一些。它可能有附带的 uservalue 需要扫描,但不设置 uservalue 几乎就没有额外的扫描开销了。当 fulluserdata 有 gc 元方法后,就给 GC 流程增加了额外的负担。GC 模块需要额外记录一个链表来串接起所有有 gc 元方法的对象,推迟到 gc 的最后环节依次调用。

对于对延迟相当敏感的游戏程序来说,最容易造成运行过程中瞬间延迟增加,却又很难控制的部分就是 GC 了。所以我们在开发中经常需要关注怎样合理的使用 Lua 避免 GC 的负担过大。

March 11, 2013

最近一些心得

最近特别忙, 每天写程序的时间都不够。有些东西在做完之前不想公开谈,所以只把一些笔记发在公司内部的周报里了。等这段时间过去,再贴到这里来。

不过还是有一些泛泛的心得可以写写的。

前几天遇到一个优化的问题。我想采用定期计算路图的方式优化寻路的算法。而不用每次每个单位在想查找目标的时候都去做一次运算并记录下路径结果。一切都看起来很顺利,算法的正确性很快就被验证了。可是最后实际跑的时候,发现在生成路图的地方会稍微卡一下影响流畅性。

November 09, 2012

Lua 字节码与字符串的共享

我们的系统的应用场合比较特殊,在同一个进程内存在数千个 lua_State

Lua 的虚拟机占用的内存已经足够小了,但还是抗不住数量多啊。所以我希望有版本节约一些内存。

最想做的一件事情是把不同 lua_State 中相同的函数字节码合并起来共用一块内存。要做到这一点并不复杂。而且可以提高一些内存访问的效率。(因为大部分 lua 程序在并行执行相同的逻辑)

首先我们需要准备一个用来共享数据块的模块,它必须是线程安全的。因为既然分到了不同的 lua_State 就是想利用并发的优势。针对这个特定需求定制这样一个模块可以做到 lock-free 。

June 20, 2012

开发笔记(21) : 无锁消息队列

最近三周按计划在做第一里程碑的发布工作,几乎所有新特性都冻结了。大家都在改 bug 和完善细节。

服务器的性能还有不小的问题,压力测试的结果不能满意。原本我希望可以轻松实现 40 人对 40 人的战场。现在看起来在目前台式机上还有困难,虽然换上高配置的服务器可以达到,但会增加不少成本。我们决定动手做一些优化。

固然过早优化的必要性不大,但早期发现的性能问题有可能是设计原因造成的。尽早发现设计中的错误,早点改正,比后期在低层次优化要省力的多。

我们采用的是大量进程(非 OS 进程,这里指 Erlang 进程)协作工作的模式。可以充分利用多核的优势,但却对内部通讯的数据交换产生的极大的压力。初步发现在多人对战时,90% 的内部通讯包是状态包的同步 。虽然我们的框架实现,会让单台机器上的 Erlang 进程间通讯,变成同一进程内的简单函数参数传递。但数据列集和内存复制还是会带来一些负荷。

目前还不太确定内部数据包传递的边际成本到底是否影响到整体性能,我打算从优化这一部分的设计和实现入手,确定问题所在。

状态同步,简单说就是一个玩家的 Agent 在做一个动作时,它需要把这个行为通知所有在虚拟场景中他附近的玩家。当很多人(超过 50 人)在一起时,就有大量的数据包需要广播出去。我们目前的做法是基于这样一个假设:服务器内部数据包的传递非常廉价。广播包比逐个发送更加廉价,这是因为,单机内部广播,可以避免大量的数据复制。所以,在同一张地图上,我们会简单的把任意一个 Agent 的状态改变信息广播给同张地图的所有其他人。这样就不需要动态维护分组信息。当每个 Agent 收到广播包后,再根据自身的逻辑进行过滤,再发给对应的客户端。

或许我们需要一个更为高效的广播方案,避免一些无谓的包复制。

我想实现这样一个数据结构:

February 02, 2012

Ring Buffer 的应用

这是一篇命题作文,源于今天在微薄上的一系列讨(好吧,也可以说是吵架)。其实方案没有太多好坏,就看你信不信这样做能好一些或坏一些。那么,整理成 blog 写出,也就是供大家开拓思路了。

我理解的需求来源于网络服务提供程序的一个普遍场景:一个服务器程序可能会收到多个客户端的网络数据流,在每个数据流上实际上有多个独立的数据包,只有一个数据包接收完整了才能做进一步的处理。如果在一个网络连接上数据包并不完整,就需要暂时缓存住尚未接收完的数据包。

问题是:如何管理这些缓冲区比较简洁明了,且性能高效。

其实这个有许多解决方案,比如为每个网络连接开一个单独的固定长度的 buffer 。或是用 memory pool 等改善内存使用率以及动态内存分配释放,等等。今天在微薄上吵架也正是在于这些方案细节上,到底好与不好,性能到底如何。既然单开一篇 blog 了,我不像再谈任何有争议的细节,仅仅说说,用 Ring Buffer 如何解决这个问题。

December 14, 2011

pbc 库的 lua binding

前几天写的 pbc 初衷就是想可以方便的 binding 到动态语言中去用的。所以今天花了整整一天自己写了个简单的 lua binding 库,就是很自然的工作了。

写完了之后,我很好奇性能怎样,就写了一个非常简单的测试程序测了一下。当然这个测试不说明很多问题,因为测试用的数据实在是太简单了,等明天有空再弄个复杂点的来跑一下吧。我很奇怪,为什么 google 官方的 C++ 版性能这么差。

我的 lua 测试代码大约是这样的:

local protobuf = require "protobuf"

addr = io.open("../../build/addressbook.pb","rb")
buffer = addr:read "*a"
addr:close()
protobuf.register(buffer)

for i=1,1000000 do
    local person = {
        name = "Alice",
        id = 123,
    }
    local buffer = protobuf.encode("tutorial.Person", person)
    local t = protobuf.decode("tutorial.Person", buffer)
end

100 万次的编码和解码在我目前的机器上,耗时 3.8s 。

December 07, 2011

开发笔记 (5) : 场景服务及避免读写锁

这周我开始做场景模块。因为所有 PC 在 server 端采用独立的 agent 的方式工作。他们分离开,就需要有一个模块来沟通他们。在一期目标中,就是一个简单的场景服务。用来同步每个 agent 看到的世界。

这部分问题,前不久思考过 。需求归纳如下:

  1. 每个 agent 可以了解场景中发生的变化。
  2. 当 agent 进入场景时,需要获取整个世界的状态。
  3. agent 进入场景时,需要可以查询到它离开时自己的状态。关于角色在场景中的位置信息由场景服务维护这一点,在 开发笔记1 中提到过。

大批量的数据同步对性能需求比较高。因为在 N 个角色场景中,同步量是 N*N 的。虽说,先设计接口,实现的优化在第二步。但是接口设计又决定了实现可以怎样优化,所以需要比较谨慎。

比如,同步接口和异步接口就是不同的。

请求回应模式最直观的方式就是设计成异步接口,柔韧性更好。适合分离,但性能不易优化。流程上也比较难使用。(使用问题可以通过 coroutine 技术来改善 )即使强制各个进程(不一定是 os 意义上的进程)在同一个 CPU 上跑,绕开网络层,也很难避免过多的数据复制。虽有一些 zero-copy 的优化方案,但很难跨越语言边界。

May 11, 2011

闲扯几句 GC 的话题

今天跟同事闲扯的时候谈到 GAE SDK 刚刚支持了 Go 语言。这对于 Go 语言爱好者来说是个让人欢心鼓舞的消息。几乎所有人都相信它能比 Python 的执行效率高一些。从开发效率上来说,不会比 Python 差,那么 Go 语言的支持可能是比 Java 更好的选择(开发效率和执行性能的均衡)?

这也让我想到了前段在北京时跟 Douban 的同学聊 Go 的事情。那天,有同学问起 GC 的事,是个 C++ 程序员。C++ 程序员对 GC 知之甚少是可以理解的。我大约花了 10 分钟介绍简单的 GC 算法(:根扫描清理、三色标记、移动或不移动内存等等。那段时间我正在研究 lua 的 gc 实现,刚巧看了不少文章。

June 13, 2010

把 vfs 实现好了

极尽简洁,然过犹不及(As simple as possible, but not simpler.)——爱因斯坦

这段时间的工作是把上次提到的 VFS 系统实现了。而写这篇 Blog 的促因是 twitter 上有同学想让我谈谈对 Linus 最近的一篇老生常谈的看法。哦,看似既然是语言之争。C 好,还是 C++ 好。但这次他平和了许多。Linus 惯有风格依旧,但少了些须三年前的争论 中的刻薄。

我想说,C 的三个特质(见引用文最后一段) 哪一点都不可忽略。Linus 这次强调的大约是第三点,也是 C++ 程序员们不屑一顾的一点。可对于多人协作构建的项目,这一点实在是太重要了。这并不是人人都聪明就能回避的问题。如果程序员们都足够睿智,反而更能意识到沟通之成本。其实即使是你一个人在做整个项目,从前的你和现在的你以及将来的你,同样有沟通(记忆)的成本。人不可能两次踏进同一条河流。

December 23, 2008

一种对汉字更环保的 Unicode 编码方案

Windows 早期默认支持的中文编码方案是 GBK ,它是对早期 GB2312 的一个扩展。后来国家又发布了 GB18030 标准,扩展了 GBK ,增加了一些 Unicode 里才有的汉字,这样就可以做到和 Unicode 字符集做完全的映射了。

而后来 Unicode 逐渐成为标准,几乎所有的系统处理多国语言时,都把 Unicode 做为默认设置了。Unicode 有两套编码集,UCS-2 和 UCS-4 ,后者是对前者的补充,虽说字面说写的 4,但实际上只用到了 3 个字节不到。

Windows 的内部其实是用的 UCS-2 标准,并用 UTF-16 来实现。而非 Windows 系统大多采用了 UTF-8 。UTF-8 在很多情况下更有优势,首先它不需要考虑大头小头的问题,其次,数据损坏的时候,不会有半个汉字的问题。并且 UTF-8 可以完整的表达 UCS-4 而不需要有额外的付出。

前几年,处于 Windows 程序员转型期,经过一些痛苦的实践,我终于意识到,VC 提倡的所谓为软件维护 UNICODE 和 非 UNICODE 两个版本是件巨傻 X 的事情。之后,我们的程序再也不为内码分版本了,一律采用 UTF-8

不过,UTF-8 的设计明显是用英文为主的西方人搞出来的东西。对于中文一点都不环保。所有汉字和中文标点都需要 3 个字节才能表达。而少量欧洲字母可以用 2 字节表达,英文的 ASCII 符号则可以只用单字节。

我不指责这个设计,因为兼容 ASCII 是 UTF-8 的最大优势。其它,则是 KISS 原则下的产物。

不过,若是内部使用的话,如果你介意这 1/3 的储存空间的浪费的话,是不是有改进的余地呢?下面我们来讨论这个问题。

September 05, 2008

高度图压缩后的边界处理

几年前我曾经写过一篇 blog 介绍我发明的一种高度图压缩算法 。最近几天,我将这个算法用于目前正在开发的 engine ,如之前所料,效果不错。由于数据被压缩,更改善了资源加载的速度。并在同等内存条件下,让用户得到更高的体验。(这是因为,现代操作系统,都会把暂时不用的物理内存全部用于磁盘缓存,更小的文件体积同时意味着在同等内存条件下能缓存更多的数据)

因为我们需要做动态地形数据的加载,所以地形高度数据也被切割成了一小块一小块。采用这个算法后带来的一个问题是:由于压缩有数据损失,两个相临块之间不能严丝合缝的衔接在一起。

为了解决这个问题,这两天想了好几个方法。

August 24, 2008

_alloca 函数的实现

C 语言里有一个 alloca 函数,可以在堆栈上分配一块内存,当前函数退出时,由于系统堆栈指针的调整,这块内存会被自动回收。

alloca 的函数原型是

void *
alloca(size_t size);

今天,在各种编程文档中已经不太提倡使用了。因为它有许多不安全因素。这里暂且不讨论。

另外,在 CRT 库里,通常还会提供一个 _alloca 函数,供编译器内部生成代码使用。比如在 C99 标准中,允许程序员在堆栈上开启变长数组,gcc 其实就是通过 _alloca 分配的内存来实现这个特性的。

另外,当你分配为局部变量数组申请空间过大时,gcc 也会调用 _alloca 。(大概是因为 crt 在实现 alloca 时,附带增加了一定的检测功能,测试堆栈溢出)

June 10, 2008

用 C 实现一个变长数组

我想用 C++ 的人都用过 std::vector 。它是一个可变长的数组,在很多时候都比 C 固有的定长数组要灵活。

C 里没有这样的标准化设施,但是写软件的人通常都会实现一个。正所谓,不厌其烦的重造轮子 :D 。这里我们不讨论造轮子的好坏问题,直接讨论下实现这么个东西的一点小技巧吧。总是固执于用谁做的轮子的问题,眼光就太短浅了。

一般的 vector 的实现,需要记录三个数据:数据空间的地址,空间大小,数组里已存在的元素个数。也可能是这三个元素的变体。比如在 msvc 的 stl 实现中,vector 保存的是三个 iterator:数组头指针、最后一个元素的指针、分配出来的全部空间的末尾指针。

December 05, 2007

多核环境下的内存屏障指令

本来不打算立刻写关于这次 软件开发大会 的事情。太多可以写的东西,反而不知道怎么写起。今天才有机会上网到处转转,转到 周伟民老师 的 blog 上,看到这么一篇 。里面既然提到我,就想在上面回上两句。可惜 csdn 的 blog 系统实在是太烂了(这个话题我们在周六的沙龙上集体声讨过,暂且按下不表),硬是没发上留言。那么我还是在自己的地盘单独提出来说说吧。


周老师那个 session 正好排在我的前面。同一间会议室,而且内容我也颇有兴趣。也就顺理成章的听了。讲的东西其实满不错的,唯一的抱怨是太像在大学里授课,互动少了点。会场气氛远不如后来 Andrei 讲 Lock-Free Data Structures 那么精彩。

周老师讲的这块内容,正巧我前几年写多线程安全的内存分配器时碰到过,有点研究。加上前几年对 Intel 的东西颇有兴趣,便有了发言的冲动 :) 。当时的会场上下文环境正好是有个朋友提问说:实际上,InterlockedIncrement 的调用是多余的。(事后交换名片得知,提问的这个哥们是来至 google 的程序员)

July 01, 2007

更健壮的 C++ 对象生命期管理

以下的这个 C++ 技巧是前段时间一个同事介绍给我的,而他是从 fmod 中看来。当时听过后没怎么在意,主要是因为这两年对 C++ 的奇技淫巧兴趣不大了。今天跟另一同事讨论一些设计问题时,突然觉得似乎在某些地方还有点用途,就向人介绍了一番。讲完了后觉得其实还是有点意思,不妨写在 blog 上。

问题的由来是这样的:音频播放的模块中比较难处理的一个问题是,波形(wave sample)数据对象的生命期管理问题。因为你拿到一个对象后,很可能只对它做一个播放(play)的操作,然后就不会再理会它了。但是这个对象又不能立刻被释放掉。因为声卡还在处理这些数据呢。我们往往希望在声音停止后,自动销毁掉这个对象。

另一些时候,我们还需要对正在播放的声音做更细致的控制。尤其在实现 3d 音效,或是做类似多普勒效应的声音效果的时候。

C++ 中传统的方法是用智能指针的方式来管理声音对象,但这依赖语言本身的一些特性。fmod 提供了诸多语言的接口,它在为 C++ 提供接口的时候利用了一个更为巧妙的方法。

May 02, 2007

实现一个 timer

前段时间写过一篇 blog 谈到 用 timer 驱动游戏 的一个想法。当 timer 被大量使用之后,似乎自己实现一个 timer 比用系统提供的要放心一些。最近在重构以前的代码,顺便也重新实现了一下 timer 模块。

这次出于谨慎,查了一些资料,无意中搜到这样一篇文章:Linux内核的时钟中断机制 。真是一个不错的设计啊 :D 和我的 timer 实现的思路是一致的,但是在细节上要优秀。

January 16, 2007

让 win32 程序也可以从 console 输出信息

今天同事在调试一个 win32 程序的时候,希望从 console 输出一些调试信息。他威胁说,否则,就要动用邪恶的 MessageBox 了。

我们以前的库倒是提供了一个 console 模块,可以从 win32 程序中创建出一个 console 。然后把标准输入输出定向到上面。这并不麻烦,就算不用翻出以前的代码重用一下,查下 MSDN 自己写上几句也可以解决。

今天突然想到,其实还有一个更 kiss 的解决方法。那就是直接开一个 console ,再在上面执行需要调试的程序。只不过直接运行是不会得到任何输出的,需要多做一步的是使用管道操作。

例如,需要调试的程序是 test ,那么只需要写 test | more 就可以把 test 的标准输出导向 more ,那么 more 就能捕获所有 test 的标准输出并显示在控制台上了。

March 20, 2006

type redefinition 的解决方法

我们的 engine 中定义了一个自己的类型叫做 boolean ,是这样定义的: typedef unsigned long int boolean;

我们的程序不主张使用 windows.h ,一直以来也没有去包含 windows.h

但是,今天包含 windows.h 时发现,boolean 被 redefinition 了。因为 C 语言里的 #ifdef 只能检查宏定义,而不能检查 typedef 定义,所以这个问题比较棘手。

资源的管理及加解锁

周末我们遇到一个问题。运行时的资源需要统一的管理,资源本身是用垃圾回收的方法管理的。但是,有时候资源需要 lock 住,发生 gc 的时候绝对不能清理掉。我们最初的想法是,把加栽的资源 lock 的时候挂到一个 lock 链上,unlock 的时候取下来。

但是资源这个东西经常被重复使用,而我们又没有引用记数,导致 unlock 的操作无法正确工作。

March 13, 2006

监视单件的调用

我们现在的引擎中,所有的单件由一个管理类来管理。任何一个模块想取到一个单件,都可以通过一个统一的方法从管理类中拿到。

在调试程序的过程中,我遇到了一个奇怪的需求。我需要在一个单件的方法被调用时,程序都会停下来,进入调试器。

诚然,如果每次单件都通过 get_instance 取得,然后调用其方法的话,我们在 get_instance 里设置断点即可。但是,在我们的引擎中,每个模块都是在初始化阶段,拿到单件的指针。然后放在了全局变量中。单件的使用,直接运用这个指针。这样,就对监视这个单件的调用造成了麻烦。

为了解决这个问题,我用了一个很 trick 的方法,下面列出代码。

February 14, 2006

double to int 神奇的 magic number

前段时间写过一篇 blog: _ftol 的优化。 今天在读 lua 5.1 的 source 的时候,发现一个更加有趣的技巧。把 double 转成 int 居然可以这样的简单。

union luai_Cast { double l_d; long l_l; }; #define lua_number2int(i,d) { volatile union luai_Cast u; \ u.l_d = (d) + 6755399441055744.0; (i) = u.l_l; }

这个宏神奇的在正数和负数的双精度浮点数时都可以正确工作,以四舍五入方式转换为 32 位整数。

December 20, 2005

把结构定义成一个数组

今天读 freebsd 的源码时发现一个小技巧,经过同事指点,恍然大悟。原来 C 里面还是有好多东西自己不知道的啊。

typedef struct _jmp_buf { int _jb[_JBLEN + 1]; } jmp_buf[1];

这个是 setjmp.h 里的一行定义,把一个 struct 定义成一个数组。这样,在声明 jmp_buf 的时候,可以把数据分配到堆栈上。但是作为参数传递的时候则作为一个指针。这样和 c array 的表现一样了。

btw, 读 freebsd 的源码后,感觉头文件组织比 vc 的强太多了。

December 16, 2005

_ftol 的优化

_ftol 是什么? 当你写 C 程序的时候,(int)float_v 就会被编译器产生一个对 _ftol 这个 CRT 函数的调用。 上个世纪听一个做 3d 的朋友提起过,用 x87 指令实现的 _ftol 会很慢,一般用整数指令提供。当时提在心里,2000 年的时候在 RISC 上做开发 (ARM 指令集) 曾经写过一些整数模拟浮点的函数,曾经写过这个转换函数,日子久了,现在也找不回来代码。不过对浮点的 IEEE 标准还是比较清楚的。去年写过一篇 浮点数的精度控制问题 的帖子放在流言中。当时已经被骂过了。 今天工作时又遇到关于浮点数的问题,再写篇 blog 吧,或许还是找骂贴 :)

November 24, 2005

游戏的优化——不仅仅是帧速率

周一在上海的 <a href="http://www.zhucheng.biz/seminar">Modern C++ Design & Programming 技术大会</a> 上做了一个演讲。这里是<a href="http://www.codingnow.com/2005/optingames.ppt">讲稿 PPT</a>

这次 C++ 大会收获颇丰,刚从成都出差回来很累,今天就不写了。

October 31, 2005

VC 对 memcpy 的优化

在很多编译器中,memcpy 是一个 intrinsic 函数,也就是说,这个函数是由编译器实现的。它比 inline 函数更容易被编译时优化。编译器可以根据 memcpy 的参数是常量还是变量做出多种版本,达到最佳的性能。这一点,用 inline 或者 template 的技巧都无法办到。