Why java concurrentmap gives slight difference in calculating doubles using multithread

Question

I am doing matrix multiplication by trying using multi-threads approach, but the calculation between doubles are not always the same for the same matrix. there are the codes:

for the matrix:

private  ConcurrentMap<Position, Double> matrix = new ConcurrentHashMap<>();

  public Matrix_2() {}


  public double get(int row, int column) {
    Position p = new Position(row, column);
    return matrix.getOrDefault(p, 0.0);
  }
  public void set(int row, int column, double num) {
    Position p = new Position(row, column);
    if(matrix.containsKey(p)){
      double a = matrix.get(p);
      a += num;
      matrix.put(p, a);
    }else {
      matrix.put(p, num);
    }
  }

for multiplication

    public static Matrix multiply(Matrix a, Matrix b) {
    List<Thread> threads = new ArrayList<>();
    Matrix c = new Matrix_2();
    IntStream.range(0, a.getNumRows()).forEach(r ->
      IntStream.range(0, a.getNumColumns()).forEach(t ->
          IntStream.range(0, b.getNumColumns())
              .forEach(
                  v -> 
           threads.add(new Thread(() -> c.set(r, v, b.get(t, v) * a.get(r, t)))))
      ));
    threads.forEach(Thread::start);
    threads.forEach(r -> {
        try {
          r.join();
        } catch (InterruptedException e) {
          System.out.println("bad");
        }
      }
    );
    return c;
  }

where get method get the double at specific row and column, get(row, column), and the set method add the given number to the double at that row and column. This code works fine at the integer level but when it comes to double with a lot precision, it will have different answers for the multiplication of same two matrices, sometimes can be as large as 0.5 to 1.5 for a number. Why is that.

Possible duplicate of [Is ConcurrentHashMap.get() guaranteed to see a previous ConcurrentHashMap.put() by different thread?](http://stackoverflow.com/questions/1770166/is-concurrenthashmap-get-guaranteed-to-see-a-previous-concurrenthashmap-put) — Andrei T., Mar 13 '17 at 19:10
Using a ConcurrentMap is a really inefficient way of representing a Matrix unless it is very sparse. Note: your implementation isn't thread safe which is mostly the reason you get different results. — Peter Lawrey, Mar 13 '17 at 19:30

score 2 · Answer 1 · answered Mar 13 '17 at 19:29

While I haven't fully analyzed your code for multiply, and John Bollinger makes a good point (in the comments) regarding the rounding-error inherent to floating-point primitives, your set method would seem to have a possible race condition.

Namely, while your use of java.util.ConcurrentHashMap guarantees thread safety within Map API calls, it does nothing to ensure that the mappings could not have changed in between invocations, such as between the time that you invoke containsKey and the time that you invoke put, or between the time that you invoke get and the time that you invoke put.

As of Java 8 (which your use of lambdas and streams indicates you are using), one option to rectify this problem is to make the check-existing + get + set sequence atomic via the compute API call. compute allows you to provide a key and a lambda (or method reference) specifying how to mutate the value mapped to that key, and ConcurrentHashMap guarantees that the lambda, which encompasses your full check-and-set logic, will be executed atomically. Using that approach, your code would look something like:

public void set(int row, int column, double num) {
    Position p = new Position(row, column);
    matrix.compute(p, (Position positionKey, Double doubleValue)->{
        if (doubleValue == null) {
            return num;
        } else {
            return num + doubleValue;
        }
    });
}

John Bollinger · Accepted Answer · 2017-03-13T19:57:48.013

A concurrent collection can help you write thread-safe code, but it does not make your code automatically thread-safe. And your code -- principally your set() method -- is not thread safe.

In fact, your set() method does not even make sense, at least not under that name. If the implementation is indeed what you intend, then it seems to be more of an increment() method.

My first suggestion would be to simplify your approach by eliminating the middle IntStream, or at least moving it into the threads. The objective here would be to avoid any two threads ever manipulating the same element of the map. You could then also use a bona fide set() method in conjunction, as there would be no contention for individual matrix elements. The ConcurrentMap would still be helpful in that case. Most likely that would run faster, too.

If you must keep the structure of the computation the same, however, then you need a better set() method, one that accounts for the possibility that another thread updates an element between your get() and put(). If you don't account for that then updates can be lost. Something along these lines would be an improvement:

public void increment(int row, int column, double num) {
    Position p = new Position(row, column);
    Double current = matrix.putIfAbsent(p, num);

    if (current != null) {
        // there was already a value at the designated position
        double newval = current + num;

        while (!matrix.replace(p, current, newval)) {
            // Failed to replace -- indicates that the value at the designated
            // position is no longer the one we most recently read
            current = matrix.get(p);
            newval = current + num;
        }
    } // else successfully set the first value for this position
}

That approach will work with any version of Java that provides ConcurrentMap, but of course, other parts of your code already rely on Java 8. The solution offered by @Sumitsu leverages API features that were new in Java 8; it is more elegant than the above, but less illustrative.

Note also that it would not be surprising to see see small differences in your result in any case, because reordering floating-point operations can cause different rounding.

Why java concurrentmap gives slight difference in calculating doubles using multithread

2 Answers2