Building Blocks - Java Concurrency in Practice - page 121

compute method. This ensures thread safety but has an obvious scalability problem: only
one thread at a time can execute compute at all. If another thread is busy computing a
result, other threads calling compute may be blocked for a long time. If multiple threads
are queued up waiting to compute values not already computed, compute may actually take
longer than it would have without memoization. Figure 5.2 illustrates what could happen
when several threads attempt to use a function memoized with this approach. This is not the
sort of performance improvement we had hoped to achieve through caching.
Figure 5.2. Poor Concurrency of Memoizer1 .
Memoizer2 in Listing 5.17 improves on the awful concurrent behavior of Memoizer1 by
replacing the HashMap with a ConcurrentHashMap . Since ConcurrentHashMap is
thread-safe, there is no need to synchronize when accessing the backing Map , thus eliminat-
ing the serialization induced by synchronizing compute in Memoizer1 .
Memoizer2 certainly has better concurrent behavior than Memoizer1 : multiple threads
can actually use it concurrently. But it still has some defects as a cache—there is a window
of vulnerability in which two threads calling compute at the same time could end up com-
puting the same value. In the case of memoization, this is merely inefficient—the purpose of
a cache is to prevent the same data from being calculated multiple times. For a more general-
purpose caching mechanism, it is far worse; for an object cache that is supposed to provide
once-and-only-once initialization, this vulnerability would also pose a safety risk.
The problem with Memoizer2 is that if one thread starts an expensive computation, other
threads are not aware that the computation is in progress and so may start the same computa-
tion, as illustrated in Figure 5.3 . We'd like to somehow represent the notion that “thread X is
currently computing f (27)”, so that if another thread arrives looking for f (27), it knows that