Unable to demonstrate performance gains of parallelism in Java using ForkJoin framework

Question

I have a simple test program. It sums the values in an array of 10m entries using a sequential approach and a parallel approach.

Running on a chromebook, with 12 cores.

import java.util.Random;
import java.util.concurrent.*;

public class App {
    public static void main(String[] args) throws Exception {
        int[] input = generateInput(10_000_000);
        par(input);
        seq(input);
    }

    private static void seq(int[] input) {
        long startTime = System.currentTimeMillis();

        int result = 0;
        for (int num : input) {
            result += num;
        }
        
        System.out.println("Result: " + result);
        System.out.println("Sequential time: " + Long.toString(System.currentTimeMillis() - startTime));
    }

    private static void par(int[] input) {

        int cores = Runtime.getRuntime().availableProcessors();
        System.out.println("Number of cores on this machine: " + Integer.toString(cores));
        
        System.setProperty("java.util.concurrent.ForkJoinPool.common.parallelism", "12");
        ForkJoinPool forkJoinPool = new ForkJoinPool(12);

        long startTime = System.currentTimeMillis();
        RecursiveSumTask task = new RecursiveSumTask(input, 0, input.length);
        forkJoinPool.execute(task);
        forkJoinPool.invoke(task);

        System.out.println("Result: " + task.getResult());
        System.out.println("Parallel time: " + Long.toString(System.currentTimeMillis() - startTime));

    }

    public static int[] generateInput(int size) {
        Random random = new Random();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(5);
        }
        return array;
    }
    
}

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

public class RecursiveSumTask extends RecursiveAction {

    private int[] input;
    private int start;
    private int end;
    private static final int THRESHOLD = 1000;
    private int result;

    public RecursiveSumTask(int[] input, int start, int end) {
        this.input = input;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        if ((this.end - this.start) / 2 > THRESHOLD) {
            List<RecursiveSumTask> subTasks = createSubtasks();
            ForkJoinTask.invokeAll(subTasks);
            subTasks.forEach((n) -> this.result += n.getResult());
        } else {
           process();
        }
    }

    private List<RecursiveSumTask> createSubtasks() {
        List<RecursiveSumTask> subtasks = new ArrayList<RecursiveSumTask>();
        int mid = (end + start) / 2;
        subtasks.add(new RecursiveSumTask(input, this.start, mid));
        subtasks.add(new RecursiveSumTask(input, mid, this.end));

        return subtasks;
    }

    private void process() {
     for (int i = start; i < end; i++) {
        this.result += input[i];
     }
    }

    public int getResult() {
        return this.result;
    }
}

Typical output is:

Number of cores on this machine: 12 Result: 20003614 Parallel time: 76 Result: 20003614 Sequential time: 25

This is surprising. The parallel implementation is taking longer! (also the results sometimes vary, but that is probably an integer overflow)

Answer 1

Try this. According to documentation

• both sorting methods use the Dual Pivot QuickSort algorithm
• parallel sort uses ForkJoin
• each test uses an array of a fixed size and runs each sorting algorithm n times and averages them out.
• using something like JMH would yield more accurate results.
• I am running a 4 core Intel i7 processor on Windows 10.

 Random r = new Random();
 int size = 100_000_000;
 int[] array = r.ints(size, 1, 1000).toArray();
 System.out.println("Starting");
 int n = 10;
 {
     double avgTime = 0;
     for (int i = 0; i < n; i++) {
         long start = System.nanoTime();
         int[] par = array.clone();
         Arrays.parallelSort(par);
         avgTime += (System.nanoTime() - start) / 1e9;
     }
     System.out.println("Parallel Sort = " + avgTime / n);

 }

 {
     double avgTime = 0;
     for (int i = 0; i < n; i++) {
         long start = System.nanoTime();
         int[] seq = array.clone();
         Arrays.sort(seq);
         avgTime += (System.nanoTime() - start) / 1e9;
     }
     System.out.println("Sequential Sort = " + avgTime / n);
 }

prints something like

Starting
Parallel Sort = 3.00119538
Sequential Sort = 5.3311432000000005