Sum of numbers from 0 to 2999999 in Java

Question

I am a Beginner here. I want to make comparison of runTime between the sequential and parallel (multithreading) summation of numbers from 0 to 2999999 in Java. I want to make sure myself that parallel sum is faster than sequential. I made a small program in Eclipse. However, I could not properly extract the results from threads and/or put them into the ArrayList to further sum them to have totalSum. My codes are attached. Please, help? Thank you in advance!

Here is the main class:

public class threading_sum {

public static void main(String[] args) {

    //Sequential summation:
    double sum_seq = 0;
    long beginTime_seq = System.currentTimeMillis();
    for (int i = 0; i <= 2999999; i++) {            
        sum_seq += i;
    }   
    long endTime_seq = System.currentTimeMillis();
    System.out.println("Sequential sum took "+(endTime_seq-beginTime_seq)+" ms. Sum is "+sum_seq);  

    //Parallel summation with 3 threads:
    long beginTime_par = System.currentTimeMillis();
    runnable R1 = new runnable(0, 999999, "Thread-1");
    R1.start();

    runnable R2 = new runnable(1000000, 1999999, "Thread-2");
    R2.start();

    runnable R3 = new runnable(2000000, 2999999, "Thread-3");
    R3.start();

    //Sum of results from all threads:
    System.out.println(runnable.arr);
    int totalSum = 0;
    for (double i : runnable.arr) {
        totalSum += i;
    }       
    long endTime_par = System.currentTimeMillis();

    System.out.println("Parallel sum took "+(endTime_par-beginTime_par)+" ms. Sum is "+totalSum);
}
}

Here is the runnable class:

import java.util.ArrayList;

class runnable implements Runnable {

private Thread t;
private int begin;
private int end;
private String threadName;

public runnable(int b, int e, String T_name) {
    begin = b;
    end = e;
    threadName = T_name;
}

static ArrayList<Double> arr = new ArrayList<Double>();

public void run() {
    double sum =0;
    for (int i = begin; i <= end; i++) {            
        sum += i;
    }
    arr.add(sum);
}
public void start() {
    if (t == null) {
        t = new Thread(this, threadName);
        t.start();
    }
}
}

Answer 1

To get the correct result you should modify your program to join the spawned threads (wait till their finish):

// in runnable class:
public void join() throws InterruptedException {
    t.join();
}

// in main:
R1.join();
R2.join();
R3.join();

// Sum of results from all threads:
System.out.println(runnable.arr);
double totalSum = 0; // also use double instead of int here
for (double i : runnable.arr) {
    totalSum += i;
}
long endTime_par = System.currentTimeMillis();

To get the faster result you should remember that starting a new thread is a complex operation which introduces quite big overhead. In contrast summing 3000000 int numbers is very fast. So you unlikely to get any benefit in such a simple test. Commonly the pre-created set of threads is used (called "thread pool") and these threads are just waiting for the new tasks to execute. Such thread pools are managed by executors (see JavaDoc). Also note that measuring the time is not that easy. See this question for more details.

Answer 2

Using Java8

long sumLongStream(LongStream stream) {
    long start = System.nanoTime();
    long sum= stream.sum();
    long end = System.nanoTime();
    return end - start;
}

@Test
public void testSumLong() {
    for (int i = 0; i < 10; ++i) {
        long sequential = sumLongStream(LongStream.range(0, 3000000));
        long parallel = sumLongStream(LongStream.range(0, 3000000).parallel());
        System.out.printf("sequential: %dns parallel: %dns%n", sequential, parallel);
    }
}

results:

sequential: 74134923ns parallel: 69891446ns
sequential: 3471362ns parallel: 1580152ns
sequential: 2865433ns parallel: 1611337ns
sequential: 2820038ns parallel: 1442387ns
sequential: 3113330ns parallel: 1207121ns
sequential: 1982790ns parallel: 1070540ns
sequential: 2370821ns parallel: 1070146ns
sequential: 2210950ns parallel: 1094619ns
sequential: 3575573ns parallel: 1481072ns
sequential: 1979237ns parallel: 1087120ns

Answer 3

Program to sum numbers 0-2999999, and time it:

long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 3000000; i++)
    sum += i;
long end = System.nanoTime();
System.out.println(sum + " in " + (end - start) + "ns");

Output (old Core 2 Duo processor)

4499998500000 in 5869508ns

Or less that 6 milliseconds. It is so fast that simply starting up multiple threads and merging the results will take longer.

And that's without warming up JIT. So I ran to 10 times:

4499998500000 in 5633141ns
4499998500000 in 7538587ns
4499998500000 in 1558147ns
4499998500000 in 1460444ns
4499998500000 in 1399859ns
4499998500000 in 1652866ns
4499998500000 in 1796222ns
4499998500000 in 1796222ns
4499998500000 in 1795795ns
4499998500000 in 1796222ns

Now less than 2 milliseconds.