【IT168 专稿】
众所周知，硬件公司正在放弃追求单个CPU速度的竞赛，取而代之的是主要把精力集中在多核处理上。尽管许多的算法能够很容易实现并行化，但是大多数的客户端的Java代码仍旧是为单个CPU系统而编写的。这些篇文章中，演示了在单核的情况下，如何调整数组排序的算法，来提高多大30%的速度。
多年来一直在增加单个CPU的处理速度方面受到了瓶颈，开发者不得不在服务器端想办法已经有最少十年了。但是现在通过在客户端编程设计来提高程序运行速度成为现实。通过使用JDK 6.0的新特征，就可以让它们能够并行化，让客户端应用程序利用多核处理器的优势。以使用单核JDK数组排序算法为例，这篇文章略述实现细节，重点讲解并行算法。在双核的机器上，即使一个简单的实现结果能够加速35%。
摩尔定律失效
摩尔定律失效
知道一两年前，API提供商能够简单的依靠一个经验观测值做出判断，这个经验观测值是由Gordon Moore在1965始创的，他是Intel创始人之一。摩尔定律指出每18到24个月集成电路上的晶体管的数量至少要翻一番。对于软件开发者来说，这就意味着你写了一个程序，当时运行在一个单核CPU上，过年两年后，你的这个相同的程序运行在两年后的单核CPU上速度肯定会快两倍。只要操作系统向后兼容的话，你甚至不需要编译你的程序。
但是，在最近两年，硬件制造商开始找到产品的瓶颈了，不去非常费成本的提供单个芯片的计算能力。他们的解决方案就是首先就是服务器市场和客户端市场，在同一个芯片上放置多个处理器，并不是去增加每个处理器的处理速度。对于软件世界来说，这就意味着你不能“坐享其成，与己无关”了。如果你的程序有一个简单的顺序流程，那么就不能享受底层多核硬件带来的优点了。这个道理同样适用于你正在写的那些程序和一些语言的核心语言库。
单核CPU情况下的集合排序
现存的Java集合排序例行程序没有异常。它们运行在一个新的多核机器上并不比一个单核机器上快。对于输入数据少的情况，这似乎是可以接受的，但是大多数现实世界的问题所需要的数据很大，那么这就是不能忍受的。另外，开发者和用户都希望他们的程序能够在新的硬件上运行得更快。
看看那些操作集合的一般算法，和现有的Java实现，将会澄清这个问题，并且会指明一条找到正确解决方案的道路。
算法的复杂度
大多数操作集合的核心算法都能在Arrays 和Collections 类中找到。使用这两个类中的API，你可以你可以对list和array排序，查找，填充。因为大多数的API操作整个集合的内容，整个运行时间和集合的大小成比例。
对于一些方法(如排序)，运行时间甚至更长。你不能在数步之内排序一个任意的集合，它是和集合的大小成比例的。这通常就称为线性复杂度。如果集合的大小是N，对这个集合进行排序的最好算法所需要的步骤数与N*log(N)成比例；这个下界被理论证明过。(注：对于冒泡排序所需要的步骤数与N*N成比例，这对于大的集合来说，是非常不适合的。)
对于一些方法(如排序)，运行时间甚至更长。你不能在数步之内排序一个任意的集合，它是和集合的大小成比例的。这通常就称为线性复杂度。如果集合的大小是N，对这个集合进行排序的最好算法所需要的步骤数与N*log(N)成比例；这个下界被理论证明过。(注：对于冒泡排序所需要的步骤数与N*N成比例，这对于大的集合来说，是非常不适合的。)
Java实现排序算法
查看Array 和Collection类中的各种的排序算法现在很容易，因为有他们都有开源许可证。Array中的所有排序例程都是使用快速排序法操作基本类型（如byte, char, double），快速排序通常被认为是最快的排序算法。（在很少的情况下，快速排序的性能下降到平方的程度。）操作对象数组的排序API使用的是归并排序，这种方法实现起来更为简单，而且性能也能达到N*log(N)的级别。最终，对于调用Collections.sort(List)，实际上是用Arrays.sort(Object[])来排序。
在进一步查看Array类中的归并排序，你可以看到它实际上是针对几个少数情况，对经典的归并排序做了几个优化。如果你的数组规模很小，它就退回到使用冒泡排序。否则，就是使用归并排序。
回到硬件发展，你可以轻松看到CPU增加的速度，改进了算法运行的时间。由于归并算法是一个顺序递归算法，有着完全一样的顺序步骤，提供相同的输入。
多核环境的排序
当运行在一个多核的机器上时，现存的归并排序实现会有什么问题了？答案很简单：他不能对递归实现并行操作。当你的数组一分为二是，对第二个数组的排序是在第一个数组排序完成之后才开始的。但是新的JDK 6.0的出现解决了这个问题，能够让你并行的执行这些子任务，而不用它们之间的互相通信。最终，当两个任务都完成了，排序好了的两个数组仍旧需要合并在一起。它的复杂度仍然是N*log(N)，但是这一次的具有更低的不变因子。为了证明是如何低的，我将给你展示一个简单的归并排序的例子，利用多核的优点。这将带你进入并行程序设计的世界。
并行程序设计解决方案
下面将要演示的代码示例是基于核心JDK实现（通过GPL认证）基础之上的。第一步，如清单1所示，为了检查可用的处理器的数量。如果只有一个处理器的化，并行化的实现什么也不操作，你将为创建线程付出额外的开销。
清单1：输入规模小，并且是单处理器的特殊情况
if ((a.length < 7) || (Runtime.getRuntime().availableProcessors() == 1)) { mergeSort(aux, a, 0, a.length, 0); return; }
接下来你需要决定如何分配可用处理器的工作。为了简化实现的过程，我将只是在两个处理器之间划分工作。你很容易看到最终的合并阶段可以在两个一分为二的数组排序完成后进行。清单2使用了JDK 6.0中新的并行功能：
1. CountDownLatch类让你等待一个具体数目的、完成的任务（本例中是2）
2. Executors.newFixedThreadPool 运行两个排序线程
1. CountDownLatch类让你等待一个具体数目的、完成的任务（本例中是2）
2. Executors.newFixedThreadPool 运行两个排序线程
清单2：将一个排序分为两个单独而且并发的排序
final CountDownLatch doneSignal = new CountDownLatch(2); ExecutorService e = Executors.newFixedThreadPool(2); class WorkerRunnable implements Runnable { int start; int end; WorkerRunnable(int start, int end) { this.start = start; this.end = end; } public void run() { mergeSort(aux, a, start, end, 0); doneSignal.countDown(); } } int mid = a.length >> 1; e.execute(new WorkerRunnable(0, mid)); e.execute(new WorkerRunnable(mid, a.length)); try { doneSignal.await(); // wait for all to finish } catch (InterruptedException ie) { } e.shutdown();
待CountDownLatch.await返回结果，你就知道两个子任务都已经完成了。此时，你就可以合并排序好了的两个子数组，如清单3所示。
清单3：合并两个排序完成的字数组
System.arraycopy(a, 0, aux, 0, a.length); // merge two halves for (int i = 0, p = 0, q = mid; i < a.length; i++) { if (q >= a.length || p < mid && ((Comparable) aux[p]).compareTo(aux[q]) <= 0) a[i] = aux[p++]; else a[i] = aux[q++];
多核机器上性能结果
本文实例包括了下面的Java类：
1. CoreSort 测试核心实现Arrays.sort()。
2. ConcurrentSort是对相同方法的一个简单的并行化实现，这个方法利用了多核CPU的优点。
3. TestConcurrentSort测试了在不同的输入情况下并行化排序实现结果。
1. CoreSort 测试核心实现Arrays.sort()。
2. ConcurrentSort是对相同方法的一个简单的并行化实现，这个方法利用了多核CPU的优点。
3. TestConcurrentSort测试了在不同的输入情况下并行化排序实现结果。
下面的结构是在多核Intel处理器上得到的，每个核的运行频率在1.66Ghz。使用并行化版本，核心的Arrays.sort方法来对数组进行排序，这个数组随机产生了百万个字符串。没有做并行化处理平均运行时间是3350ms，进行并行化处理的运行时间是2180ms(提高了35%).
在理想的情况下，性能的提高幅度可以达到50%。但是，由于一些原因，你几乎能达到这个效果。首先，创建和运行多线程就会引起一些“消耗”。第二，大多数问题涉及到一些“归并”阶段，延误一些时间。第三，子任务之间还需要通信。
这容易吗？
那么，这样做容易吗？没有定论。如果是固有的并发操作，那么问题就很简单了，你只需要使用JDK 6.0 并发API，写几行代码就可以完成。但是，如果你的代码是给规模不固定，任意数量的处理器的话，那么你的代码就不是很容易了，这样一来你的代码有可以用到摩尔定律了(只要硬件开发商保持在自己的芯片上安装更多的核)。
另外一方面，你现在并行程序设计的时候面临多方面的选择。首先，你需要决定如何将你的任务放在所有的处理器上，还是其中的一部分，或者只是一个固定的数量上。将任务分布在所有的处理上会获得一个不错的运行时间，但是实施起来会很复杂，并且在某些情况下(当一个核负载很大的时候)，一个具体的子任务会比其它的任务花更长的时间。如果将一个任务分散在一个固定数量的核上，性能提高度就只是一个常数了，无论你有多少个可用的核。
第二，你的测试会变得越来越复杂。你需要测试你的代码在不同的配置条件下，包括单核，双核，四核等等。一些Bug变得很难复现出来。
第三，代码本身变得更加复杂，并且不仅仅是因为任务的细分导致的。你还需要考虑系统资源；你的方法或许要被多个线程调用。并且如果你使用了较多的线程，很容易导致系统死机。
最后，但是当然不是最不重要的，有一些问题并不是很轻易的就可以实现并行化的。举个例子，ArrayList.indexOf。这个方法非常简单，扫描整个数组，返回符合传入参数的第一个元素。这个任务很容易的拆分到任何的可用处理器上，每一个去查找自己的范围。但是这个方法和Arrays.sort的主要区别就是合并阶段。在indexOf方法，你需要返回第一个匹配元素的索引。但是如果子任务操作的第一个区域找到了匹配的元素，那么在ArrayList.indexOf的例子中，所有其它的子任务使用的处理器就没有什么意义了。
ArrayList.indexOf方法，不像Arrays.sort，它们不需要所有子任务的全部结果。如果不止一个子任务返回非负的结果，那么就应该最小的那个。想想你把一个查找任务拆分成四个子任务，并且第三那个子任务返回了匹配的索引。你不能停止剩余的子任务和返回的结果，只能不需等等，直到前面两个子任务完成，就是为了决定结果是什么。在这个具体的例子中，当一个子任务N返回了一个匹配的结果，你能停止所有的任务N以后的任务，但是你要等待N以前的任务的执行。
结论
多核的硬件用来进行客户端的开发已经成为现实了。对于那些在现有硬件伸缩行不是很好的硬件将不会采用。但是，并行化处理可以让你的代码享受多核硬件所有带来的优点。但是，这就意味你要将你旧的思维习惯从顺序模式转变到并行模式。并行模式不仅是提高性能，它也能带来自身的最优方法。如果你想让你应用程序性能拥有更强的竞争力，具有更大的伸缩性的话，你应该加入到并行化的阵营来。
