Why can't Java Concurrency In Practice listing 5.18 be done atomically with a lock?

Question

In Java Concurrency in Practice, on page 106, it says " Memoizer3 is vulnerable to the problem [two threads seeing null and starting expensive computation] because a compound action (put-if-absent) is performed on the backing map that cannot be made atomic using locking." I don't understand why they say it cannot be made atomic using locking. Here is the original code:

package net.jcip.examples;

import java.util.*;
import java.util.concurrent.*;

/**
 * Memoizer3
 * <p/>
 * Memoizing wrapper using FutureTask
 *
 * @author Brian Goetz and Tim Peierls
 */
public class Memoizer3 <A, V> implements Computable<A, V> {
    private final Map<A, Future<V>> cache
        = new ConcurrentHashMap<A, Future<V>>();
    private final Computable<A, V> c;

    public Memoizer3(Computable<A, V> c) {
        this.c = c;
    }

    public V compute(final A arg) throws InterruptedException {
        Future<V> f = cache.get(arg);
        if (f == null) {
            Callable<V> eval = new Callable<V>() {
                public V call() throws InterruptedException {
                    return c.compute(arg);
                }
            };
            FutureTask<V> ft = new FutureTask<V>(eval);
            f = ft;
            cache.put(arg, ft);
            ft.run(); // call to c.compute happens here
        }
        try {
            return f.get();
        } catch (ExecutionException e) {
            throw LaunderThrowable.launderThrowable(e.getCause());
        }
    }
}

Why wouldn't something like this work?

...
public V compute(final A arg) throws InterruptedException {
    Future<V> f = null;
    FutureTask<V> ft = null;
    synchronized(this){
        f = cache.get(arg);
        if (f == null) {
            Callable<V> eval = new Callable<V>() {
                public V call() throws InterruptedException {
                    return c.compute(arg);
                }
             };
             ft = new FutureTask<V>(eval);
             f = ft;
             cache.put(arg, ft);                 
        }
    }
    if (f==ft) ft.run(); // call to c.compute happens here
    ...

Answer 1

It of course can be made atomic by using locking, imagine the most primitive case: you have a global lock around your entire function, then everything is single-threaded and therefore thread-safe. I assume that either they meant something else or there was a general misunderstanding.

Your code could even be improved by using the putIfAbsent method of ConcurrentHashMap like this:

public V compute(final A arg) throws InterruptedException {
  Future<V> f = cache.get(arg);
  if (f == null) {
    final Callable<V> eval = new Callable<V>() {
      public V call() throws InterruptedException {
        return c.compute(arg);
      }
    };
    final FutureTask<V> ft = new FutureTask<V>(eval);
    final Future<V> previousF = cache.putIfAbsent(arg, ft);
    if (previousF == null) {
      f = ft;
      ft.run(); 
    } else {
      f = previousF; // someone else will do the compute
    } 
  }
  return f.get();
}

f will at the end either be a previous value that has been added in between or the initial value, at the potential cost of an extra creation of a Callable, but no call to compute is done more than once.