Single vs MultiThread : Mergesort performance comparison

Question

Can anyone please look at the code snippet below?

It's a Class to test multithreaded solution of mergesort by splitting an array of words into 10 sub-arrays, vs single threaded solution and passing the whole array as argument.

For some reason only works better for the multi-thread version when the size of the array is 1 million, and it's terrible (2 seconds more than single threaded solution) when I increase it to 10 million.

Probably because of final merge step of the concatenated ordered lists, line 120.

I guess that at some point there is no more performance advantage of splitting the array, using 10 threads to process the dataset and sort the merged results.

I'm aware that it's not a proper benchmark and that skipping the JVM warm-up step might have a little influence in the times.

Average times for array size = 1 million :

Single Thread : 450ms

Multi Thread : 350ms

Average times for array size = 10 million :

Single Thread : 3.5s

Multi Thread : 5s

package brandao;

import com.fnf.xes.services.test.util.generators.impl.StupidDictionary;
import org.apache.commons.io.FileUtils;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * User: ostras
 * Date: 23/09/15
 * Time: 14:16
 * 
 * Class to test multithreaded solution of mergesort by splitting array of words into 10 sub-arrays, vs single threaded solution and passing the whole array as argument.
 * For some reason only works better for multiT when the size of the array is 1000000.
 * Probably because of final merge step of the concatenated ordered lists, line 120.
 * At some point there is no more performance advantage of splitting the array and using 10 threads to process the dataset.
 */
public class ThreadTest {

    private static StupidDictionary stupidDictionary = new StupidDictionary();
    private static ArrayList<String> list = new ArrayList<String>();
    private static ArrayList<String> list2 = new ArrayList<String>();


    public static void main(String[] args) {
        ThreadTest test = new ThreadTest();
        int length = 10000000;

        stupidDictionary.loadDefault();

        for (int i = 0; i <= length; i++) {
            String word = stupidDictionary.getRandomWord();
            list.add(word);
            list2.add(word);
        }

        //System.out.println("The list is : " + list.toString());

        long startTime = System.currentTimeMillis();

        test.testSingleThread(list);

        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Single Thread : " + elapsedTime + "ms");
        //System.out.println("Sorted list : " + list);
/*
        try{
            FileUtils.writeLines(new File("textdata.txt"), list);
        } catch (IOException ioe) {

        }
*/

        startTime = System.currentTimeMillis();

        test.testMultiThread(list2);

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("Multi Thread : " + elapsedTime + "ms");
        //System.out.println("Sorted list 2 : " + test.testMultiThread(list2));
    }

    public void testSingleThread(ArrayList<String> array) {
        mergeSort(array);
    }

    public ArrayList<String> testMultiThread(final ArrayList<String> obj) {
/*        MyThread rum = new MyThread(obj.subList(0 , 100000));
        MyThread rdois = new MyThread(obj.subList(100000 , 200000));
        MyThread rtres = new MyThread(obj.subList(200000 , 300000));
        MyThread rquatro = new MyThread(obj.subList(300000 , 400000));
        MyThread rcinco = new MyThread(obj.subList(400000 , 500000));
        MyThread rseis = new MyThread(obj.subList(500000 , 600000));
        MyThread rsete = new MyThread(obj.subList(600000 , 700000));
        MyThread roito = new MyThread(obj.subList(700000 , 800000));
        MyThread rnove = new MyThread(obj.subList(800000 , 900000));
        MyThread rdez = new MyThread(obj.subList(900000 , 1000001));*/

        MyThread rum = new MyThread(obj.subList(0, 1000000));
        MyThread rdois = new MyThread(obj.subList(1000000, 2000000));
        MyThread rtres = new MyThread(obj.subList(2000000, 3000000));
        MyThread rquatro = new MyThread(obj.subList(3000000, 4000000));
        MyThread rcinco = new MyThread(obj.subList(4000000, 5000000));
        MyThread rseis = new MyThread(obj.subList(5000000, 6000000));
        MyThread rsete = new MyThread(obj.subList(6000000, 7000000));
        MyThread roito = new MyThread(obj.subList(7000000, 8000000));
        MyThread rnove = new MyThread(obj.subList(8000000, 9000000));
        MyThread rdez = new MyThread(obj.subList(9000000, 10000001));

        new Thread(rum).start();
        new Thread(rdois).start();
        new Thread(rtres).start();
        new Thread(rquatro).start();
        new Thread(rcinco).start();
        new Thread(rseis).start();
        new Thread(rsete).start();
        new Thread(roito).start();
        new Thread(rnove).start();
        new Thread(rdez).start();

        ArrayList<String> result = new ArrayList<String>();
        result.addAll(rum.getToSort());
        result.addAll(rdois.getToSort());
        result.addAll(rtres.getToSort());
        result.addAll(rquatro.getToSort());
        result.addAll(rcinco.getToSort());
        result.addAll(rseis.getToSort());
        result.addAll(rsete.getToSort());
        result.addAll(roito.getToSort());
        result.addAll(rnove.getToSort());
        result.addAll(rdez.getToSort());

        mergeSort(result);

        return result;
    }

    public void mergeSort(List<String> obj) {
        Collections.sort(obj);
    }

    public class MyThread implements Runnable {
        List<String> toSort;

        public MyThread(List<String> toSort) {
            this.toSort = toSort;
        }

        public void run() {
            mergeSort(toSort);
        }

        public List<String> getToSort() {
            return this.toSort;
        }
    }
}

Answer 1

Mergesort should be memory bandwidth limited, but the cache in each core may help a bit. Maybe try using 4 or 8 threads instead of 10. After the sorts are done, merge the 4 or 8 parts instead of concatenating and sorting again.

I'm not sure this is going to help much. With C / C++, a merge sort of 4 million 64 bit unsigned integers takes less than 1/2 second on my system, Intel 2600K (3.4 ghz).