并行泡泡分类性能

Question

我的目标是实现排序算法泡泡排序使用线程，程序似乎运行良好。然而，这些表现太糟糕了，所以我想知道如何让代码运行得更快，为什么它运行得非常糟糕。

的代码是基于如下算法：

并行的冒泡排序（A） - 算法

> 1.For k = 0 to n-2 
> 2.If k is even then 
> 3. for i = 0 to (n/2)-1 do in parallel 
> 4.  if A[2i] > A[2i+1] then 
> 5.  Exchange A[2i] <-> A[2i+1] 
> 6.Else 
> 7. for i = 0 to (n/2)-2 do in parallel 
> 8. if A[2i+1] > A[2i+2] then 
> 9.  Exchange A[2i+1] <-> A[2i+2] 
> 10.Next k 

---

public static void sort(){ 
    int n = input.length; //length of the array to sort 
    Thread[] thr1 = new Thread[(int)n/2]; 
    Thread[] thr2 = new Thread[(int)n/2]; 
    int count1; 
    int count2; 

    for(int i = 0; i<n-1;i++){ 
     if(i % 2 == 0){ // i even 
     count1 = 0; 

     for(int j = 0; j<n/2; j++){ 
      final int tmp = j; 
      count1++; 
      thr1[tmp] = new Thread(){ 
       public void run(){ 
        if (input[2*tmp]>input[2*tmp+1]) 
         swap(2*tmp,2*tmp+1); 
       } 
      }; 
      thr1[tmp].start(); 
     } 
     //waiting for threads to finish 
     for(int m = 0; m<count1; m++){ 
      try { 
       thr1[m].join(); 
      } catch (InterruptedException e) { 
       e.printStackTrace(); 
      }} 
     } 
     else{ // i odd 
     count2 = 0; 
     for(int k = 0; k<n/2-1;k++){ 
      final int tmp = k; 
      count2++; 
      thr2[tmp] = new Thread(){ 
       public void run(){ 
        if (input[2*tmp+1]>input[2*tmp+2]) 
         swap(2*tmp+1,2*tmp+2); 
       } 
      }; 
      thr2[tmp].start(); 
     } 
     // Waiting for threads to finish 
     for(int m = 0; m<count2; m++){ 
      try { 
       thr2[m].join(); 
      } catch (InterruptedException e) { 
       e.printStackTrace(); 
      } 
     }}   
    } 
} 

编辑：

这里是新版本不幸的是，正如预测的那样，ExecutorService仍然运行得非常糟糕，比顺序版本慢。

public static void sort(){ 
    int n = input.length; //length of the array to sort 
    ExecutorService executor = Executors.newFixedThreadPool(8); 

    for(int i = 0; i<n-1;i++){ 
     if(i % 2 == 0){ // i even 

     for(int j = 0; j<n/2; j++){ 
      final int tmp = j; 
      executor.submit(new Runnable(){ 
       public void run(){ 
        if (input[2*tmp]>input[2*tmp+1]) 
         swap(2*tmp,2*tmp+1);} 
      });} 
     } 

     else{ // i odd 
     for(int k = 0; k<n/2-1;k++){ 
      final int tmp = k; 
      executor.submit(new Runnable(){ 
       public void run(){ 
        if (input[2*tmp+1]>input[2*tmp+2]) 
         swap(2*tmp+1,2*tmp+2);} 
      });} 
     }  
    } 
executor.shutdown(); 
try { 
    executor.awaitTermination(1, TimeUnit.DAYS); 
} catch (InterruptedException e) { 
    e.printStackTrace();} 
} 

Answer 1

它之所以这么慢是因为调用new Thread()是非常昂贵的。它需要数千倍的时钟周期才能启动另一个线程来完成部分排序，而不是完成原始线程中的所有排序。

此外，即使new Thread()并不昂贵，您仍然没有看到太多（或任何）的性能改进，因为排序是一个内存绑定操作，并且您最有可能试图在单CPU上运行它，多核系统，但CPU只有一个地址总线和一个数据总线，所以核心将主要等待对方放开数据总线。