博文

目前显示的是 九月, 2011的博文

测试FatVariableLengthGammaTransaction的性能

图片
分配一个比较大的二维数组,然后在一个transaction中遍历这个二维数组,测试当单个transaction读写很多对象的时候的性能瓶颈。测试代码如下:
static AtomicBlock block = GlobalStmInstance.getGlobalStmInstance().newTransactionFactoryBuilder().setIsolationLevel(IsolationLevel.Serializable).setSpeculative(false).newAtomicBlock();
static final IntRef[][] grids = new IntRef[2500][2500];
public static void loop() { block.execute(new AtomicVoidClosure() { publicvoidexecute(Transaction tx)throws Exception { for (int i = 0; i != 2500; ++i) { for (int j = 0; j != 2500; ++j) { grids[i][j].set(tx, 1); } } } }); }public static void main(String[] args) {
System.out.println("begin");for (int i = 0; i != 2500; ++i) { for (int j = 0; j != 2500; ++j) { grids[i][j] = StmUtils.newIntRef(); } } for(intcount=0;count!=10;count++) loop(); System.out.println("end"); }测试结果:第一个方法,GammaObjectPool,是为了防止老是new对象,所以把废弃不用的对象组成了一个Object Pool。第二个,就是openForRead的时候需要频繁在hash表中查。…

内存事务如何选择加锁协议,乐观好还是悲观好?

最近我用 Multiverse STM做了一点东西。在开始动手之前,我专门测了multiverse的性能,发现它可以达到每秒2000多万次事务(每个CPU),于是我觉得它所带来的overhead应该是极小的,于是就放心大胆的用了。可是后来用profile工具看,我的程序始终是在openForRead这样的函数上占据了绝大部分时间。为什么? 这就涉及了multiverse STM是如何实现事务的。Multiverse的核心是Ref这个类。这个这个类,把普通的对象引用,转换成一个事务引用。例如Ref<Integer> i=StmUtils.newRef(Integer.valueOf(10)); 通过这种方式,可以给原有的Object加一些metaInfo,比如version。数据库最初的validate based algorithm,是这样,读的时候直接从全局数据里读(并且是同一个版本),写的时候写到事务本地的buffer里,提交的时候重新验证所有读过的信息是否在这个事务执行的过程中被更新了。TL2算法就属于此类。TL2算法在读一个全局数据的时候根本不用加锁,只需要一个tryLock。下次读的时候,先检查本地的read set。那么,比较一下,如果采用悲观锁呢(例如我以前在完美用的xdb)?读一个变量的时候,首先要加这个锁,拿不到就等着。逻辑很简单。从这点上来说,TL2这种乐观并发控制,相比于XDB那种老土的悲观并发模式,并不能提高性能。为什么?在首次载入一个变量的时候,乐观的(TL2)用tryLock,悲观的用lock,但是在没有冲突的时候,这两个的消耗是一样的啊!都是一个CAS。在NUMA系统上,都会逼迫CPU扔掉cache,强制刷store buffer。事务下次再读这个变量的时候,略有区别。multiverse需要在本地的readset里面先查一遍,如果查到就用,就不必tryLock了。对mutilverse而言,如果一个事务所用到的变量的个数是不一定的(大多数情况都是如此),它会用一个Hash Table来管理这些变量。于是每次openForRead都会需要做一次hash查找。这个hash table采用的是闭散列,在冲突发生的上下位置找一个空的。do { finalint offset = goLeft ? -jump : jump;…

我们哪里错了?

这不是一篇科普,这只是一篇对于从经典力学到狭义相对论的回顾。爱因斯坦是一个伟大的人,他的伟大不是因为他在实验室里通过做物理实验发现了什么牛B的现象,他的一切实验都是思想实验,他单单凭借大脑的空想,就建立了狭义相对论。现在我们来重新回顾这一历程,看看他哪里错了。先从牛顿说起。回想一下牛顿第一定律,中学物理老师整天特爱念叨这个,“任何不受力的物体都保持静止或匀速直线运动状态”。一个物体是静止还是运动的,取决我们站在哪看。比如你站在火车上看火车,火车就是静止的。你站在地面上看火车,它就是运动的。无论如何,只要它满足牛顿第一定律,就说我站的这个点(参考物),是惯性系。现在换个问题,如果我们站在火车里面,拉上窗帘,屏蔽所有声音和火车以外的信号。你能否知道火车现在是在走,还是到站停下来了呢?你扔个苹果笔直的扔上去,发现它还是笔直的落下来。你倒杯水,发现水流并不会倾斜。你不知道,你根本没办法知道。这个就是所谓的“力学相对性原理”。在惯性系内所做的任何物理实验,都无法告诉你,这个惯性系是静止的还是在做匀速直线运动。想知道,只有打开窗子看看外面。马哲老师一直在说:“运动是绝对的,静止是相对的。”可惜19世纪的物理学家们,缺乏这个常识,他们并非一生下来就得接受马克思主义教育。某天,他们发现了一个奇怪的现象,光波在真空中也能传输。亲爱的,你知道什么是波吗?你扔个石头到水里,水因为上下震荡所以才能产生水波。没有水,能有水波吗?没有空气,能有声波吗?没有人类,会有文艺复兴吗?不行,绝对不行。光波必须也得有个载体。为此,我们认为,真空的玻璃罩里也有东西,只是这种东西超出了我们现在的感知能力。这种东西必须是无处不在的,所以你在地球上的任何地方,制造一个真空,发现光线依然能在里面传输。这个不生不灭,没有质量,无处不在的东西,我们称为以太。这是一个完全空想出来的东西。好了,既然它弥漫了宇宙的每一个角落,我们可以认为它是静止的。于是我们可以把它当作坐标系,认为我们都是在相对于它运动。那么既然以太是静止的,光波是以太形成的波,那么光波在真空中的传输速度,必然是恒定的。这个速度是指光波针对以太来说。可是完了,地球是运动的啊?想这么一个实验:有一个正方形的房子,房子中央有一盏灯。我们现在打开灯,那么光线就会照亮四面墙。毫无疑问,光线肯定是相同的速度同时达到这四面墙。哦,可是不,这是在我看来。事实上,这个房…

JMX Server Behind Firewall

本来JMX用起来很简单mBeanServer = ManagementFactory.getPlatformMBeanServer(); Object obj=new MyMbean(); mBeanServer.registerMBean(obj, new ObjectName("com.tianshen:type=xiyou,name="+obj.getClass().getCanonicalName())); 但是JMX在远程使用的时候经常不大好使。JMX remote最基本的用法是,在启动的时候加上-Dcom.sun.management.jmxremote
-Dcom.sun.management.jmxremote.authenticate=true
-Dcom.sun.management.jmxremote.password.file=jmxpass
-Dcom.sun.management.jmxremote.port=13000
-Dcom.sun.management.jmxremote.ssl=false下面解释下com.sun.management.jmxremote.port这个东西。默认情况下,JMX协议是架构在RMI协议的基础上。那么RMI就需要一个位置定位服务,即rmiregistry 。rmiregistry 是一个类似于CORBA命令服务或者LDAP的东西。rmiregistry可以是一个单独的进程,带上端口号执行JDK/bin/rmiregistry即可。也可以是嵌入在当前的java进程中。而com.sun.management.jmxremote.port这个参数就是指,rmiregistry这个服务在哪个端口监听。然后,JMX Server会向这个rmiregistry注册自己。注册的时候需要提供一个主机地址和一个端口号。而这个端口号,默认是随机生成的。这个主机地址,常常很悲剧的是127.0.0.1或localhost。由于端口号是随机生的,这让系统管理员很为难。而且,如果那个主机地址是localhost……其实几年前在做mz项目的时候就遇到这个问题了,只不过今天又遇到了,拿出来分享下。MBeanServer的初始化代码得改成这样:finalint port1=14000; //the port number…

游戏中你能看见我不代表我能看见你

假设这是一款普通的2D游戏。屏幕被划成9个格子,一般来说人站在最中间那个格子。它能看见自己周围一圈这8个格子里的东西。上左我在这里右下如果如下两个假设成立,角色一定站在屏幕正中间。必须是正中心,丝毫不差。每个角色的视野的宽和高都是一样的(而不是像WOW那样可以让玩家自己调整)。那么,如果A能看见B,则B一定能看见A。所以,当一个角色上线的时候,只需要告诉它视野内的人即可。同理,这个角色的所有状态改变,如移动啊、下线啊、进入离开视野啊,也只需要按照它的视野来算。在我移动中,凡是有角色进入我的视野,我就应该告诉它,嘿,哥们,我出现了,我的横坐标是xxx,纵坐标是yyy,我在往哪哪哪走。视野广播,从来都不是为了发给我能看见的那些人,而是为了发给能看见我的人!其实很难保证这个人就是在正中心,因为如果人的位置是按像素坐标存的,那么他的视野未必恰好就是跨越整格子数。要么不是让人站正中心,而是让人所在的格子在正中心。要么就得把一些视野外的人也算进来。可是,可是!角色并非总是站在屏幕中间。当角色走到地图边缘附近的时候,有两种做法让角色依然站在屏幕中央。让超出地图边界的部分显示成黑色让地图边界与屏幕边界对齐。如果是后一种做法,请看下图:(0,0) 角色A(1,0)(2,0)(3,0)(0,1)(1,1)(2,1)(3,1)(0,2)(1,2)(2,2)角色B的终点(3,2)(0,3)(1,3)(2,3)(3,3)角色B的起点假设角色A站在地图的左上角,(0,0)位置。而另一个角色B从(3,3)往(2,2)走。那么当它走到(2,2)停下来的时候,它看不到A,所以不会告诉A说我进入你视野啦!所以A就看不见B。但实际上B却站在A的视野内。这会造成一种不可接受的现象:两个人约了在仓库门口交易,一个人(A)先到了,站在旁边的武器店挑选武器。另一个人接着(B)也到了。玩家B说: 我到了。邀请我交易。
玩家A说: 我也到了。你站哪的?
玩家B说: 我就站在仓库门口啊!有棵树这
玩家A说: 不对啊,仓库门口明明没有人啊!……把这个问题抽象出来,就是平面上有很多大小相等的矩形,给定一个点,问这个点在哪些矩形内?一般化一点,可能有的矩形大,比如人物视野,有些矩形小,比如npc的主动攻击范围。解决这个问题,最笨的办法就是把地图上所有的对象都去问一遍,嘿,我在你的视野范围内不?但是,假如地图上有1000人,就因…

坐标转换带来的阻碍判断出错

今天调试程序,发现人经常走到不可走的区域去了。我用的从直角到斜角的转换公式是:\( x’=x/2+y \)
\( y’=y-x/2+400 \)格子的边长30
起点斜角坐标(2370,13020),除以30得到(79,434)
终点斜角坐标(2370,13080),除以30得到(79,436)起点直角坐标(1350,1695)
终点直角坐标(1290,1725)
这两点在直角坐标下的距离是67.08203932499369
沿着这条线走2.24个像素。
于是得到直角坐标
1347.9964830921601
1696.0017584539198
取整得到
1347 1696
换算成斜角是
2369 13023
再除以格子的边长30,得到
78 434完蛋了。刚才是在x=79这条线上移动,但是现在跑到x=78这条线上去了。走到不可走的点,其实,也是正常的。区别在于寻路时候的依据。假如我现在站在中央格子,要向右上方走。障碍图如下(可走)(可走)(可走)(可走)(可走)(不可走)终点(可走)(可走)(可走)起点(可走)(可走)(可走)(可走)(可走)(可走)(可走)那么是否允许直接斜着走过去?还是必须先往右走再上去?如果按照前者来,那么就出现走到不可走点的情况。因为它可以先往某一个目的点走一点,使得它尽管依然在起点的格子内,但是不是在格子正中间,然后往斜上走。在走了几毫秒之后停下来。而在完美的时候,lch用的是很严格的判断必须正上和正右方的格子都可走,才允许往斜上走。

ID生成器

背景:网络游戏经常需要合服,所以角色ID最好不要重复,这样会降低合服的难度。另外,如果能做到物品id、角色id、npcid这些都不重复,那么更好。于是有人说,那你用UUID吧。但是,如果能根据这个id就能知道它到底是宠物还是角色还是物品,那么更好。注意:A、B合服后,要用A或者B的serverid。另一个废弃,新开服也不能用废弃的ID。(自以为这个比xdb的那套方法好。因为没有多余的表来存这个ID)/** * ID生成器。 <br /> * TODO: 把type用Integer.reverse这样的方式颠倒之后再存进去。那么当扩展typebits的时候,现在的数据依然可用。 * * @author cm * */publicclassIDGenerator{ privatevolatile AtomicLong[] nextValue; staticfinalint typebits = 3; staticfinalint serverbits = 12; staticfinalint valuebits = Long.SIZE - 1 - typebits - serverbits; privatestaticvolatile IDGenerator instance; privatevolatileint serverid = 0; publicvoidsetServerid(int serverid){ this.serverid = serverid; } publicstatic IDGenerator getInstance(){ if (instance == null) { synchronized (IDGenerator.class) { if (instance == null) instance = new IDGenerator(); } } return instance; } publicstaticinterfaceIType…

老老实实学数据结构与算法

最近2周,看了很多关于数据结构与算法的东西,老老实实写代码,不在weibo上和他们吐口水谈什么架构了。简述一下最近用到的东西。首先是一些基本的平面几何算法,比如某个平面区域内有很多点,然后在这个区域内画一个矩形,求这个矩形内有哪些点。然后发现做服务器端开发也是需要学图形学的,图形学的结果未必非要用在屏幕显示上。比如,假如服务器是按格子存储障碍点信息,那么给定两点,问这两点能否相互可见(直线可达),其实就是图形学最基本的划线算法。另外A*其实也蛮有意思。虽然算法本身看起来很简单,但是实现技巧很多。传说lch为了写这个算法并反复优化,写了至少有3个月。其中一个常见技巧就是不要用Set来存OpenList,而是用Heap。但是其实用Heap的时候也有细节上的不同,比如某个元素的值如果改变了,那么是remove并add呢,还是从它到根做一次调整呢,还是干脆不删除旧值,直接插入一个新的进去。第一种和第三种,不需要改现有的接口,用java.util下的优先队列就可以了,但是第二种需要自己重新写一下这个数据结构。multiverse 0.7中的collections基本处于不可用的状态,让我很郁闷很愤怒。所以接下来我和Peter会将之完善,并重写很多数据结构。解决问题最简单的方法就是蛮搜,所有可能性都试一遍,稍微聪明的程序员会考虑采用更较为合适的算法。但是,这个时候会发现选择往往不只有一个,而且最佳选择往往是依赖于数据集的规模,而不同算法在不同数据规模下的效率,这个知识的积累过程可比学懂并实现一个算法慢很多了也难多了,需要长期的经验和形式化分析的能力。更倒霉的是,需求的提出方往往估计不了市场的反应。AOI这个问题,我在想怎么更好。先想最基本的问题,对象移动以及视野广播。假如,每个角色的视野距离可以是不一样的,比如魔兽世界里面那样。那么我能看见你不代表你就能看见我。于是,当我的位置发生移动的时候,不能按照我的视野范围来做广播,而是看我到底是在哪些人的视野范围内。那么可以采用观察者模式,当对象移动位置的时候不断的register/unregister被观察者。这样才能保证被观察者突然下线或者发生某种行为的时候能及时被该看见的人都看见。但是我又在想,如果人很少,与其这样,还不如遍历整张地图所有角色来的快呢。用堆做A*的OpenList的时候,让我想到一个问题,就是,大多数搜索结构,可…

服务器端的游戏场景管理

最近在想怎么在服务器端组织游戏场景。服务器客户端地图位置同步的2种方式:1。服务器只存对象的当前位置。Client发来的消息分为两种:开始移动和定期同步。开始移动:目的点。定期同步:当前点和刚经过的关键点。服务器验证后把这个信息再广播给视野内的Client。role的位置改变是由客户端来触发的。视野内其它玩家的路径信息,可能是服务器转发的,也可能是客户端自己寻的。2。服务器保存对象的当前位置和行走路径。Client向服务器发它要走的路径。服务器把这部分信息merge到现在的行走路径中。然后定期根据路径刷新,并广播。我觉得2比1好,没有必要让客户端多发那个包。今天看到一个很不错文档,http://theory.stanford.edu/~amitp/GameProgramming/,让我大开眼界。一个很基本的问题,地图的阻挡信息如何表示?最简单的做法是地图画格子,每个格子要么是0,要么是1,代表可走与不可走,然后在格子上做A* 。另一种方式是,在上述的基础上,把阻挡以多边形的方式存储,那么寻出的路径的折点恰好就是多边形的顶点,但是貌似没见谁这么用,而且游戏里如果玩家真这么走,太别扭了。还有就是导航网格。UE3的文档中对这个有很详细的介绍:http://udn.epicgames.com/Three/NavigationMeshReference.html算AOE以及做视野内广播的时候也是,如果不是把对象划到格子里,按格子做广播,那么采用某个查找树比如红黑树就很不错。查找树因为是有序的方式组织数据,所以天然的支持范围查找,分别对x,y做两次范围查找就可以得到想要的结果,例如TreeMap\>>。最后一个Set是这个格子里的roleid列表。

斜投影(二):神马叫线性变换?

10点多刚下班,下班的路上我才发现我真是被他们给绕晕了。我原始的需求很简单,给定一个点(斜投影下的格子坐标),求它的视野(也要格子坐标)。这个人站在屏幕的正中心,但是屏幕的大小是平面直角坐标系的值啊,单位是像素。怎么办?我同事给我的算法是上文所写的,先把自己换成直角坐标,然后计算出屏幕边框的直角坐标值,然后换回去。其实呢,一眼就可以看出这是一个线性变换,因为它的变换规则可以用矩阵表示出来啊。那么,假设这个人的平面直角坐标是X,屏幕上某一点的坐标是X+b。那么根据线性变换,就有A(X+b)=AX+Ab。换句话说,直接算出Ab就行了啊!比如,屏幕的宽高分别是w、h,坐标原点在屏幕中心,那么屏幕右下角的坐标就是\( \left(
\begin{array}{ccc}
\frac{w}{2} \\
\frac{h}{2} \\
\end{array}
\right) \),因为\( A=\left(
\begin{array}{ccc}
\frac{1}{2} & 1 \\
-\frac{1}{2} & 1 \\
\end{array}
\right) \),所以\(Ab = (\frac{w}{4}+\frac{h}{2},-\frac{w}{4}+\frac{h}{2}) \),把人物的当前的格子坐标加上这个值就得了呗。就这么简单,我今天居然还拿笔从7点算到10点还算错了,然后写了一篇日志洋洋得意的以为自己终于把问题解决了。结论就是:工作就像开车,如果需要动脑子,千万不要疲劳驾驶。

斜投影

我这两天在研究diablo那样的投影方式。菱形的2个角一般是30度、120度。但是由于tan(30度)=sqrt(3)/3 约等于0.58,是一个无理数不利于计算,所以一般采用tan(x)=0.5的角,也就是26.5度。因为减少了误差,所以画出来没那么强的锯齿感。下面称新的坐标系为斜角坐标系。那么从直角坐标系到斜角坐标系是一个线性变换。根据前面的假设,设斜角坐标系的x轴和y轴在直角坐标系中分别是:y=x/2,y=-x/2;那么可推得从斜角坐标系到直角坐标系的变换矩阵为:$$$$ \begin{align} \left( \begin{array}{ccc} 1 & -1 \\
\frac{1}{2} & \frac{1}{2} \\ \end{array} \right) \end{align}$$$$ 求逆可得,从直角坐标系到斜角坐标系变换矩阵为:$$$$ \begin{align}
\left(
\begin{array}{ccc}
\frac{1}{2} & 1 \\ -\frac{1}{2} & 1 \\ \end{array} \right)
\end{align}$$$$假设地图采用菱形的格子,格子的边长在直角坐标系为m。屏幕的正中心恰好是某个菱形的正中心。假如一个玩家站在屏幕正中心,它在斜角坐标系下的格子坐标是(x,y)。那么它在平面坐标系下的值是(x-y)m,(x+y)m/2,那么屏幕正中心的值就是(x-y)m,(x+y)m/2+m/2。如果点P相对于屏幕中心的直角坐标是(a,b),那么它的坐标就是\( ( (x-y)m+a,\frac{(x+y)m}{2}+\frac{m}{2} +b )\),那么换算回去就是\( (mx+\frac{a+m}{2}+b,my-\frac{a-m}{2}+b) \),除以m换算回去是\( (x+ \frac{1}{2}+\frac{a+2b}{2m},y-\frac{1}{2}+\frac{2b-a}{2m}) \) 。用这个公式就可以算出屏幕4个角的格子值。不过我一直在怀疑是否应该补那半个格子。如果去掉那些二分之一,结果简单的很多。由直角坐标系到斜角坐标系变换矩阵可以推出,与x轴平行的线(比如屏幕上边线),转换成斜角坐标系后,都具有x+y=m这样…