Multi thread array sort Java

Question

So hello!

I'm trying to sort int array with several threads. Now I've got something like this:

import java.util.Arrays;


public class MultiTread extends  Thread{

int sizeOfArray;
public static int treadsN = 4;
public  static  int sortFrom;
public  static  int sortTo;

public MultiTread(int sizeOfArray, int treadsN) {
    this.sizeOfArray = sizeOfArray;
    this.treadsN = treadsN;
}

public MultiTread(int[] arrayToSort, int sizeOfArray) {
    this.sizeOfArray = sizeOfArray;
}



public static int [] creatingArray(int sizeOfArray) {
    int [] arrayToSort = new int[sizeOfArray];
    int arrayLength = arrayToSort.length;
    for (int counter = 0; counter<arrayLength; counter++){
        arrayToSort[counter] = (int)(8000000*Math.random());
    }
    return arrayToSort;
}

public  static  int [] sortInSeveralTreads(final int [] arrayToSort){
    int [] newArr = new int[arrayToSort.length];
    int numberOfThreads = treadsN;
    if (numberOfThreads == 0){
        System.out.println("Incorrect value");
        return arrayToSort;
    }
    if (numberOfThreads == 1){
        Arrays.sort(arrayToSort);
        System.out.println("Array sorted in 1 thread");
    } else {
         final int lengthOfSmallArray = arrayToSort.length/numberOfThreads;
        sortFrom = 0;
        sortTo = lengthOfSmallArray;
        for (int progress = 0; progress < numberOfThreads; progress++){
            final int [] tempArr = Arrays.copyOfRange(arrayToSort,sortFrom,sortTo);
            new Thread(){public void run() {
                Arrays.sort(tempArr);
            }}.start();
            sortFrom = sortTo;
            sortTo += lengthOfSmallArray;
            newArr =  mergeSort(newArr, tempArr);
        }
        new Thread(){public void run() {
            Arrays.sort(Arrays.copyOfRange(arrayToSort, arrayToSort.length-lengthOfSmallArray, arrayToSort.length));
        }}.start();
        newArr = mergeSort(newArr, arrayToSort);
    }
    return newArr;
}

public static  int [] mergeSort(int [] arrayFirst, int [] arraySecond){
    int [] outputArray = new  int[arrayFirst.length+arraySecond.length];
    while (arrayFirst.length != 0 && arraySecond.length != 0){
        int counter = 0;
        if (arrayFirst[0] < arraySecond[0]){
            outputArray[counter] = arrayFirst[0];
            counter++;
            arrayFirst = Arrays.copyOfRange(arrayFirst, 1, arrayFirst.length);
        }else {
            outputArray[counter] = arraySecond[0];
            counter++;
            arraySecond = Arrays.copyOfRange(arraySecond, 1, arraySecond.length);
        }
    }
    return outputArray;
}


public static void main(String[] args){
    long startTime;
    long endTime;
    int [] a = creatingArray(8000000);
    startTime = System.currentTimeMillis();
    a =  sortInSeveralTreads(a);
    endTime = System.currentTimeMillis();
    System.out.println(Thread.activeCount());
    System.out.printf("Sorted by: %d treads in %.7f seconds %n", treadsN, (float)(endTime-startTime)*1e-6);
    try {
        Thread.currentThread().sleep(1000);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println(Thread.activeCount());
}
}

I know that it's not very good realization. All works fine but merge sort works too bad - it crashes... Error should be in that lines:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOfRange(Arrays.java:3137)
at MultiTread.mergeSort(MultiTread.java:78)
at MultiTread.sortInSeveralTreads(MultiTread.java:61)
at MultiTread.main(MultiTread.java:94)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
at java.lang.reflect.Method.invoke(Method.java:597)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)

What i'm doing wrong?

You are trying to create a array with 8 million elements and you have a OOM error -- you are using too much memory, which is larger than your JVM's heap memory setting. Can you point out exactly what the 78th, 61st and 94th line in MultiTread.java is? — Dante WWWW
– Dante WWWW, Commented Dec 23, 2011 at 7:17
int [] outputArray = new int[arrayFirst.length+arraySecond.length]; — Ivan Kozlov
– Ivan Kozlov, Commented Dec 23, 2011 at 7:19
here you are; Main error in creating array with length of 2 small arrays, but this length should be around 4 millions - i have no idea why i catch memory exemption — Ivan Kozlov
– Ivan Kozlov, Commented Dec 23, 2011 at 7:21
Wouldn't it be faster (and use less memory) if you sorted the values in place as much as possible. As far as I can see you only need to take a copy to do the final merge. — Peter Lawrey
– Peter Lawrey, Commented Dec 23, 2011 at 8:38

Zéychin · Accepted Answer · 2011-12-23 07:18:14Z

Well, you're running out of the memory allowed by use by the J.V.M..

I've not checked to see that your algorithm is correct, but you should try the code with a much smaller array to see if it works alright, say, 1000.

You make several copies of the array (or at least partial copies) throughout your program, in threads. Each thread then is allocating a large amount of data. For this reason, you may wish to reconsider your design, or you will continue to run into this problem. If you find no way to reduce this allocation and my next paragraph does not help you, then you may need to resort to the use of files to sort these large arrays, instead of attempting to hold everything in memory at once.

You can increase the heap size by following instructions on this page (first link I found, but it has the right information): http://viralpatel.net/blogs/2009/01/jvm-java-increase-heap-size-setting-heap-size-jvm-heap.html This will allow you to hold allocate more memory from your Java program.

Ahmed Masud · Accepted Answer · 2011-12-23 07:24:41Z

1

Okay there are several issues:

First your array size is way too large. Which is why you are running out of Memory (8000000) should be tried with a low number say 1000. Even with that your code will probably crash elsewhere as it stands.

Second your code makes very little sense as it stands you are mixing static and non static calls ... e.g. Thread.currentThread().sleep(1000) is bizarre, you are not in the current Thread.

The thread creation where you perform Array.sort.

I suggest that first you create a simple multi-threaded program before dealing with sorting job. Also recommend that you implement Runnable interface rather than extending the Thread class to create your worker class.

answered Dec 23, 2011 at 7:24

Ahmed Masud

22.7k3 gold badges37 silver badges60 bronze badges

Comments

dku.rajkumar · Accepted Answer · 2011-12-23 07:18:35Z

0

while (arrayFirst.length != 0 && arraySecond.length != 0){

here it goes in infinite loop once the conditions are satisfied and hence the memory heap is getting OutOfMemoryError

It is not at all terminated so You should include some code to terminate this loop.

answered Dec 23, 2011 at 7:18

dku.rajkumar

18.6k8 gold badges43 silver badges58 bronze badges

10 Comments

Zéychin Over a year ago

Actually, it appears that it will exit due to the: arrayFirst = Arrays.copyOfRange(arrayFirst, 1, arrayFirst.length); and arraySecond = Arrays.copyOfRange(arraySecond, 1, arrayFirst.length); statements.

dku.rajkumar Over a year ago

yeah i saw that but seems that due to some reason it is not terminating.

Zéychin Over a year ago

Actually, if I understand how Arrays.copyOfRange() works, then when arrayFirst.length == 1, it will enter a loop, as each following call to arrayFirst = Arrays.copyOfRange(arrayFirst, 1, arrayFirst.length); will yield an array of size 1, and so the loop will not end. Either way, this does not result in an OutOfMemoryError. This results in an infinite loop, which is not the problem.

Ivan Kozlov Over a year ago

But it didn't help; very strange - i just made a debug - no idea why loop is infinite.

dku.rajkumar Over a year ago

i have faced the OutOfMemoryError many times when the loop goes in infinite loop. it consume all the heap memory and throw OutOfMemoryError error.

|

Collectives™ on Stack Overflow

Multi thread array sort Java

3 Answers 3

Comments

Comments

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related