Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java multi-threaded program using join() gives wrong results in calculating sum of adjacent numbers

I wrote this simple multi-threaded program to add numbers from 1 to 100,000. When I ran this, I got different values as the end result ( values less than expected 5000050000 ). When I executed the program only using one thread, it gave correct result. Program also works for smaller values such as 100. What did possibly go wrong ? Thanks in advance.

class Calculation {

  private long total=0;
  public void calcSum(long start, long end) {
      long i = start;
      for( ;i<=end; i++) {
          total += i;
      }
  }
  public long getTotal() {
     return total;
  }
}

class CalculatorThread extends Thread{
   private long start;
   private long end;
   private Calculation calc;
   public CalculatorThread(long start, long end, Calculation calc) {
       this.start = start;
       this.end = end;
       this.calc = calc;
   }
   @Override
   public void run() {
       calc.calcSum(start, end);
   }
}

public class ParallelTest {

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

      int start = 1;
      int end = 100000;

      Calculation calc = new Calculation();
      CalculatorThread ct1 = new CalculatorThread(start, end/2 , calc);
      CalculatorThread ct2 = new CalculatorThread( (end/2) + 1, end, calc);

      ct1.start();
      ct2.start();

      ct1.join();
      ct2.join();

      System.out.println(calc.getTotal());
  }
}
like image 537
user54321 Avatar asked May 27 '18 22:05

user54321


1 Answers

Unsynchronized access to shared mutable state usually doesn't go well.

In your Calculation calc, there is a mutable variable long total. When you start the threads:

  CalculatorThread ct1 = new CalculatorThread(start, end/2 , calc);
  CalculatorThread ct2 = new CalculatorThread( (end/2) + 1, end, calc);

you share the mutable state of calc between those two threads. There is no synchronization whatsoever inside calc, so the threads will only trash each other's memory in random time intervals.

Here is a working version:

class ParallelSum {
  public static long calcSum(long start, long end) {
      long total = 0;
      for(long i = start; i < end; i++) {
          total += i;
      }
      return total;
  }

  public static class CalculatorThread extends Thread {
     private long result = 0;
     private long start;
     private long end;
     public CalculatorThread(long start, long end) {
         this.start = start;
         this.end = end;
     }
     @Override
     public void run() {
         result = calcSum(start, end);
     }
     public long getResult() {
         return result;
     }
  }

  public static void main(String[] args) throws InterruptedException {
    int start = 1;
    int end = 100000;
    int endExcl = end + 1;

    CalculatorThread ct1 = new CalculatorThread(start, endExcl/2);
    CalculatorThread ct2 = new CalculatorThread(endExcl / 2, endExcl);

    ct1.start();
    ct2.start();

    ct1.join();
    ct2.join();

    System.out.println(ct1.getResult() + ct2.getResult());
  }
}

Outputs:

5000050000

Additional note: always use [inclusive, exclusive) indexing of ranges. This decreases the chance for off-by-one errors dramatically. Also, I've replaced the Calculation class by a method: nothing can go wrong with local variables, inside a method, and the less mutable state there is, the better.

like image 69
Andrey Tyukin Avatar answered Oct 20 '22 18:10

Andrey Tyukin