[FIXED] Parallel implementation of sum problem returns unexpected results

Issue

So I was learning and experimenting with java concurrent package where I came upon a parallel implementation of adding numbers.

I wanted to try a different approach, so I mixed the parallel implementation of merge sort algorithm which is the divide and conquer method with typical addition of numbers.

Here is the code:

class SequentialSum {
    public static long sum(int[] numbers, int low, int high) {
        long total = 0;
        for (int i = low; i <= high; i++) total += numbers[i];
        return total;
    }
}

class ParallelSum {

    private static final AtomicLong finalSum = new AtomicLong(0);

    public static void parallelSum(int[] numbers, int low, int high, int threads) {

        if (threads <= 1) finalSum.addAndGet(SequentialSum.sum(numbers, low, high));

        int middle = (low + high) / 2;
        Thread left = new Thread(() -> parallelSum(numbers, low, middle, threads / 2));
        Thread right = new Thread(() -> parallelSum(numbers, middle + 1, high, threads / 2));

        left.start();
        right.start();
    }

    public static long getOutput() {
        return finalSum.get();
    }
}

public class _3_ParallelSummation {

    private static final int NUM_OF_THREADS = Runtime.getRuntime().availableProcessors();
    private static final Random random = new Random();
    private static final int ARRAY_LENGTH = 100_000_000;

    public static void main(String[] args) throws InterruptedException {

        int[] numbers = new int[ARRAY_LENGTH];
        for (int i = 0; i < ARRAY_LENGTH; i++) numbers[i] = random.nextInt(10);


        long t1 = System.currentTimeMillis();
        long sum = SequentialSum.sum(numbers, 0, ARRAY_LENGTH - 1);
        long t2 = System.currentTimeMillis();
        System.out.printf("Sum is: %d, completed in %d ms\n", sum, t2 - t1);

        t1 = System.currentTimeMillis();
        ParallelSum.parallelSum(numbers, 0, ARRAY_LENGTH - 1, NUM_OF_THREADS);
        t2 = System.currentTimeMillis();
        Thread.sleep(1000);
        System.out.printf("Sum is: %d, completed in %d ms\n", ParallelSum.getOutput(), t2 - t1);
    }
}

I'm getting unexpected results:

Sum is: 449963052, completed in 56 ms
Sum is: 3950670566, completed in 3 ms
[28.597s][warning][os,thread] Failed to start thread - _beginthreadex failed (EACCES) for attributes: stacksize: default, flags: CREATE_SUSPENDED STACK_SIZE_PARAM_IS.
[28.598s][warning][os,thread] Failed to start thread - _beginthreadex failed (EACCES) for attributes: stacksize: default, flags: CREATE_SUSPENDED STACK_SIZE_PARAM_IS.
[28.598s][warning][os,thread] Failed to start thread - _beginthreadex failed (EACCES) for attributes: stacksize: default, flags: CREATE_SUSPENDED STACK_SIZE_PARAM_IS.
[28.601s][warning][os,thread] Failed to start thread - _beginthreadex failed (EACCES) for attributes: stacksize: default, flags: CREATE_SUSPENDED STACK_SIZE_PARAM_IS.

What is the mistake I made in my code? Or is my way of thinking wrong?

Solution

Missing else block in merge sort

if (threads <= 1) { 
            finalSum.addAndGet(SequentialSum.sum(numbers, low, high));
        }else {
        int middle = (low + high) / 2;
        Thread left = new Thread(() -> parallelSum(numbers, low, middle, threads / 2));
        Thread right = new Thread(() -> parallelSum(numbers, middle + 1, high, threads / 2));
        left.start();
        right.start();
}

Adding else block will fix the code.

also you can remove the fixed sleep time by using join()

left.join();
right.join();

Answered By - Minnow
Answer Checked By - Pedro (JavaFixing Volunteer)