CODEWITHSUNDEEP
javamultithreading
amingo
amingo

Reputation: 101

multithread summation with java

I intend to get summation from 1 to 10000000 using multithread, below code doesn't work correctly in this line - sum = sum + Sum(finalI, finalI * step);, the sum is always 0 in current thread. I have already added volatile, I'm new to java I don't know how to solve this.

package test;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class testParallelFor {
    volatile static long sum = 0;
    final static int step = 100;
    final static int start = 1;
    final static int end = 10000000;

    public static void main(String[] args) throws InterruptedException {
        int num = Runtime.getRuntime().availableProcessors();
        ExecutorService exec = Executors.newFixedThreadPool(num);
        try {
            for (int i = start; i < end; i = i * step) {
                int finalI = i;
                exec.submit(new Runnable() {
                    @Override
                    public void run() {
                        sum = sum + Sum(finalI, finalI * step);
                    }
                });
            }

        } finally {
            exec.shutdown();
            exec.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
            sum = sum + end;
            System.out.println(sum);
        }
    }

    static long Sum(int i, int j) {
        System.out.println("Sum from " + i + " to " + j + " start.");
        long temp = 0;
        for (int k = i; k < j; k++) {
            temp = temp + k;
        }
        System.out.println("Sum from " + i + " to " + j + " end. sum=" + temp);
        return temp;
    }
}

output:

Sum from 1 to 100 start.
Sum from 1000000 to 100000000 start.
Sum from 100 to 10000 start.
Sum from 10000 to 1000000 start.
Sum from 1 to 100 end. sum=4950
Sum from 100 to 10000 end. sum=49990050
Sum from 10000 to 1000000 end. sum=499949505000
Sum from 1000000 to 100000000 end. sum=4999499950500000
4999499960500000

Upvotes: 0

Views: 674

Answers (3)

Jason Law
Jason Law

Reputation: 1015

the sum is always 0 in current thread

No, this is not true. You can replace ExecutorService exec = Executors.newFixedThreadPool(num); with ExecutorService exec = Executors.newFixedThreadPool(1);, you will see sum is 0 only in the first task. This is because there is only one thread, the tasks are executed sequentially, the next task will guarantee to see the change of sum.

// replace `ExecutorService exec = Executors.newFixedThreadPool(num);` with `ExecutorService exec = Executors.newFixedThreadPool(1);`
// add `System.out.printf("i: %d, sum: %d\n", finalI, sum);` in `run`
i: 1, sum: 0
i: 100, sum: 4950
i: 10000, sum: 49995000
i: 1000000, sum: 499999500000

When the number of threads >= the number of tasks, sum is "always" 0. This is because tasks can be executed concurrently, they see the initial 0 before other threads update sum.

But when the 1 < the number of threads < the number of tasks, you can't predict which tasks will see 0, which tasks will see the change. The only guarantee is that when the task is getting executed and start to read sum, it will see the latest sum.

Upvotes: 0

Andy Turner
Andy Turner

Reputation: 140554

the sum is always 0 in current thread

That's possible (although not guaranteed) because of the evaluation order of the expression:

sum+ Sum(finalI, finalI * step)

sum is read before invoking Sum; and Sum is slow when it's called for a large input range.

All the threads are started at roughly the same time, and the very first thing they will do is to read sum. Unless it has already been updated by another thread, the thread will read the initial value, evaluate Sum, and then add the result back to the sum variable without checking to see if sum was updated in the interim.

You could do the slow evaluation of Sum prior to reading sum:

sum = Sum(finalI, finalI * step) + sum;

but you still have the issue that the read of sum and the write of the updated sum are performed atomically: another thread can update sum in between, and then this thread would stomp that thread's update.

You would need to use some sort of synchronization to ensure that updates happen atomically; or use something like AtomicLong or LongAdder, which can be updated atomically.

Or use the Executor better, so you don't need to worry about synchronization of the updates to sum:

List<Future<Long>> futures = new ArrayList<>();
for (int i = start; i < end;i = i * step) {
  int finalI = i;
  futures.add(exec.submit(() -> Sum(finalI, finalI * step)));
}

long sum = 0;  // No need to be volatile if you update in a single thread.
for (Future<Long> future : futures) {
  sum += future.get();
}

Or use parallel streams, as in Abrikot's answer.

Upvotes: 3

Abrikot
Abrikot

Reputation: 1005

The easiest solution would probably to use parallel streams:

long start = 1;
long end = 10000000;
long result = LongStream.rangeClosed(start, end)  // Creates a stream going from 1 to 10000000
        .parallel()  // Parallelize this stream
        .sum();      // Sums every value of this stream
System.out.println(result);

That's much more clear than your version :)

Upvotes: 4

Related Questions