CODEWITHSUNDEEP
javamultithreadingperformancealgorithmsorting
Philippe
Philippe

Reputation: 670

Parallel Bubble-sort performances

My goal is to implement the sorting algorithm Bubble-sort using Thread, the program seems to run okay. However the performances are horrible, so I wanted to know how to make the code run faster and why does it run so badly.

The code is based on the following algorithm :

PARALLEL BUBBLE SORT(A) - algorithm

> 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();
            }
        }}          
    }
}

EDIT :

Here is the new version with ExecutorService, unfortunately, as predicted, it still runs very badly, slower than the sequential version.

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();}
}

Upvotes: 2

Views: 2584

Answers (1)

Mike Nakis
Mike Nakis

Reputation: 61993

The reason why it is so slow is that the invocation of new Thread() is very expensive. It takes thousands of times more clock cycles to start another thread to do part of the sorting, than to do all of the sorting in your original thread.

Also, even if new Thread() was not so expensive, you would still not see much (or any) performance improvement, because sorting is a memory-bound operation, and you are most probably trying to run it on a single-CPU, multi-core system, but the CPU has only one address bus and one data bus, so the cores will mostly be waiting for each other to let go of the data bus.

Upvotes: 2

Related Questions