Java多线程效率-素数计算

方兆国

1. 
   
2. JavaNative 单线程实现
   
3. Number of primes under 10000000 is  664579
   
4. Time taken is 21.640470622 s
   
5. 
   
6. JavaPure 单线程实现：
   
7. Number of primes under 10000000 is  665025
   
8. Time taken is 29.615632484 s
   
9. 
   
10. JavaPure 4线程实现：
    
11. Number of primes under 10000000 is  665025
    
12. Time taken is 12.943822983 s
    
13. 
    
14. JavaPure 5线程实现：
    
15. Number of primes under 10000000 is  665025
    
16. Time taken is 11.316296326 s
    
17. 
    
18. JavaPure 6线程实现：
    
19. Number of primes under 10000000 is  665025
    
20. Time taken is 11.852669045 s
    
21. 
    
22. JavaPure 7线程实现：
    
23. Number of primes under 10000000 is  665024
    
24. Time taken is 11.875677067 s
    
25. 
    
26. JavaPure 8线程实现：
    
27. Number of primes under 10000000 is  665025
    
28. Time taken is 11.583545436 s
    
29. 
    
30. JavaPure 9线程实现：
    
31. Number of primes under 10000000 is  665025
    
32. Time taken is 11.472949961 s
    
33. 
    
34. JavaPure 4Mix线程实现：
    
35. Number of primes under 10000000 is  664579
    
36. Time taken is 10.488330912 s
    
37. 
    
38. JavaPure 5Mix线程实现：
    
39. Number of primes under 10000000 is  664579
    
40. Time taken is 10.491616154 s
    
41. 
    
42. JavaPure 6Mix线程实现：
    
43. Number of primes under 10000000 is  664579
    
44. Time taken is 10.480008206 s
    
45. 
    
46. JavaPure 7Mix线程实现：
    
47. Number of primes under 10000000 is  664579
    
48. Time taken is 10.357619101 s
    
49. 
    
50. JavaPure 8Mix线程实现：
    
51. Number of primes under 10000000 is  664579
    
52. Time taken is 10.43754778 s
    
53. 
    
54. JavaPure 9Mix线程实现：
    
55. Number of primes under 10000000 is  664579
    
56. Time taken is 10.511800879 s
    

复制代码

方兆国

先上主函数

1. package com.fangzhaoguo.primefinder;
   
2. 
   
3. public class Main {
   
4. 
   
5.         public static void main(String[] args) {
   
6.                 timeAndCompute(10000000);
   
7.         }
   
8. 
   
9.         public static void timeAndCompute(final long number) {
   
10.                 long start = 0, numberofPrime = 0, end = 0;
    
11.                 NativePrimeFinder nativePrimeFinder = new NativePrimeFinder();
    
12.                 start = System.nanoTime();
    
13.                 numberofPrime = nativePrimeFinder.countPrime(number);
    
14.                 end = System.nanoTime();
    
15.                 System.out.println("\nJavaNative 单线程实现");
    
16.                 System.out.println("Number of primes under " + number + " is  "
    
17.                                 + numberofPrime);
    
18.                 System.out.println("Time taken is " + (end - start) / 1.0e9 + " s");
    
19. 
    
20.                 SequentialPrimeFinder sequentialPrimeFinder = new SequentialPrimeFinder();
    
21.                 start = System.nanoTime();
    
22.                 numberofPrime = sequentialPrimeFinder.countPrime(number);
    
23.                 end = System.nanoTime();
    
24.                 System.out.println("\nJavaPure 单线程实现：");
    
25.                 System.out.println("Number of primes under " + number + " is  "
    
26.                                 + numberofPrime);
    
27.                 System.out.println("Time taken is " + (end - start) / 1.0e9 + " s");
    
28. 
    
29.                 for (int i = 4; i < 10; i++) {
    
30.                         ConcurrentPrimeFinder concurrentPrimeFinder = new ConcurrentPrimeFinder(
    
31.                                         i);
    
32.                         start = System.nanoTime();
    
33.                         numberofPrime = concurrentPrimeFinder.countPrime(number);
    
34.                         end = System.nanoTime();
    
35.                         System.out.println("\nJavaPure " + i + "线程实现：");
    
36.                         System.out.println("Number of primes under " + number + " is  "
    
37.                                         + numberofPrime);
    
38.                         System.out.println("Time taken is " + (end - start) / 1.0e9 + " s");
    
39.                 }
    
40. 
    
41.                 for (int i = 4; i < 10; i++) {
    
42.                         MixConcurrentPrimeFinder mixConcurrentPrimeFinder = new MixConcurrentPrimeFinder(
    
43.                                         i);
    
44.                         start = System.nanoTime();
    
45.                         numberofPrime = mixConcurrentPrimeFinder.countPrime(number);
    
46.                         end = System.nanoTime();
    
47.                         System.out.println("\nJavaPure " + i + "Mix线程实现：");
    
48.                         System.out.println("Number of primes under " + number + " is  "
    
49.                                         + numberofPrime);
    
50.                         System.out.println("Time taken is " + (end - start) / 1.0e9 + " s");
    
51.                 }
    
52.         }
    
53. }
    

复制代码

方兆国

1. package com.fangzhaoguo.primefinder;
   
2. 
   
3. public abstract class AbstractPrimeFinder {
   
4. 
   
5.         public abstract boolean isPrime(final long number);
   
6. 
   
7.         public abstract int countPrime(final long number);
   
8. 
   
9.         public abstract int countPrime(final long lower, final long upper);
   
10. }

复制代码

这是一个虚基类,其实也可以写成接口,不过感觉用处不大;
下面的四个例子中,除了JavaNative的例子没有用到这个类,其他三个纯Java的例子都用到了

方兆国

JavaNative的Java类

1. package com.fangzhaoguo.primefinder;
   
2. 
   
3. public class NativePrimeFinder {
   
4.         static {
   
5.                 System.loadLibrary("libJavaNative_PrimeFinder");
   
6.         }
   
7. 
   
8.         public NativePrimeFinder() {
   
9. 
   
10.         }
    
11. 
    
12.         public native boolean isPrime(final long number);
    
13. 
    
14.         public native int countPrime(final long number);
    
15. 
    
16.         public native int countPrime(final long lower, final long upper);
    
17. }
    

复制代码

JavaNative的C头文件,这里只是将#include <jni.h>修改成#include "jni.h"

1. /* DO NOT EDIT THIS FILE - it is machine generated */
   
2. #include "jni.h"
   
3. /* Header for class com_fangzhaoguo_primefinder_NativePrimeFinder */
   
4. 
   
5. #ifndef _Included_com_fangzhaoguo_primefinder_NativePrimeFinder
   
6. #define _Included_com_fangzhaoguo_primefinder_NativePrimeFinder
   
7. #ifdef __cplusplus
   
8. extern "C" {
   
9. #endif
   
10.         /*
    
11.          * Class:     com_fangzhaoguo_primefinder_NativePrimeFinder
    
12.          * Method:    isPrime
    
13.          * Signature: (J)Z
    
14.          */
    
15.         JNIEXPORT jboolean JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_isPrime(
    
16.                         JNIEnv *, jobject, jlong);
    
17. 
    
18.         /*
    
19.          * Class:     com_fangzhaoguo_primefinder_NativePrimeFinder
    
20.          * Method:    countPrime
    
21.          * Signature: (J)I
    
22.          */
    
23.         JNIEXPORT jint JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_countPrime__J(
    
24.                         JNIEnv *, jobject, jlong);
    
25. 
    
26.         /*
    
27.          * Class:     com_fangzhaoguo_primefinder_NativePrimeFinder
    
28.          * Method:    countPrime
    
29.          * Signature: (JJ)I
    
30.          */
    
31.         JNIEXPORT jint JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_countPrime__JJ(
    
32.                         JNIEnv *, jobject, jlong, jlong);
    
33. 
    
34. #ifdef __cplusplus
    
35. }
    
36. #endif
    
37. #endif
    

复制代码

JavaNative的C源文件

1. /*
   
2. * com_fangzhaoguo_primefinder_NativePrimeFinder.c
   
3. *
   
4. *  Created on: 2013年7月18日
   
5. *      Author: root
   
6. */
   
7. 
   
8. #include "com_fangzhaoguo_primefinder_NativePrimeFinder.h"
   
9. 
   
10. #include <stdio.h>
    
11. #include <math.h>
    
12. 
    
13. JNIEXPORT jboolean JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_isPrime(
    
14.                 JNIEnv *env, jobject obj, jlong number) {
    
15.         jlong i = 0;
    
16.         if (1 >= number) {
    
17.                 return 0;
    
18.         }
    
19.         for (i = 2; i <= sqrt(number); i++) {
    
20.                 if (0 == number % i) {
    
21.                         return 0;
    
22.                 }
    
23.         }
    
24.         return 1;
    
25. }
    
26. 
    
27. JNIEXPORT jint JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_countPrime__J(
    
28.                 JNIEnv *env, jobject obj, jlong number) {
    
29.         jint total = 0;
    
30.         jlong i = 0;
    
31.         for (i = 2; i < number; i++) {
    
32.                 if (Java_com_fangzhaoguo_primefinder_NativePrimeFinder_isPrime(env, obj,
    
33.                                 i)) {
    
34.                         total++;
    
35.                 }
    
36.         }
    
37.         return total;
    
38. }
    
39. 
    
40. JNIEXPORT jint JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_countPrime__JJ(
    
41.                 JNIEnv *env, jobject obj, jlong lower, jlong upper) {
    
42.         jint total = 0;
    
43.         jlong i = 0;
    
44.         for (i = lower; i < upper; i++) {
    
45.                 if (Java_com_fangzhaoguo_primefinder_NativePrimeFinder_isPrime(env, obj,
    
46.                                 i)) {
    
47.                         total++;
    
48.                 }
    
49.         }
    
50.         return total;
    
51. }
    

复制代码

方兆国

java单线程类

1. package com.fangzhaoguo.primefinder;
   
2. 
   
3. public class SequentialPrimeFinder extends AbstractPrimeFinder {
   
4. 
   
5.         public SequentialPrimeFinder() {
   
6.         }
   
7. 
   
8.         public boolean isPrime(final long number) {
   
9.                 if (1 >= number) {
   
10.                         return false;
    
11.                 }
    
12.                 for (long i = 2; i < Math.sqrt(number); i++) {
    
13.                         if (0 == number % i) {
    
14.                                 return false;
    
15.                         }
    
16.                 }
    
17.                 return true;
    
18.         }
    
19. 
    
20.         @Override
    
21.         public int countPrime(long number) {
    
22.                 int total = 0;
    
23.                 for (long i = 2; i < number; i++) {
    
24.                         if (isPrime(i)) {
    
25.                                 total++;
    
26.                         }
    
27.                 }
    
28.                 return total;
    
29.         }
    
30. 
    
31.         @Override
    
32.         public int countPrime(long lower, long upper) {
    
33.                 int total = 0;
    
34.                 for (long i = lower; i < upper; i++) {
    
35.                         if (isPrime(i)) {
    
36.                                 total++;
    
37.                         }
    
38.                 }
    
39.                 return total;
    
40.         }
    
41. 
    
42. }
    

复制代码

方兆国

Java多线程的类
在这个类中，没有对运算进行优化，只是简单的将计算区域划分为与线程个数相同的几个部分

1. package com.fangzhaoguo.primefinder;
   
2. 
   
3. import java.util.ArrayList;
   
4. import java.util.List;
   
5. import java.util.concurrent.Callable;
   
6. import java.util.concurrent.ExecutionException;
   
7. import java.util.concurrent.ExecutorService;
   
8. import java.util.concurrent.Executors;
   
9. import java.util.concurrent.Future;
   
10. import java.util.concurrent.TimeUnit;
    
11. 
    
12. public class ConcurrentPrimeFinder extends AbstractPrimeFinder {
    
13. 
    
14.         private int poolSize;
    
15. 
    
16.         public ConcurrentPrimeFinder(int poolSize) {
    
17.                 // this.poolSize = Runtime.getRuntime().availableProcessors();
    
18.                 this.poolSize = poolSize;
    
19.         }
    
20. 
    
21.         public boolean isPrime(final long number) {
    
22.                 if (1 >= number) {
    
23.                         return false;
    
24.                 }
    
25.                 for (long i = 2; i < Math.sqrt(number); i++) {
    
26.                         if (0 == number % i) {
    
27.                                 return false;
    
28.                         }
    
29.                 }
    
30.                 return true;
    
31.         }
    
32. 
    
33.         @Override
    
34.         public int countPrime(long number) {
    
35.                 int total = 0;
    
36.                 List<Callable<Integer>> partitions = new ArrayList<Callable<Integer>>();
    
37.                 long part = number / poolSize;
    
38.                 for (int i = 0; i < poolSize; i++) {
    
39.                         final long low = (i * part) + 1;
    
40.                         final long up = (i == poolSize - 1) ? number : low + part - 1;
    
41.                         partitions.add(new Callable<Integer>() {
    
42. 
    
43.                                 @Override
    
44.                                 public Integer call() throws Exception {
    
45.                                         return countPrimeInRange(low, up);
    
46.                                 }
    
47.                         });
    
48.                 }
    
49. 
    
50.                 ExecutorService executorService = Executors
    
51.                                 .newFixedThreadPool(poolSize);
    
52.                 try {
    
53.                         List<Future<Integer>> reFutures = executorService.invokeAll(
    
54.                                         partitions, 10000, TimeUnit.SECONDS);
    
55.                         executorService.shutdown();
    
56.                         for (Future<Integer> result : reFutures) {
    
57.                                 total += result.get();
    
58.                         }
    
59.                 } catch (InterruptedException e) {
    
60.                         e.printStackTrace();
    
61.                 } catch (ExecutionException e) {
    
62.                         e.printStackTrace();
    
63.                 }
    
64.                 return total;
    
65.         }
    
66. 
    
67.         @Override
    
68.         public int countPrime(long lower, long upper) {
    
69.                 int total = 0;
    
70.                 return total;
    
71.         }
    
72. 
    
73.         private int countPrimeInRange(long lower, long upper) {
    
74.                 int total = 0;
    
75.                 for (long i = lower; i < upper; i++) {
    
76.                         if (isPrime(i)) {
    
77.                                 total++;
    
78.                         }
    
79.                 }
    
80.                 return total;
    
81.         }
    
82. }
    

复制代码

方兆国

Java多线程的类
在这个类中，运算进行优化，首先过滤了所有的偶数，因为偶数中只有2 是素数，所以将total的初始值设为1，然后直接忽略偶数。在判断某一个数是不是素数时，不再考虑偶数问题

1. package com.fangzhaoguo.primefinder;
   
2. 
   
3. import java.util.ArrayList;
   
4. import java.util.List;
   
5. import java.util.concurrent.Callable;
   
6. import java.util.concurrent.ExecutionException;
   
7. import java.util.concurrent.ExecutorService;
   
8. import java.util.concurrent.Executors;
   
9. import java.util.concurrent.Future;
   
10. import java.util.concurrent.TimeUnit;
    
11. 
    
12. public class MixConcurrentPrimeFinder extends AbstractPrimeFinder {
    
13. 
    
14.         private int poolSize;
    
15. 
    
16.         public MixConcurrentPrimeFinder(int poolSize) {
    
17.                 // this.poolSize = Runtime.getRuntime().availableProcessors();
    
18.                 this.poolSize = poolSize;
    
19.         }
    
20. 
    
21.         public boolean isPrime(final long number) {
    
22.                 if (1 >= number) {
    
23.                         return false;
    
24.                 }
    
25.                 if (3 == number || 5 == number) {
    
26.                         return true;
    
27.                 }
    
28.                 for (long i = 1; i < Math.sqrt(number); i++) {
    
29.                         if (0 == number % (2 * i + 1)) {
    
30.                                 return false;
    
31.                         }
    
32.                 }
    
33.                 return true;
    
34.         }
    
35. 
    
36.         @Override
    
37.         public int countPrime(long number) {
    
38.                 int total = 1;
    
39.                 List<Callable<Integer>> partitions = new ArrayList<Callable<Integer>>();
    
40.                 for (int i = 0; i < poolSize; i++) {
    
41.                         final long start = 2 * i + 3;
    
42.                         final long end = number;
    
43.                         partitions.add(new Callable<Integer>() {
    
44. 
    
45.                                 @Override
    
46.                                 public Integer call() throws Exception {
    
47.                                         return countPrimeInRange(start, end);
    
48.                                 }
    
49.                         });
    
50.                 }
    
51. 
    
52.                 ExecutorService executorService = Executors
    
53.                                 .newFixedThreadPool(poolSize);
    
54.                 try {
    
55.                         List<Future<Integer>> reFutures = executorService.invokeAll(
    
56.                                         partitions, 10000, TimeUnit.SECONDS);
    
57.                         executorService.shutdown();
    
58.                         for (Future<Integer> result : reFutures) {
    
59.                                 total += result.get();
    
60.                         }
    
61.                 } catch (InterruptedException e) {
    
62.                         e.printStackTrace();
    
63.                 } catch (ExecutionException e) {
    
64.                         e.printStackTrace();
    
65.                 }
    
66.                 return total;
    
67.         }
    
68. 
    
69.         @Override
    
70.         public int countPrime(long lower, long upper) {
    
71.                 int total = 0;
    
72.                 return total;
    
73.         }
    
74. 
    
75.         private int countPrimeInRange(long start, long end) {
    
76.                 int total = 0;
    
77.                 int part = poolSize * 2;
    
78.                 for (long i = start; i < end; i += part) {
    
79.                         if (isPrime(i)) {
    
80.                                 total++;
    
81.                         }
    
82.                 }
    
83.                 return total;
    
84.         }
    
85. 
    
86. }
    

复制代码

方兆国

1. public abstract int countPrime(final long lower, final long upper);

复制代码

这个函数用于计算指定范围内的素数，这例子中并没有予以实现，都是计算0-10000000之间的素数的个数

方兆国

本来打算做两个JavaNative的多线程例子，可是做出来的动态链接库有问题，无法使用，详情请看

JavaNative 使用Boost多线程库的问题   
JavaNative 使用C多线程库的问题

方兆国

我的CPU是Intel i5 430M，虚拟四核的，经过测试，感觉线程数大于等于四，加速效果比较明显，至于后面，就看不出来多少区别了

下面是没有经过优化的Java多线程运行的结果，线程数从1-39

1. JavaNative 单线程实现
   
2. Number of primes under 10000000 is  664579
   
3. Time taken is 21.359702833 s
   
4. JavaPure 单线程实现：
   
5. Number of primes under 10000000 is  664579
   
6. Time taken is 29.103943469 s
   
7. JavaPure 1线程实现：
   
8. Number of primes under 10000000 is  664579
   
9. Time taken is 26.835752807 s
   
10. JavaPure 2线程实现：
    
11. Number of primes under 10000000 is  664579
    
12. Time taken is 17.268595996 s
    
13. JavaPure 3线程实现：
    
14. Number of primes under 10000000 is  664579
    
15. Time taken is 14.083862457 s
    
16. JavaPure 4线程实现：
    
17. Number of primes under 10000000 is  664579
    
18. Time taken is 12.298518244 s
    
19. JavaPure 5线程实现：
    
20. Number of primes under 10000000 is  664579
    
21. Time taken is 11.293884756 s
    
22. JavaPure 6线程实现：
    
23. Number of primes under 10000000 is  664579
    
24. Time taken is 11.325465024 s
    
25. JavaPure 7线程实现：
    
26. Number of primes under 10000000 is  664578
    
27. Time taken is 11.738370314 s
    
28. JavaPure 8线程实现：
    
29. Number of primes under 10000000 is  664579
    
30. Time taken is 11.126746332 s
    
31. JavaPure 9线程实现：
    
32. Number of primes under 10000000 is  664579
    
33. Time taken is 11.155879652 s
    
34. JavaPure 10线程实现：
    
35. Number of primes under 10000000 is  664579
    
36. Time taken is 11.467730438 s
    
37. JavaPure 11线程实现：
    
38. Number of primes under 10000000 is  664579
    
39. Time taken is 11.723364353 s
    
40. JavaPure 12线程实现：
    
41. Number of primes under 10000000 is  664579
    
42. Time taken is 11.408438917 s
    
43. JavaPure 13线程实现：
    
44. Number of primes under 10000000 is  664579
    
45. Time taken is 11.049511426 s
    
46. JavaPure 14线程实现：
    
47. Number of primes under 10000000 is  664579
    
48. Time taken is 11.056839138 s
    
49. JavaPure 15线程实现：
    
50. Number of primes under 10000000 is  664579
    
51. Time taken is 11.129368095 s
    
52. JavaPure 16线程实现：
    
53. Number of primes under 10000000 is  664579
    
54. Time taken is 11.109334184 s
    
55. JavaPure 17线程实现：
    
56. Number of primes under 10000000 is  664579
    
57. Time taken is 11.158874594 s
    
58. JavaPure 18线程实现：
    
59. Number of primes under 10000000 is  664579
    
60. Time taken is 11.178487773 s
    
61. JavaPure 19线程实现：
    
62. Number of primes under 10000000 is  664579
    
63. Time taken is 11.120964776 s
    
64. JavaPure 20线程实现：
    
65. Number of primes under 10000000 is  664579
    
66. Time taken is 11.086961562 s
    
67. JavaPure 21线程实现：
    
68. Number of primes under 10000000 is  664579
    
69. Time taken is 11.007674624 s
    
70. JavaPure 22线程实现：
    
71. Number of primes under 10000000 is  664579
    
72. Time taken is 11.039509868 s
    
73. JavaPure 23线程实现：
    
74. Number of primes under 10000000 is  664579
    
75. Time taken is 11.145095505 s
    
76. JavaPure 24线程实现：
    
77. Number of primes under 10000000 is  664579
    
78. Time taken is 10.952947299 s
    
79. JavaPure 25线程实现：
    
80. Number of primes under 10000000 is  664579
    
81. Time taken is 11.076983555 s
    
82. JavaPure 26线程实现：
    
83. Number of primes under 10000000 is  664579
    
84. Time taken is 10.941116983 s
    
85. JavaPure 27线程实现：
    
86. Number of primes under 10000000 is  664579
    
87. Time taken is 10.94612999 s
    
88. JavaPure 28线程实现：
    
89. Number of primes under 10000000 is  664579
    
90. Time taken is 11.039012597 s
    
91. JavaPure 29线程实现：
    
92. Number of primes under 10000000 is  664579
    
93. Time taken is 10.939461681 s
    
94. JavaPure 30线程实现：
    
95. Number of primes under 10000000 is  664579
    
96. Time taken is 10.995222494 s
    
97. JavaPure 31线程实现：
    
98. Number of primes under 10000000 is  664579
    
99. Time taken is 10.992655984 s
    
100. JavaPure 32线程实现：
     
101. Number of primes under 10000000 is  664579
     
102. Time taken is 10.955971225 s
     
103. JavaPure 33线程实现：
     
104. Number of primes under 10000000 is  664579
     
105. Time taken is 11.044467169 s
     
106. JavaPure 34线程实现：
     
107. Number of primes under 10000000 is  664579
     
108. Time taken is 10.982884492 s
     
109. JavaPure 35线程实现：
     
110. Number of primes under 10000000 is  664579
     
111. Time taken is 10.987279761 s
     
112. JavaPure 36线程实现：
     
113. Number of primes under 10000000 is  664579
     
114. Time taken is 11.023815067 s
     
115. JavaPure 37线程实现：
     
116. Number of primes under 10000000 is  664579
     
117. Time taken is 11.085869652 s
     
118. JavaPure 38线程实现：
     
119. Number of primes under 10000000 is  664579
     
120. Time taken is 10.986662023 s
     
121. JavaPure 39线程实现：
     
122. Number of primes under 10000000 is  664579
     
123. Time taken is 10.963607354 s
     

复制代码