1【原创】一个游戏引发的无血案 41 Highway 2007-03-04 23:53:16
【案情背景】

前些日子在河里瞎逛，看到一个面壁朋友问一个小小的问题，就是有没有什么简单的算法来可以解出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张牌的游戏，计算机都够呛，没个几个钟头是搞不定的。所以说别小看这些排列组合问题。搞基因蛋白质的，动辄要上万台计算机上千个小时的计算，问题和这个异曲同工。据说这个领域已经变成了计算最密集的行业，需求不可思议的巨大。

不早了，水就先灌到这里吧！


请尽量 选转。四月一日 荐,铁手 荐,最后于2007-03-05 08:05:47改,共5次;

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

3关于这个我想说两句 泰让 2007-03-09 07:44:37

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

4here is something interesting flyfeather 2007-03-09 12:27:24
http://www.geocities.com/tablizer/top.htm

链接出处

最后于2007-03-09 12:41:49改,共2次;

2牛，花 黄有财 2007-03-07 09:55:47

2偶是来参观无血案滴~~ lily 2007-03-07 02:14:34

2花花牛啊 戴某来自泉韵 2007-03-06 18:55:15
真是大牛

2长见识。 小愚 2007-03-06 16:22:58

2景仰一下 雪个 2007-03-06 14:06:42

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

3哈哈，highway、泰让兄快来看上帝！ 1 面壁 2007-03-06 15:36:34
哈，雪个兄，开个玩笑别生气啊。俺当年交的一个加密算法（10M文件，指定CPU），大于4秒就不及格。俺编得昏天黑地，从2.3秒降到了1.8秒。后来助教给出了他的算法：0.23秒！哎，人与人的差别咋就芥末大涅！

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

4书法我的不灵，不过河里可能有灵的 雪个 2007-03-06 18:03:42

你若喜欢，只管切，大家也好一同欣赏。大不了没人知道答案

5请教怎样发RM格式文件 面壁 2007-03-07 13:31:43
我切下来一个5M，一个不到1M，不知怎么发上来。要不你给我短信里发个Email，让你帮忙贴贴？

6可以传到google空间。 雪个 2007-03-07 17:09:11

4是同样的加密算法，不同实现，还是算法不同？ 小愚 2007-03-06 16:22:02
如果算法不同，还要比较加密效果吧..

5应该是算法不同 面壁 2007-03-07 13:27:22
应该是算法不同。10M文件读取，加密后输出10M。类似外排序，这些对于计算机专业的不算问题，对于俺，就成问题了。

3回仰一下，哈哈！太傅可是这里的稀客啊!!! 1 Highway 2007-03-06 15:27:35
这两天突然过敏了起来。流眼泪，打喷嚏，鼻子跟水龙头似的，难受的一塌糊涂。下午看了大夫，领到了强效Drug(毒品？)，现在好像似乎好了那么一点。

4这么早啊？ 雪个 2007-03-06 17:59:37

好像花粉多的季节还没到呢。据说反应大的人到最后要打针，真可怜呀。我现在还没过敏，据说也是七年之痒？那也快了。。。

3风花雪月和二进制的区别啊！ 1 请尽量 2007-03-06 15:10:33