« July 2008 | Main | September 2008 »

August 24, 2008

_alloca 函数的实现

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

alloca 的函数原型是

void *
alloca(size_t size);

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

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

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

这个周末,我手工写了一个 _alloca ,试着替换 CRT 的实现(莫追究原因 :) )。一开始老不得要领,总是不能正常工作。

gcc 的这个 _alloca 是个内部函数,其调用协议不同于 alloca 。它的尺寸参数并不通过堆栈传递,而是直接通过寄存器。在 X86 上,就是 eax 。

返回值当然是通过 eax 送出,同时一并修改了堆栈寄存器 esp 。

经过多次程序崩溃,并用 gdb 对汇编代码逐行分析,还看出了另外一点门道。

调用 _alloca 这个函数前,调用者并不需要对其它寄存器里的数据安全负责。就是说,_alloca 需要负责除 eax esp 之外的寄存器内的数据安全,不得破坏。(或许没有这么严格,我试着用了一个 ecx ,并没有出错。但是破坏掉 edx 却是一定会引起程序崩溃的)

如果打开 gcc 的优化开关(我使用的 -O2 ,gcc 版本 3.4.5),编译器有时候会预测 _alloca 的行为,并以此来决定堆栈上局部变量的分布(往往出现在代码中以常量申请固定尺寸的大数组的情况下)。_alloca 的行为被认为是在堆栈上准确分配经过 4 字节对齐后的 eax 内值大小的空间。不仅不能少分配,连多分配也是不允许的(否则会导致编译器生成的代码出错)。

最后给出云风的 _alloca 的实现。

.globl __alloca; 
__alloca:
    subl    $1,%eax
    andl    $0xfffffffc,%eax    /* align to dword */
    subl    %eax,%esp
    pushl   (%esp,%eax)     /* return addr */
    movl    %esp,%eax
    addl    $4,%eax
    ret

ps. 这个帖子放在这里,日后肯定会有同学偷懒搜代码搜过来的,嘿嘿。程序随便用,但出了问题别找我。我不帮人做作业。

August 15, 2008

让 lua 编译时计算

lua 里其实也颇多奇技淫巧,使用时应三思。

如果你读过 kepler 的代码,就会发现,多次编译这种技巧用的很多,甚至迭代几次使用。即,第一次加载代码时,用一段 lua 程序生成真正需要的源代码,然后再将其编译出来。

由于 lua 的编译速度相当快,而且这种迭代编译的过程仅仅在程序加载的时候进程一次,故而可以带来性能的提高:一些在系统初始化时可以决定的参数(比如从配置文件中读出来的数据)直接编译为常量置入程序中。

云风写了一小段 lua 程序,简化这种迭代编译的过程,算作周末自娱吧。

例如这样一个例子,我们在程序中需要用一个常量,这个常量可能是通过加载配置文件得到。假设允许编译期计算,我们可以这样:

function foo()
    for i=1,| config "max" | do
        execute(i)
    end
end

这个例子里,循环的终值是通过调用 config "max" 得到的,如果每次运行这个程序时都去查询 config 必然影响效率。我们需要在程序加载时,第一次得到 config "max" 的结果即可。

这里,我使用 | 夹在中间 | 表示这段代码应该在加载时运行。

有点像 php 写网页用的模版?呵呵,可以接着往下看。

姑且我们把这种技术叫做代码模版吧,对于 C 程序员,则更接近于宏替换,C++ 程序员看来可能是一个高级 template 技巧。不过 lua 能做的更强一些。

我来演示一下,代码模版的上下文变量。

| ALPHA = math.pi / 4 |
function foo(a)
    return a * math.sin(|ALPHA|)
end

这个例子里,一开始给代码模版变量 ALPHA 赋了值为 pi/4 。然后在下面的函数中,使用了这个变量。这段代码经过处理后,会把常量 0.78539816339745 (pi/4) 直接编译进入最终执行的代码。而 ALPHA 这个变量,将只在模版预处理期间可见。

下面再看一个更实用一点的例子。

有时候,我们需要一个增强版的 unpack 。我们知道,lua 自带的 unpack 可以把一直数组(只有连续数字下标的 table)展开成一串返回值,但是对用字符串或别的东西做 key 的 table 无能为力。

function unpackex(tbl,args)
    local ret={}
    for _,v in ipairs(args) do
        table.insert(ret,tbl[v])
    end
    return unpack(ret)
end

下面我们可以用这个函数展开一个数组,

print ( unpackex( { one=1,two=2,three=3 }, { "one","two","three" } ))

unpackex 将按第 2 个参数表中给出的字符串次序解开第一个参数表。这里我们将看到输出 1,2,3 。

btw, 如果你真的需要一个高效的 unpackex ,推荐用 C 来实现,这样能省掉其中的临时 table ret 。

接下来,我们在使用 unpackex 时,还有可能遇到一个性能问题。因为第二个参数表通常是个常量数组,但由于 lua 的语义,下列函数中的这个常量表,可能在每次进入函数 foo 时构造一个新的出来。

function foo(tbl)
    return unpackex(tbl,{"one","two","three"})
end

如果 foo 对性能很敏感,有经验的 lua 程序员或许会这样优化一下:

local const_list={"one","two","three"}

function foo(tbl)
    return unpackex(tbl,const_list)
end

但这破坏了代码的直观。如果有了代码模版,我们实际上可以写成这样:

function foo(tbl)
    return unpackex(tbl,| {"one","two","three"} |)
end

ok. 现在基本能看出来这个代码模版做了些什么。

它在分析源码字符串时,碰到 | 夹住的部分,将立即运行,获得结果。如果没有结果(例如只是运行一些代码,无返回值),则跳过。如果有结果值(可以由 return 返回,也可以本身是一个表达式),先判断类型是否是一个简单类型(nil ,boolean ,number 或 string ),就把值直接插入源码。如果是一个复杂类型,则创建一个 local 变量记住结果,并将这个 local 变量插入代码。

这里,简单类型 string 会被加上 [=[ 这样的括号插入。而有时候,我们需要直接把字符串插进去。

例如,有时候我们期望 lua 有 C 的 include 那种功能,直接把一文本文件插入源码。

为了效率,我们通常在每个 .lua 文件最前面写上诸如:

local pairs=pairs
local table=table
local string=string

这样的语句。

这可以提高 lua 程序访问内置 api 的效率(减少一次对全局表的查询)。

但每个文件前都写这么一串过于繁琐,也容易出错。如果有 include 功能就好了。那么就让我们实现一个:

function include(filename)
    local f=assert(io.open(filename))
    local ret=f:read "*a"
    f:close()
    return ret
end

这个函数可以读入一段文本返回。

代码模版可以通过 |# include "local.lua"| 这样的语法,将 include 函数的返回值插入代码。(注:遇到 | 后紧跟一个 # ,这个区间的返回值就必须是一个 string ,并且这个 string 将被插入代码)

最后,来看看代码模版的实现吧,使用 lua 本身就可以轻易搞定。有兴趣的同学点这里

August 13, 2008

Lua 不是 C++

嗯,首先,此贴不是牢骚帖。

话题从最近私人的一点工作开始。应 dingdang 的建议,我最近在帮 大唐无双 做一些程序上的工作。接手做这件事情,是因为这个内部被我们称作 dt2 的游戏 engine 关系重大。公司有至少四个项目在使用(另外三个暂处于研发期,尚未公布)。

dt2 用了大量的 lua 代码构建系统,但从系统设计上,沿袭了老的大唐的许多代码。原来的大唐是用 C++ 构建的,为了利用上这些代码(虽然我觉得这种复用非常无意义,但是其中原因复杂,就不展开谈了),dt2 engine 的开发人员做了一套非常复杂的中间层,把 lua 和 C++ 几乎无缝的联系在了一起。

从表征上看,可以完全不修改 C++ 代码,只额外加上一些东西,便可以在 lua 中得到一个类对象,从语法上相当接近的使用 C++ 的类,并可以对其继承,用 lua 重载其虚函数。甚至可以实现多重继承。

由于项目组隔的比较远,所以直到最近一个月,我才拿到这套东西的文档和源码。我的直觉告诉我,这属于过厚的粘合层,是绝对需要抛弃的。如果不是无双内测初期频频的出现 bug ,可能不会有太多人赞同我这个观点。但事实上,即使这个粘合层实现的绝无问题,完全正确的使用它也几乎是不可能的。这么厚的粘合层很难做到 robust 。

这段时间,在开发维护人员的不懈努力(不包括我,在为这个项目修 bug 的工作上,我只是一打酱油的)下,主要的 bug 也修的差不多了,但是做一些适度的改造也必须开展。跟 engine 的前开发人员聊过,我很能理解这个东西被做成这个样子,以及为什么做这样一个东西的必然性:对 lua 的不熟悉,以及迫切的需要复用 C++ 代码。但是我依然想说,解决问题之道在于,先仔细考虑问题存不存在。不做是最好的做法。

表面上看起来,这个粘合层是设计的是很精妙的,它隐藏了 lua 虚拟机的细节。C++ 程序员在写代码的时候,并不需要实际上也的确是,不知道 lua 的存在。而 lua 程序也不需要关心那个类是用 C++ 实现的。在 lua 中,可以按照 C++ 的对象模型继续对类进行继承扩展。一切都展现的完美无缺。

C++ 的代码从某种程度上也显得非常有水准,template 的灵活使用,可以在可能存在的领域重复利用发挥出功效,大量使用的 stl 容器以及智能指针保证了底层领域的健壮。

如果不是这个粘合层的对象生命期管理出了一点设计上的小问题。在 C++ 的引用计数和 lua 的 gc 管理之间有点搅和不清,我想,这个东西可能就一直用下去了。我也不会被派来对这些代码做 code review 。

没错,代码的 bug 最终都可以改过来,这个设计点上的错误也可以想办法用比较小的代价纠正。但是,仔细的考虑一下,整件事情应该去做吗?在 lua 里实现一个 C++ 的面向对象的对象模型?


面向对象不是 C++ 语言向我们展示的那些东西。这不是 C++ 语言的错,因为 C++ 只是在用它的方式去表达而已。我们可以去寻求 lua 的表达方式,正像 ROR 追寻 ruby 的表达方式一样。

诚然,培养新的语言的程序员,比把一门语言模拟成另一种要困难的多。如果我们用写 C++ 程序的思考方式去写 lua 程序,那么当我们决定把游戏用 lua 重新实现一次。除了性能,我们还会失去很多。

前段时间去广州出差,和西游组的同事吃饭。据说最近一年来,他们改进了大话和梦幻的服务器设计,把处理连接的部分独立出来放到单独的进程中 ,使服务器性能大大提高。梦幻西游的服务器,已经可以做到单台机器支持一万人同时在线。

可惜的是,大话 3 的服务器,依然徘徊在单机三千人左右。表面上最大的区别是,梦幻西游的游戏逻辑是用一种类 C 的脚本语言 LPC 写的,而大话3 则是用的 lua 。

刨除大话 3 更为复杂的逻辑处理的因素,追根到底是,lua 的表达能力更强,导致了程序员用更 C++ 的方式去用 lua 。而原来的 LPC 的代码更接近 C 一些。

不是说 C++ 比 C 慢,对于编译语言来说 C++ 甚至比 C 的执行性能更高。但是对于解释型的动态语言。那种看起来更 C++ 的风格会拖垮运行性能许多。对于开发人员来说 lua 5 以后加入的 meta table 是个好东西,但是任何强大的特性都可能被滥用。有幸 lua 还是门简洁的语言,如果有一天 ruby 在游戏开发圈子里流行起来,我都不敢想会发生怎样的事情 ;)

对于那些新接触 lua 的 C/C++ 程序员来说,我的第一条建议通常是:看看 lisp/scheme 吧,可能 lua 的血统里,scheme 的成分比 C 更多一些。要不玩一下 Haskell ,增进对函数式编程的了解。C++ 借助 template 是可以玩玩函数式编程,但很少有人真的去用。进入 lua 的领域后,你得正正经经的理解一下了。


关于 dt2 engine ,这几天我为之做的最多的事情是重新实现了一个 timer tick 的系统,这个东西很早以前就做过,也有现成的代码。不过 200 行。

但是,重新实现一个的意义在于:把这个子模块剥离出来,绕过原来的厚粘合层。而不是先前的那种设计:在 C++ 里实现一个 CTick 类,然后从 lua 中继承它,再注册回 C++ 中的 CTickMgr 。

可能下一步还会协助开发组的同事把连接管理分离出来,并改进数据库的访问。

最后友情做一个广告:大唐无双 这个游戏还是不错的。美术和玩法方面都有了长足的进步。技术问题我相信在大家的努力下都会慢慢的解决。网易的开发团队还是很强的。

最近太不小心

前天晚上做深蹲练习,做了两组感觉不太对劲,改做腿举。后来又换了几个器械练习大腿。可能是练过了,一开始回办公室的路上没觉得有什么,在公司冲了个淋浴然后回家。结果在办公楼前的小台阶上膝盖一软跪到地上摔了一跤。

心里暗暗嘲笑自己这么没用,想当年做深蹲,一百多公斤几十个的做都没问题,如今怎么这么快就脱力了。幸亏胳膊还有力气,回家那三层楼就靠手这么拉上去了。

原来以为睡一觉起来就会恢复的,结果昨天一起床坐在床边居然站不起来。勉强用手撑起来后,一下没站稳又坐到地上了 :( 等再次站起来,很小心的小步走到厨房弄吃的。走顺当了不免得意忘形,步子迈大了一点,膝盖一弯就跪在了地上。

这下够惨的,周围没啥支撑物,胳膊在摔倒的时候还被蹭破了。在地上躺了两分钟,冷静了一下才想了个方法支撑起来。接下来不敢大意了,扶着个椅子在屋子里移动。

好不容易拿了吃的回到床上,吃饱了仔细检查了一下双腿,除了摔跤后的轻微纽伤,似乎没什么大碍。就是肌肉无力,动弹不得。用手机 google 了半天也得不出个所以然来。我想也是正常现象吧,前段时间练上肢也遇到过类似情况。需要点时间修养。

想来自己是很难靠自己下楼了,估计走路也得万分小心。大街上摔倒了爬不起来那可够惨的。最终决定打电话让同事来架我上班去。

我是个坐不住的人,结果昨天在办公室只好推着个椅子溜达,防止走路的时候摔倒。


庆幸的是,肌肉恢复的比预期的快,今天早上一抄煤气表的按门铃,我在床上还没完全清醒,噌的就坐了起来过去开门,这才意外的发现腿已经恢复了 :D 就是多了点点酸,知道那是乳酸堆积,很正常的。

不过奇怪的是,上周同样练深蹲,运动量也不小,但那次居然什么事情都没有,腿也不酸,不知道这次怎么弄的。


ps. popo 上跟同事 siney 聊天,他说他前段没怎么运动,光吹空调也吹出过这毛病。我想我还是坚持晚上不开空调比较好。而且比较环保。

会不会有种说法,无氧运动后休息时少吹空调?

August 07, 2008

人不可貌相

昨晚从健身房出来,去找地方觅食。路上碰见一小孩儿问路。满口长沙口音。虽然我毕业有点年头了,可还会说那么两句长沙话。饶有兴趣的逗了小孩子几句。

小孩旁边有一年轻人,看起来跟我一般年纪。我说道,幸亏我在长沙读过书,不然这当地人多半听不明白。

接下来的攀谈得知,这家伙居然是我的校友。其实我挺不好意思认校友的,因为在学校那几年,学业几乎荒废掉了,尤其怕人家跟我提某系某教授老师,我是一个都记不得了。(当年几乎没上课,怎能记得名字)

还好,大家只是交流了一下学校里的老建筑以及宿舍楼。他突然问我一句,那你现在毕业了吗?我大寒,在下毕业已经有八个年头了 -_-

“我 92 年毕业的”

……

亏我一直以为遇到个师弟。

August 06, 2008

被 Darcs 折磨了一天

最近想在子项目中试一下 darcs ,替代原来的 svn 。只是尝试一下。

之前都是在本地玩 darcs 的,没遇到多少问题。今天找了台 freebsd 的机器,做了一个集中的仓库。没想到遇到许多麻烦。

我的想法很简单,在集中仓库的机器上建一个专有用户,把几个项目相关人员的 key 都放进去,大家都可以通过 ssh 访问这台机器。那么所有人都可以方便的通过 darcs get/put/pull/push 操作仓库了。

从 freebsd 或 linux 上远程操作这个仓库都没有多少问题,问题出在 windows 上。windows 版的 darcs 在提交文件时,一旦 patch 过大,就很容易失败。弄了一天才把问题弄明白。

一开始怀疑是 darcs 版本不匹配,patch bundle 文件不兼容。因为 freebsd 上装的是 2.0.2 版,而 windows 上是 2.0.0 版的。提交失败时,总会报一句,

darcs failed: Malformed patch bundle: '[init' is not 'Context:'

貌似我的 init 这个 patch bundle 格式错误。尝试了老版的仓库格式还是依然存在。

google 了一下,有许多人遇到跟我一样的问题,但是没有人解答。我试着找 2.0.2 版的 windows 下编译好的 darcs 未果。想自己在 windows 下 build 一个出来,怎么弄都没搞定,放弃。转而去 freebsd 下自己 build 了个 2.0.0 版的 darcs ,可问题依旧。

我用 darcs send -O 生成 patch 文件,再用 scp 放到远程机器上,然后 ssh 登陆 darcs apply 一下却没有问题。确定不是版本不兼容问题。

通过修改 DARCS_SSH 设置了一个 bat 文件间接引导 ssh ,以此观察 darcs 如何调用 ssh 工作。发现,在 darcs push 的时候,其实就是在远程机器上运行了 darcs apply ,然后等待标准输入。这边通过 ssh 把 patch bundle 发送过去。

由于小的 patch bundle 没有问题,问题都出在文件太大的时候。让人怀疑是 windows 控制台的问题。胡乱改了一些 windows 控制台的属性,并反复测试,发现同样大小的 patch bundle ,有时候可以正常工作,有时候却不行。很难确定具体原因。症状就是:从 ssh 建立的管道发送过去的输入数据不完整。

最后,放弃使用 mingw 版的 darcs 以及 putty 带的那个 plink (ssh)工具;装了一个 cygwin 以及 openssh 。一切就正常了。另外,如果用 cygwin + putty 的 ssh 也有问题。

我估计很大可能出在那个 darcs 的 windows 包中带的 ssh.exe (其实就是 putty 的 plink.exe )这个工具上。windows 糟糕的管道设施或许也有责任。

哎,在 windows 上跑 *nix 的命令行工具就是问题多多啊。


随手记录下这失败的一天,希望可以帮助到遇到同样问题 google 到这里的人们。


顺便宣传一下 darcs ,虽然 windows 版很是折磨了我一次,但东西还是很好用的。如果你有 svn / cvs 的经验,很容易切换过去。下面列几条基本指令,前几条大约可以跟 svn 对应起来,但不完全一致。

  darcs get == svn co
  darcs put == svn import
  darcs pull == svn up
  darcs push == svn ci
  darcs record == 本地提交
  darcs send == 发送/生成 patch bundle
  darcs apply == 打上 patch bundle

darcs 是没有版本号的,工作理念跟 svn 很不一样,但是很人性,容易让人接受。推荐有兴趣的朋友试一试。