Android 应用性能优化（三） 多核下的多线程计算

    多核的处理器不同于单核处理器，可以同时执行多个线程。可以说，在理论上双核的处理器的性能是单核的两倍，基本上我们一般不用操心这个设备到底是多核还是单核的，因为使用Thread或者AsyTask将工作分派给不同线程就足够了。如果处理器是多核的，那这些线程就会运行在不同的核心上，但是可能有的时候要最有效的使用CPU来获得可接受的性能，要特别为多核定制算法。

    以下实现做的事情：

    1.将原问题划分成多个更简单的子问题

    2.然后将子问题的结果合并处理，算出原问题的解（使用Future和ExcecutorService）

    3.成功避免了重复计算很多相同的斐波那契数（使用高并发高吞吐并且线程安全的ConcurrentHashMap作为缓存）

    代码如下：

private static final int proc = Runtime.getRuntime().availableProcessors();  
   private static final ExecutorService executorService = Executors.newFixedThreadPool(proc + 2);  
  
   public static BigInteger recursiveFasterBigInteger(int n ){  
       if(n>1) {  
           int m = (n/2) + (n&1);  
           BigInteger fM = recursiveFasterBigInteger(m);  
           BigInteger fM_1 = recursiveFasterBigInteger(m-1);  
           //合并结果，计算出原问题的解  
           if((n&1)==1){  
               return fM.pow(2).add(fM_1.pow(2));  
           }else {  
               return fM_1.shiftLeft(1).add(fM).multiply(fM);  
           }  
       }  
       return (n==0)?BigInteger.ZERO:BigInteger.ONE;  
   }  
  
   private static BigInteger recursiveFasterWithCache(int n) {  
       HashMap<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>();  
       return recursiveFasterWithCache(n, cache);  
   }  
  
   private static BigInteger recursiveFasterWithCache(int n, Map<Integer, BigInteger> cache) {  
       if (n > 92) {  
           BigInteger fN = cache.get(n);  
           if (fN == null) {  
               int m = (n / 2) + (n & 1);  
               BigInteger fM = recursiveFasterWithCache(m, cache);  
               BigInteger fM_1 = recursiveFasterWithCache(m - 1, cache);  
               if ((n & 1) == 1) {  
                   fN = fM.pow(2).add(fM_1.pow(2));  
               } else {  
                   fN = fM_1.shiftLeft(1).add(fM).multiply(fM);  
               }  
               cache.put(n, fN);  
           }  
           return fN;  
       }  
       return BigInteger.valueOf(iterativeFaster(n));  
   }  
  
   public static BigInteger recursiveFasterWithCacheAndThread(int n) {  
       int proc = Runtime.getRuntime().availableProcessors();  
       if (n < 128 || proc <= 1) {  
           return recursiveFasterWithCache(n);  
       }  
  
       final ConcurrentHashMap<Integer, BigInteger> cache = new ConcurrentHashMap<Integer, BigInteger>();  
  
       final int m = (n / 2) + (n & 1);  
  
       Callable<BigInteger> callable = new Callable<BigInteger>() {  
           @Override  
           public BigInteger call() throws Exception {  
               return recursiveFasterWithCache(m,cache);  
           }  
       };  
  
       Future<BigInteger> ffM = executorService.submit(callable);  
  
       callable = new Callable<BigInteger>() {  
           @Override  
           public BigInteger call() throws Exception {  
               return recursiveFasterWithCache(m-1,cache);  
           }  
       };  
       Future<BigInteger> ffM_1 = executorService.submit(callable);  
  
       //得到各部分的结果开始合并  
       BigInteger fM,fM_1,fN;  
  
       try{  
           fM = ffM.get();//获取第一个子问题的结果（阻塞调用）  
       }catch (Exception e){  
           //如果抛出了异常 那就在当前主线程中计算fM  
           fM = recursiveFasterBigInteger(m);  
       }  
  
       try{  
           fM_1 = ffM_1.get();//获取第一个子问题的结果（阻塞调用）  
       }catch (Exception e){  
           //如果抛出了异常 那就在当前主线程中计算fM  
           fM = recursiveFasterBigInteger(m-1);  
       }  
  
       if((n & 1) != 0 ){  
           fN = fM.pow(2).add(fM_1.pow(2));  
       }else {  
           fN = fM_1.shiftLeft(1).add(fM).multiply(fM);  
       }  
       return fN;  
   }

    其实很多时候即使把问题分解为子问题并将子问题分派到不同的线程，性能也有可能并没有什么提升，有可能是数据之间有依赖，不得不进行同步，线程就可能会花大部分的时间在等待数据。所以实践中通常是用多线程执行无关的任务，避免同步需求。