« September 2005 | Main | November 2005 »

October 31, 2005

VC 对 memcpy 的优化

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

我们看看 VC 对 memcpy 的优化。(所用版本 VC6)

void foo(void *d,const void *s)
{
memcpy(d,s,1);
}

选性能最优化,生成汇编代码可以看到。代码被优化成:

mov eax, DWORD PTR _s$[esp-4]
mov edx, DWORD PTR _d$[esp-4]
mov cl, BYTE PTR [eax]
mov BYTE PTR [edx], cl

只是一个字节拷贝,用 cl 寄存器 mov 完成的。

把 1 改成 4 后:

mov eax, DWORD PTR _s$[esp-4]
mov edx, DWORD PTR _d$[esp-4]
mov ecx, DWORD PTR [eax]
mov DWORD PTR [edx], ecx

就变成了一条最普通的 mov 指令。

如果是 8 个字节:

mov eax, DWORD PTR _s$[esp-4]
mov ecx, DWORD PTR _d$[esp-4]
mov edx, DWORD PTR [eax]
mov DWORD PTR [ecx], edx
mov eax, DWORD PTR [eax+4]
mov DWORD PTR [ecx+4], eax

就是两条 mov 指令。

直到长度是常量 19 还是用 mov 完成的:

mov eax, DWORD PTR _s$[esp-4]
mov ecx, DWORD PTR _d$[esp-4]
mov edx, DWORD PTR [eax]
mov DWORD PTR [ecx], edx
mov edx, DWORD PTR [eax+4]
mov DWORD PTR [ecx+4], edx
mov edx, DWORD PTR [eax+8]
mov DWORD PTR [ecx+8], edx
mov edx, DWORD PTR [eax+12]
mov DWORD PTR [ecx+12], edx
mov dx, WORD PTR [eax+16]
mov WORD PTR [ecx+16], dx
mov al, BYTE PTR [eax+18]
mov BYTE PTR [ecx+18], al

长度达到 20 后,就转变成了使用 rep movsd

push esi
mov esi, DWORD PTR _s$[esp]
push edi
mov edi, DWORD PTR _d$[esp+4]
mov ecx, 5
rep movsd

pop edi
pop esi

如果长度并非 4 的整数倍的话,比如复制 23 个字节:

push esi
mov esi, DWORD PTR _s$[esp]
push edi
mov edi, DWORD PTR _d$[esp+4]
mov ecx, 5
rep movsd
movsw
movsb

pop edi
pop esi

编译器会在后面插入 movsw 和 movsb 。

现在我们来看看,memcpy 的长度是变量的情况:

void foo(void *d,const void *s,size_t size)
{
memcpy(d,s,size);
}

这次编译器直接调用了 rep movsd

mov ecx, DWORD PTR _size$[esp-4]
push esi
mov esi, DWORD PTR _s$[esp]
mov eax, ecx
push edi
mov edi, DWORD PTR _d$[esp+4]
shr ecx, 2
rep movsd
mov ecx, eax
and ecx, 3
rep movsb
pop edi
pop esi

因为我们并不知道 size 是否是 4 的整数倍,所以尾巴上用 and ecx,3 / repmovsb 来处理了一下。

那么我们能否通知编译器,需要 memcpy 的数据块长度是 4 的倍数呢?答案是可以的。看看编译器怎么编译 memcpy(d,s,size*4);

mov ecx, DWORD PTR _size$[esp-4]
push esi
mov esi, DWORD PTR _s$[esp]
push edi
mov edi, DWORD PTR _d$[esp+4]
rep movsd
pop edi
pop esi

非常简洁,不是吗?

October 29, 2005

lua 的 table 处理

lua 的整体效率是很高的,其中,它的 table 实现的很巧妙为这个效率贡献很大。

lua 的 table 充当了数组和映射表的双重功能,所以在实现时就考虑了这些,让 table 在做数组使用时尽量少效率惩罚。

lua 是这样做的。它把一个 table 分成数组段和 hash 段两个部分。数字 key 一般放在数组段中,没有初始化过的 key 值全部设置为 nil 。当数字 key 过于离散的时候,部分较大的数字 key 会被移到 hash段中去。这个分割线是以数组段的利用率不低于 50% 为准。 0 和 负数做 key 时是肯定放在 hash 段中的。

string 和 number 都放在一起做 hash ,分别有各自的算法,但是 hash 的结果都在一个数值段中。hash 段采用闭散列方法,即,所有的值都存在于表中。如果hash 发生碰撞,额外的数据记在空闲槽位里,而不额外分配空间存放。当整个个表放满后,hash 段会扩大,所有段内的数据将被重新 hash ,重新 hash 后,冲突将大大减少。

这种 table 的实现策略,首先保证的是查找效率。对于把 table 当数组使用时将和 C 数组一样高效。对于 hash 段的值,查找几乎就是计算 hash 值的过程(其中string 的 hash 值是事先计算好保存的),只有在碰撞的时候才会有少许的额外查找时间,而空间也不至于过于浪费。在 hash 表比较满时,插入较容易发生碰撞,这个时候,则需要在表中找到空的插槽。lua 在table 的结构中记录了一个指针顺次从一头向另一头循序插入来解决空槽的检索。每个槽点在记录 next 指针保存被碰撞的 key 的关联性。

整个来说,这种解决方法是非常不错的。

关于映射表的实现,我前段时间也做过一个别的研究。贴在留言本上:
树表结合的一种映射表实现
在 vector , map , list 间取得平衡

October 27, 2005

Windows 对 DLL 文件的一些处理

Windows 的 DLL 文件是可以有别名的,它设置在 HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\KnownDLLs
中,用注册表编辑器,我们可以看到这个别名的列表。

比如有一条数据是 kernel32 / kernel32.dll 这条记录保证了再调用 LoadLibrary("kernel32.dll") 的时候,系统总是调用的 system32 下的 kernel32.dll 这个版本。而不会是当前目录下的 kernel32.dll (如果有的话)

这是如何做到的呢?

LoadLibrary 发现参数字符串中需要加载的是 kernel32.dll (没有显式指定路径) 的话,就会在注册表中找到 DllDirectory 这一项,再那个指定路径下加载 kernel32.dll 。

注意,这里的键名是没有 .dll 的后缀的。系统在识别 dll 是否属于 KnownDLLs 的时候,只能对需要加载的后缀为 .dll 的文件起效,在匹配键名的时候再截断后缀。

我们也可以通过修改注册表,达到给这些系统的 DLL 换名的效果。

关于 COM 对象 DLL 存放在本地目录的问题

已经注册的 COM 对象,如果害怕跟别的软件冲突,就可以用 DLL 转移技术。不过这个 Windows 98 中是不支持的。

比如 myapp.exe 想强制优先加载当前目录下的 DLL ,那么只要创建一个文件名叫作 myapp.exe.local ,启动 myapp.exe 后, DLL 都将优先从当前目录加载了。


October 26, 2005

Windows 下的进程间通讯及数据共享

Windows 下有很多方法实现进程间通讯,比如用 socket,管道(Pipe),信箱(Mailslot),等等。但最基本最直接的还是使用内存共享。其他方法最终还是会绕道这里。

可想而知,如果物理内存只有一份,让这份内存在不同的进程中,映射到各自的虚拟地址空间上,每个进程都可以读取同一份数据,是一种最高效的数据交换方法。下面我们就讨论如何实现它。

共享内存在 Windows 中是用 FileMapping 实现的。我们可以用 CreateFileMapping 创建一个内存文件映射对象, CreateFileMapping 这个 API 将创建一个内核对象,用于映射文件到内存。这里,我们并不需要一个实际的文件,所以,就不需要调用 CreateFile 创建一个文件, hFile 这个参数可以填写 INVALID_HANDLE_VALUE 。但是,文件长度是需要填的。Windows 支持长达 64bit 的文件,但是这里,我们的需求一定不会超过 4G , dwMaximumSizeHigh 一定是 0 ,长度填在 dwMaximumSizeLow 即可。然后调用 MapViewOfFile 映射到当前进程的虚拟地址上即可。一旦用完共享内存,再调用 UnmapViewOfFile 回收内存地址空间。

Windows 把 CreateFileMapping 和 MapViewOfFile 两个 API 分开做是有它的道理的。这是因为允许映射一个超过 4G 的文件,而地址空间最大只有 4G (实际上,一般用户的程序只能用到 2G) , MapViewOfFile 就可以指定文件的 Offset 而只映射一部分。

在 CreateFileMapping 的最后一个参数 pszName 填写一个名字,那么别的进程就可以用这个名字去调用 OpenFileMapping 来打开这个 FileMapping 对象,在新的进程内作映射。 不过,通过约定字符串的方法似乎不太优雅。

一个优雅的方法是,用 DuplicateHandle 在新进程中复制一份 FileMapping 对象出来,然后想办法把 Handle 通知新进程,比如用消息的方式传递过去。

如果需要共享内存的两个进程是父子关系,那么我们可以不用消息传递的方式来通知 FileMapping 的 Handle 。父进程可以用继承 Handle 的方式直接把 FileMapping 的 Handle 传递到子进程中。当然,在 CreateFileMapping 时就应该设置可以被继承的属性。

大约是这样:

SECURITY_ATTRIBUTES sa;
sa.nLength=sizeof(sa);
sa.lpSecurityDescriptor=NULL;
sa.bInheritHandle=TRUE;
handle=CreateFileMapping(INVALID_HANDLE_VALUE,&sa,PAGE_READWRITE,0,size,NULL);

这样,在 CreateProcess 的时候,如果 bInheritHandles 参数为 TRUE ,所有有可被继承属性的内核对象都会被复制到子进程中。

注:内核对象的继承就是在 CreateProcess 创建子进程,但是子进程的主线程尚未活动之前,内核扫描当前进程中所有内核对象,检查出有可继承属性的那些,再用 DuplicateHandle 复制一份到子进程。由于是内核对象,在内核中实质只有一份,所有只是引用记数加一,父进程和子进程对同一内核对象的 Handle 一定是相同的。

复制内核对象的过程是由 CreateProcess 内部完成的,我们可以放心的把对象 Handle (和子进程相同) 通过命令行传递给子进程。或者,用环境变量传递也可以。

值得注意的是,子进程用完了这个 FileMapping 对象后一样需要 CloseHandle 减去引用计数。

备注:
CreateProcess 调用时,pszCommandLine 不能直接填上一个不可修改的字符串。例如:

CreateProcess("test.exe","test argument",...);

这样就是错误的,因为 "test argument" 会被编译器编译放到不可修改的数据段中。正确的方法是:

char cmdline[]="test argument";
CreateProcess("test.exe",cmdline,...);

这样,命令行的字符串就被放在堆栈上,是可以被读写的。

CreateProcess 的倒数第二个参数需要填写一个 STARTUPINFOW 结构,这个结构很复杂,通常填起来很麻烦。我们可以复制一份父进程的结构,再酌情修改。方法是:

STARTUPINFO si={sizeof(si)};
PROCESS_INFORMATION pi;
GetStartupInfo(&si);
CreateProcess(...,&si,& pi);

这里, STARTUPINFO 结构的第一个长度信息通常应该填上,保证 GetStartupInfo(&si); 的正确执行。

October 21, 2005

针对网络游戏客户端更新的 P2P 网络

我最近在构思一个用 P2P 网络同步文件的计划。用于以后网络游戏的 client 同步更新。现有的 BT 之类的软件很成熟了,不过我考虑到网络游戏有其特殊性,说不定可以做的更好。

网络游戏可以说有一个天然的稳定的 p2p 网络的基础,好象我们的梦幻西游,最高已经超过八十万玩家同时在线了。而所有玩家所需求的是同一份 client。这跟 BT 网络上传输文件的需求和环境都不太相同。

游戏服务器将是一个天然的中心管理服务器,类似 BT 的种子发布服务器。BT 的下个版本据说要加入分布式的用户列表。也是,如果真有几十万玩家同时需要共享一份文件时,让每个玩家都知道他们的几十万同伙的位置是不现实的。这就需要分布式来做。而且,我们的游戏相关服务器是全职为玩家服务器的,无论从带宽还是性能上,都非常不错,这点应该加以利用。

关于分布式用户列表的问题暂时不讨论了,我最近想的比较多的是针对 LAN 的优化。

很明显,现在国内的网络玩家很多都是网吧用户。网吧更新是一个大问题,以前没有用 P2P 技术前,网吧老板大多采用自己同步 client 的作法。现在越来越多的游戏 client 采用 P2P 了,一般内嵌一个 BT 。但是当用户特别多时,BT 种子服务器都不堪重负(这个是存在于我们公司运营中的梦幻西游和大话西游的事实)。

如果能针对 LAN 做一些优化就好了。我能想到的是,如果一个玩家可以在自己的 LAN 上发现一份 copy ,就不再外连 BT 种子服务器,而是相互通讯,复制一份过来。整个 LAN 充当外部 P2P 网络的一个节点,如果有对外的连接任务,大家应该协商平摊,不应该做重复的事情。而且任务也尽量分散,不让某一台机器处理的任务过多,造成 CPU 和单机的网络负载太大。

在一个 LAN 上,各个玩家伙伴的身份是对等的,没有中央服务器,所以协调工作是很难展开的。我们务必先产生出一个领导者。因为领导者是临时产生的,我们无法确定它的机器性能如何,是否能长期稳定工作。所以,我们不能让领导者担负过强的工作,而且要有集体认可的候补人员。

能想到的最简单的集体推选方法是这样的:我们默认的标准是,IP 值最小的人是当然领导候选人。每个 client 进程启动后,都向 LAN 广播,准备参选领导职位。如果 LAN 上已经存在领导人,每个人都回复他现在的领导人是谁。如果他是更适合当领导的人,所有人回复他,承认他的地位。

当这个新人收到别人的通知,得知领导人以后,他却没有收到领导人的消息,认为现任领导人可能失踪。由这个人推举新领导。直到大家都确认领导人是谁。

所有点对点传输任务,必须得到领导的认可。新人只有找到领导后,向领导索取LAN上自己的结队对象,领导分配至少1个的结队对象给他。这个新人再主动去向这些对象索取需要同步的文件。注:这里,LAN 上任何一个人向自己索取文件,并不需要先得到领导的同意就可以满足其要求。

整个 LAN 对外的连接需要得到领导的同意,当整个 LAN 上文件都不全时,领导主要定期向外索取连接,但是这个连接任务应该分摊给大家,而不是全部由自己连接。当同伴完成任务后,应该主动讲获取部分传回领导。(然后领导通知其他人去索要)

当整个 LAN 文件收全后,为了保证外部 P2P 网络的健全,整个 LAN 作为一个节点,应该主动发起连接,这个发起者就是领导。领导定期分配任务给同伴,让每个人平均分配对外的连接。

所有人都应该定期保持对领导的联系,防止领导意外失踪。

October 18, 2005

保重身体

今天体检,起了个早床,六点就爬起来了,当然昨天还是按惯例两点睡的。不是很困,但是也没什么精神。检查结果,别的都一切正常,血压略微有点点偏高。

这可能是经常熬夜弄的。想想去年体检的时候,也是如此,第一次量血压也是略微偏高,洗了把脸再测又正常了,就没在意。今天看来,是应该注意身体了。

按理说平时锻炼也挺多的,身体还算强壮,每周还有两次攀岩的活动。每天也吃好喝好的,没有啥不良嗜好。想来也就是喜欢晚睡晚起了,现在已经习惯了每天两点睡觉,十一点半起床,睡眠时间是够的,就是跟别人生物钟不同吧。知道这样不太好,几次想改,可是每次要改的时候就弄个失眠,生物钟紊乱什么的。

唉,不过想来想去,身体还是要好好调理一下了。现在每次运动过量就会头晕,睡觉睡过了也会头痛,梦魇,的确很多不良的信号的 :(

October 14, 2005

纤程

Widnows 是提供了用户级线程的,类似 coroutine 需要用户主动是切换。这在单线程程序中非常有用。线程调度模块只负责提供堆栈,环境的保存。不负责分配时间片等。

自己实现 coroutine 并不难,但能用操作系统提供的可以得到更多的便利。Windows 中把这种用户级线程叫做 Fiber,纤维的意思。比较通用的译名是纤程。

我们可以把一个 thread 转换成一个 fiber ,用到的 API 是 ConvertThreadToFiber。其实用的更多的是CreateFiber,它可以创建一个纤程,但并不切换过去运行。

被创建出来的 Fiber 会有一个上下文的地址被返回,用于以后的切换操作。我们可以用 SwitchToFiber 来切换。这是唯一用于 Fiber 释放操作权的途径。SwitchToFiber 必须显式的指定切换的目标,所以 Fiber 调度的工作需要我们自己写代码来实现。

GetCurrentFiber 和 GetFiberData 这两个函数都很有用,一个用来取到运行环境,一个用来取得创建参数,这两个函数都是用 inline 函数的形式提供在 .h 文件中的。

October 11, 2005

游戏,一种奇怪的软件

现在做半职业游戏策划了,但是还是改不了程序员的老毛病。尤其是在写策划案的时候,方更加觉得程序的优美。程序是可以调试的,可以用工程的方法做质量控制,可以有测试的机制。大多数时候是可以被验证的。而且掌握了正确的方法,我们可以一步步的把程序搭出来,逐步看到成果。

但是游戏,作为一种软件则不然。

首先,游戏设计中,多出了一个游戏策划的概念。往往,一个大型的游戏还不只一个人,而是一组人。而平常做软件,尤其是小作品,往往是实现的人是第一用户,在构思怎样让软件贴近用户。(我个人认为,游戏软件还是属于一种规模不大的小作品)作为游戏策划仿佛漫无目的在想在写。却在构思和实现之间断了层。而且文档这种东西是无法量化的验证并做质量保证的。

其实,把思考建立在一个高的层次而不必理会低层次的机理并非坏事。单从写程序来讲,一个 php 程序员可能永远不用关心 php 本身是怎么实现的,他的程序是如何转换为机器代码,运行于 CPU 的。相反,一个好的 C 程序员刚刚转写 php 的时候,通常不会是一个好的 php 程序员。这种以高层次为基础来发展的东西,更多靠的是经验的总结和学习,而非理论和逻辑的推理。(当然从更高层面说,有了足够的经验总结后,更宏观的工程,可以从这些微观的经验上基于逻辑推理来描述)

游戏策划估计也是这样吧。所以游戏策划更依赖一个成熟的团队,和技术基础。人的思维空间是有限的,思考深度也是有限的。有了一个牢固的根基后,才有发展的深度和广度。

胡乱说了一通,也不知道自己想表达什么。无意褒贬游戏策划这个职位。只是感叹现状。

October 09, 2005

新的开始

一直想有个地方随便写点什么,以前用 javascript 做个人网站也是想简化网站维护的流程。虽然早就知道 BLOG 会比较适合自己的需要,但是因为懒,也就一直没有做。

这个国庆过完了,最近几个月也弄了不少东西出来。原来主页的留言本看来是不能再将就下去。自己用 php 或是别的做一个 BLOG 系统显然不大现实,所以还是找来了个现成的,也就是现在这个 Moveable Type 3.2 。

虽说是安装现成的软件,对于 linux 不太熟悉的我,还是颇费了一些工夫。慢慢来吧,希望是个好的开始。