西西河

主题:【原创】一个游戏引发的无血案 -- Highway

共:💬45 🌺54
分页树展主题 · 全看首页 上页
/ 3
下页 末页
  • 家园 【原创】一个游戏引发的无血案

    【案情背景】

    前些日子在河里瞎逛,看到一个面壁朋友问一个小小的问题,就是有没有什么简单的算法来可以解出4张扑克牌用加减乘除拼出24的方案。这其实是一个小孩子们玩的口算游戏,我小时候也常玩儿。于是乎就冒出一个想法,写一个程序让计算机算出所有可能的解决方案来。

    有人说了,你是不是吃饱了撑的没事干了,写这破玩艺儿干什么,又不能当钱花?唉,没办法,这可能就是当程序员老落下的职业病吧。据说鞋匠跟人握手的时候会盯着人家的鞋子,刽子手和人家拥抱的时候都情不自禁的打量人家的后脖梗子。程序员做久了,什么事都想写段code来算算,没办法,手就是这么

    【一.小试牛刀】

    一开始,只想验证一下自己的想法,于是乎就来了个短平快,几下子搞出了一个雏形,踹了两把,Work(一开始有个小bug,被网友们发现了)。哈哈,比较得意。

    问题是面壁朋友呢想问我要程序代码,这下子麻烦来了。这个雏形走的是quick-and-dirty路线,程序丑陋的很,见不得人的。并且自己也清楚,这个雏形程序有两处硬伤,一是不灵活,不能玩其他张数的游戏(比如5张牌),另外程序基于string replacement,效率极低。和人玩可能感觉不出来,但是运算量一大,问题就暴露出来了。比如有的朋友说,你能不能把扑克牌所有的组合过一次,看看什么情况下无解。我试着算了一下,大概要7分半钟。是不是太说不过去了,Core 2 Duo的电脑算几张扑克牌居然要一袋烟的功夫,way too slow!!!

    【二.鸟枪换炮】

    于是乎,开始修正程序的dirty部分,希望能使得程序变得quick。要解决的问题有两个,一个算法要generic,二是效率要高。

    一段时间之后,第二版游戏出笼了。这个版本解决了上述的两个问题。玩家可以制定扑克牌张数(以及允许增减运算方法和最后的结果数值),另外String replacement的算法被删除了,改成了native加减乘除。这一下,效率提高近10倍左右。现在把所有组合算一套下来,只需要50秒不到。哇噻!!!。

    为了show off一把 ,在做整套扑克牌计算的时候,我使用了多线程,好让计算机的两个“核”都忙起来了,要不买dual core计算机干什么。粗粗一弄,程序提高到了28秒左右, 嗯,爽!

    【三.大事不好】

    修改后的code第二天带到了公司,准备再把几个细节修改一下就算是大功告成了。很快的问题搞定了。看起来天空晴朗,万里无云。但是没曾想到问题马上就出现了。

    新的code单线程运行的时候一切顺利,CPU利用率饱和在50%上面。注意这个小程序是计算密集型的,没有IO或是其它操作。在双CPU(two logic CPU,可以是P4的Hyper-thread,或是dual core, dual socket)的计算机上,CPU的利用率应该是100%左右,也就是全饱和状态。问题就出在了多线程上。一进入多线程状态,CPU利用率不但没有上升,反而下降了,在10-40%之间徘徊。CPU不给出力干活,性能自然就好不了。使用多线程性能下降了近2倍左右。嘿。乖乖!

    一看在JDK 5.0平台上不行,我马上切换到了新的JDK 6.0平台上。猛一看,情况喜人,两个CPU都忙活了起来,CPU利用率在95-100%之间徜徉。但问题很快就显示出来了,CPU这么忙活,性能却提高有限,比单个线程只提高了10%左右。呃,这就怪了,CPU利用率从50%上升到了100%,但怎么就出力部出活呢。CPU都忙活什么去了?

    我在Pentium 4 Hyper-thread的计算机上,Pentium D(双核)的计算机上做测试,现象惊人的相识。难道是 Windows XP扩展性有问题?不对啊,这也不是头一回在XP机器上使用多线程了。

    我将程序上载到了Linux(Red Hat)的服务器上。在两个CPU (两个AMD Opetron 250) 的服务器以及8个CPU的服务器上(8个AMD Opetron 850),情况一样。JVM 5.0在多线程情况下性能大幅下降(程度比windows要好一些),在JVM 6.0平台下,性能只提高10-25%左右。

    TNND,邪乎了!

    【四.峰回路转】

    老革命遇到了新问题,怎么办?

    晚上回了家,拎着啤酒瓶子开始默默思考。。。

    闲言少叙,经过好一阵子的struggle,问题开始明朗了。白天在单位清理code的时候,为了使double的数字输出美观一些(比如说4/7就会产生一个很长的double),我使用了DecimalFormat类,大概是这样的code

    public static final NumberFormat NF = new DecimalFormat("0.00");

    问题就出在了这里。这个类不是我想象的stateless的那种utility class,它是一个Stateful class.我这样的语句使得它成了整个程序的瓶颈(static,只有一个instance)。我估计这个程序在某个地方使用了synchronized的程序段,这就造成了多个线程争抢一个lock的局面。

    那为什么在JVM 5.0和6.0平台上,CPU利用率以及性能会出现那样的怪现象呢?

    我初步推断,问题大概是这样的。

    1)JVM 5.0的synchronization机制是传统的“进入或者休息等待” 模式。就是说如果一个线程抢到了lock,它进入critical section,开始执行相应的操作,完成后,释放lock。那么没有抢到lock的线程呢,进入休息等待状态(wait)。其它线程释放了lock以后,它会被notify,重新进入运行状态,再次试着抢lock。在现代计算机里,进入等待状态以及再度激活是一个相当昂贵的操作,会浪费几百个CPU cycle.由于程序中有一个被频繁争抢的lock。这造成了线程大多的时间花费在了“休息—〉激活”的状态切换上,真正执行程序的时间反倒成了少数。于是乎,CPU没有能被很好的利用了起来,这造成了性能的大幅下降。

    2)JVM 6.0的synchronization机制有较大改进。其中一个feature叫做spinlock。当一个线程拿不到lock的时候,它不是马上转换到等待状态,而是不离开CPU, “原地打转”。转几圈以后,在回头去抢lock。这就是以前人们所说的Busy waiting。 在以前,Busy Waiting是“坏东西”,是要避免地。但是在当前的软件硬件情况下,先spin一阵子,再试着抢几次lock,不行再转入等待状态效果更好。由于busy waiting的thread不释放CPU,所以CPU利用率居高不下。但是这其中有很多cycle是在“打转儿”,并不出活儿。所以我们就看到了CPU利用率从50%提升到100%,而性能只提升15%-20%左右的现象。原因就在于很多CPU时间是花在了spin上。

    找到了问题事情就好办了。我先是写了一个小函数来处理double变成string时的长度问题,替代了那个DecimalFormat类。这样,程序的瓶颈消除了,多线程的威力开始显现。第二天带到公司在各个平台上测试了一圈 ,一切如所想。

    点看全图

    外链图片需谨慎,可能会被源头改

    点看全图

    外链图片需谨慎,可能会被源头改

    (注:数值代表的是完成测试所需要的时间。越小越好。测试是对扑克牌所有组合进行穷尽计算。一次穷尽计算大概1-2秒,我将游戏值从12算到36,算24遍。大概40-50秒。这样计算量购大,时间又不至于太长)

    在测试的时候,我突然发现程序里面有好多操作是重复的,完全可以一次性 搞定。另外表达式生成部分算法还有提高的余地。于是乎,对程序再次下手。这一次搞下来,性能又大幅飙升。一套扑克计算下来只需要区区不到俩秒钟,和最初的7分半简直是判若云泥。

    到这里,不知不觉地有些飘飘然,对自己的敬仰之情油然而生,牛人就是牛人,没办法!

    【五.风云再起】

    在单位改好的code被带到了家里,准备在家里的Core 2 Duo计算机上跑几趟。看看在XP,Vista,以及在Windows 2003 Server平台上成绩如何。你猜怎么着,在单位久经考验的程序回了家居然不好使了。注意我带回的是编译好的jar文件,100%原版。在家里,JVM 6.0的环境里,多线程性能有提升,但只 提高了50%左右,这和我期望的80-90%的有很大出入。在JVM 5.0环境里,性能下降的问题又出现了。

    是不是我把jar文件搞错了?我马上remote login到公司,把这个jar文件放到公司的计算机上现run一遍,和白天的情形一样,在双核的p4上多线程还是比单线程快90%以上,而在JVM 5.0环境里也不出现性能下降的问题。

    难道是遇到了鬼不成?

    无奈,我只好用jconsole来跟踪JVM,看看什么地方堵住了。可惜现在的Java监控程序还不能给出我想要的细节,我只能从有限的信息中展开想象。

    点看全图

    外链图片需谨慎,可能会被源头改

    同样的软件,在公司运行的时候,非常smooth.Total blocked and Total waited number都非常小。这说明线程之间没有相互协调造成的overhead,各个线程几乎是独立运行的。而在家里的计算机里,这两个数字出奇的高,尤其是在JVM 5.0环境下。一样的OS,一样的JVM,一样的程序,怎么会有如此迥异的情形,真是匪夷所思!

    我做了N种尝试,最后把新型的for(int[] pokes : Set<int[])的循环改成了老式的(for int i=0; i< array.length; i++),把share的东西全部全部作了独自占有(虽然是只读的数据),这些尝试在JVM 6.0中能看到效果(性能又有一些提高,多线程的scalability也从50%提高到了85%左右)。但问题是在JVM 5.0环境下性能下降的问题依然故我。更奇怪的是同样的code ,同样的JVM 5.0,如果我的操作系统是Windows 2003 Server,下降问题就消失了。但问题是多线程的性能提高却只有36%左右,和理想值想去甚远。

    Damn it, I had enough!

    到这里,我老人家准备洗手不干了。但就在这时候,事情又有了转机。我clean了一遍code,删除了一些comments,改改format什么的,JVM 5.0好像突然间变好了一样。性能不再下降了,在XP和Vista平台上,也居然能有50%提高。不过一Reboot machine, 问题有出现了。TLLD,这不是逗我玩吗?我老人家这下是彻底晕菜了。。。

    【六.草草结案】

    自认为在多线程问题上有几年功力,但这次这个小程序搞得我有些灰头土脸。当然我有不当的地方,但是Java本身也确实还不够完美。有很多问题我认为是它具体实现上的问题。不过呢,JDK 6.0要好很多,不仅所有的测试要比5.0快一些,而且似乎更可靠一些,更“makes sense”。所以呢,建议大家尽早升级到6.0上来。

    Linux平台上的Java扩展性能相当稳定,不过不知道这是Linux的功劳,而是AMD Opetron结构优势的体现。我没有在相同的AMD平台上测试Windows的表现,所以不好下结论。

    Core 2 Duo确实优秀。2.13GHz的E6400几乎比所有的处理器都快,所以大家如果购买计算机,我认为这是首选。

    另外就游戏本身而言,我认为4张扑克牌算24是个比较折中的方案。4张牌,加减乘除口算可以基本解决。不过呢,算24无解的情况比较多,如果改为2那么无解情况就会极大地减少。可能那样玩起来不够劲,2看起来太简单了一些。5张牌口算可能还能勉强应付,6张牌我想一般人就handle不了了。没个计算器什么的估计是不好解决。不信,你用4,5,6,7,8,9给我算个5188(吾要发发)出来。计算机都得算个好几秒钟呢。如果是玩8张牌的游戏,计算机都够呛,没个几个钟头是搞不定的。所以说别小看这些排列组合问题。搞基因蛋白质的,动辄要上万台计算机上千个小时的计算,问题和这个异曲同工。据说这个领域已经变成了计算最密集的行业,需求不可思议的巨大。

    不早了,水就先灌到这里吧!

    元宝推荐:四月一日,铁手,
    • 家园 给您老大送花竟然得了个宝!呵呵

      传统的通信行业,从底层到应用层都有严格的规范,特别是利用概率统计几近完美地概括表达了很多复杂的物理意义。不过我对计算机行业有些纳闷,很多应用软件的开发与开发平台、CPU、操作系统都是息息相关,但是作为计算机行业的一般从业者很难探究其中的关系。您老兄做的这个测试已经达到了功能测试(黑盒)的目的,同时,您也还做了白盒测试,自己还更正优化了代码,同时比对了相关的平台,包括同一平台不同版本的运行效果,这个工作确实很好,真牛!不过对平台、操作系统、CPU中很多原理性的东东没法表述清楚,但是这也太为难您老大了,既要搞应用算法,又要关注应用平台的效能,估计有您这样水平的中国程序员也不多,毕竟大家没条件深入研究intel、MS这些内部的原理架构。

      • 家园 关于这个我想说两句

        其实计算机行业,最令人困扰的问题并非对机器的性能利用不够,而是如何大规模标准化的生产软件。就是说最好大家都写非常格式化的八股文。说到底,在大多数应用中,机器的计算能力是充足的,而花钱让程序员写代码,对代码进行维护,则成本高得多。一般来说,追求性能的代价往往是增加了开发周期,牺牲了程序的可读性,这是不合算的。更麻烦的是,当最初写程序的人离开后,接手的人可能需要极大的精力来理解前人的思路。所以在这个意义下,程序能给人看懂要比能非常好的利用机器性能来说,重要得多的多。

    • 家园 牛,花
    • 家园 偶是来参观无血案滴~~
    • 家园 花花牛啊

      真是大牛

    • 家园 长见识。
    • 家园 景仰一下

      七分钟就很好了,搞成两秒钟真是没必要

      • 家园 哈哈,highway、泰让兄快来看上帝!

        哈,雪个兄,开个玩笑别生气啊。俺当年交的一个加密算法(10M文件,指定CPU),大于4秒就不及格。俺编得昏天黑地,从2.3秒降到了1.8秒。后来助教给出了他的算法:0.23秒!哎,人与人的差别咋就芥末大涅!

        另外,俺前几天看李卫当官,有一集的牌匾◎江苏按察院◎不错,还有一集康熙背后的屏风上楷书,不知是谁的法帖,如果兄台愿意,改天切下来请教。

分页树展主题 · 全看首页 上页
/ 3
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河