Android开发性能篇--fork/join

在实际的开发过程中，大家都会注意到不在UI线程中去做IO或复杂业务处理，却往往忽视了在性能方面的优化。在Android开发过程中只是区分UI线程和非UI线程只能解决UI无响应（ANR）的问题，但是还是对程序或者某个业务模块的性能的提升却是了了，具体表现形式就是菊花时间长。之所以出现这种现象是因为我们在实际的开发过程中没有充分的利用现代CPU的多核心的特性，白白的浪费了处理器的性能，造成了这种一核有难，多核围观局面。

比如在一个大小为N（N>1000000）的集合中进行M次查找，常规解决方案可能就是下面的示例了：

public static long[] SOURCE = new long[MAX_LEN];
private static long[] KEY = new long[80];
static void normalSearch() {
        long startTime = System.currentTimeMillis();
        List<Integer> result = new ArrayList<>();
        for (long k : KEY) {
            for (int i = 0; i < SOURCE.length; i++) {
                if (SOURCE[i] == k) {
                    result.add(i);
                }
            }
        }
        System.out.println("\n耗时：" + (System.currentTimeMillis() - startTime));
        result.sort(Comparator.comparingInt((i) -> i));
        for (Integer integer : result) {
            System.out.print(integer + ",");
        }
    }

public static void main(String[] args) {
        //生成随机数
        for (int i = 0; i < SOURCE.length; i++) {
            SOURCE[i] = (long) (Math.random() * MAX_LEN);
        }
        //生成带查找的随机key
        for (int i = 0; i < KEY.length; i++) {
            KEY[i] = (long) (Math.random() * MAX_LEN);
        }
        System.out.println("可用CUP核心数目：" + Runtime.getRuntime().availableProcessors());
        normalSearch();
    }

运行结果如下：

可用CUP核心数目：8
耗时：1595
119661,337105,401423,420279,582259,833772,915289,1220176,1362115,1385498,1407456,1410458,1412537,1486334,1672986,1674490,1856904,1897285,2102246,2252358,2346380,2432449,2682087,2912521,3092778,3264722,3357749,3608071,3689355,3734622,3744433,4125270,4234587,4281248,4314317,4341244,4436954,4677349,4753986,4813957,4910578,4958269,5015601,5080880,5180586,5300020,5364204,5631064,5756371,5878736,5996476,6036646,6066038,6297594,6393639,6408677,6415918,6664395,6858922,7025579,7297229,7705758,7815756,7913880,7940796,7971198,8160302,8187878,8258721,8273061,8478081,8584189,8616914,8650043,8695414,8815420,8985573,9039380,9079216,9226196,9304474,9422083,9465702,9545556,9741503,9770754,9848830,

如果说这是在一个8核心CPU机器上那有7个核心的CPU被浪费了，现在Android设备的CPU基本都是4核心起步，如果程序全部使用上述方案去设计实现那程序的性能就被认为的设置了瓶颈。既然发现了问题，那就想解决方案，解决方案也很容易想到那就是使用多线程，将查找业务拆分成多个子任务然后分别放到独立的线程中执行，最终将所有自任务的执行结果汇总起来。从Java 7开始JDK添加了分支/合并(fork/join) Api，我们除了可以使用传统的线程（Thread | Runnable）去实现并行计算外还可以用 fork/join api去实现而且更方便。这里我们将整个查找任务按照20个每组的策略拆成四个子任务（这里可以根据当前设备的CPU核心数量作为任务拆分数量的依据，达到充分利用CPU资源的目的）分别在各自的线程中运行，最终将子任务的结果汇总生成最终结果。

实现方案如下：

static class SearchTask extends RecursiveTask<List<Integer>> {
        private static final int SLOP = 80 / 4;
        private long[] data;

        public SearchTask(long[] data) {
            this.data = data;
        }

        @Override
        protected List<Integer> compute() {
            if (data.length <= SLOP) {
                return doSearch(data);
            }
            ForkJoinTask<List<Integer>> fork = new SearchTask(Arrays.copyOfRange(data, SLOP, data.length)).fork();
            List<Integer> result = new SearchTask(Arrays.copyOf(data, SLOP)).compute();
            result.addAll(fork.join());
            return result;
        }

        private List<Integer> doSearch(long[] ds) {
            List<Integer> result = new ArrayList<>();

            for (long d : ds) {
                for (int i = 0; i < SOURCE.length; i++) {
                    if (d == SOURCE[i]) {
                        result.add(i);
                    }
                }
            }
            return result;
        }
    }//end SearchTask

static void parallelSearch() {
        long startTime = System.currentTimeMillis();
        List<Integer> result = new ForkJoinPool().invoke(new SearchTask(KEY));
        System.out.println("\n耗时：" + (System.currentTimeMillis() - startTime));

        result.sort(Comparator.comparingInt((i) -> i));
        for (Integer integer : result) {
            System.out.print(integer + ",");
        }
    }

public static void main(String[] args) {
        //生成随机数
        for (int i = 0; i < SOURCE.length; i++) {
            SOURCE[i] = (long) (Math.random() * MAX_LEN);
        }

        //生成带查找的随机key
        for (int i = 0; i < KEY.length; i++) {
            KEY[i] = (long) (Math.random() * MAX_LEN);
        }
        System.out.println("可用CUP核心数目：" + Runtime.getRuntime().availableProcessors());
        parallelSearch();
    }

运行结果如下：

可用CUP核心数目：8
耗时：229
190450,518321,519536,667571,1026180,1236306,1275936,1374522,1393754,1576010,1616249,1616646,1875229,1885370,2023697,2039008,2098160,2156943,2293885,2386163,2512508,2633884,2844610,3008867,3172781,3260755,3289703,3306916,3617237,3926288,4029758,4100177,4308783,4427440,4571876,4737692,4937399,4998991,5039259,5042379,5085831,5210899,5331303,5358580,5389430,5714091,5742347,5847322,6005706,6050434,6616903,6879677,7169505,7229141,7248784,7318644,7536698,7605990,7656189,8110381,8126203,8142227,8366379,8426563,8496790,8552683,8584329,8671821,8713540,8991753,9005534,9123005,9197396,9206506,9268363,9472202,9515304,9541788,9669959,9679572,
Process finished with exit code 0

从结果可以看出使用多任务拆分策略后程序的执行性能得到了大幅的提升，但是并不是在所有的场景下使用任务拆分都能提高性能，我整理了一份表格如下：

M	线程数量	N	执行时间（串行）/ms	执行时间（并行）/ms
80	4	1000	2	4
80	4	10000	6	16
80	4	100000	30	30
80	4	1000000	173	50
80	4	10000000	1579	229

通过上表结果，我们可以得出结论在保持查找次数M和拆分任务数量不变的情况下，查找集合N越大性能提升越明显，因为任务线程的切换和同步也是需要耗费时间的，当查找任务比较小（N比较小的情况下）使用任务拆分的策略并不能带来性能的提升，反而会是性能下降，所以在使用的时候需要特别注意。