Java Reference
In-Depth Information
each other; common optimizations such as caching frequently computed values can introduce
“hot fields” that limit scalability.
If you were implementing
HashMap
, you would have a choice of how
size
computes the
number of entries in the
Map
. The simplest approach is to count the number of entries every
time it is called. A common optimization is to update a separate counter as entries are ad-
ded or removed; this slightly increases the cost of a
put
or
remove
operation to keep the
counter up-to-date, but reduces the cost of the
size
operation from
O
(
n
) to
O
(1).
Keeping a separate count to speed up operations like
size
and
isEmpty
works fine for a
single-threaded or fully synchronized implementation, but makes it much harder to improve
the scalability of the implementation because every operation that modifies the map must
now update the shared counter. Even if you use lock striping for the hash chains, synchron-
izing access to the counter reintroduces the scalability problems of exclusive locking. What
looked like a performance optimization—caching the results of the
size
operation—has
turned into a scalability liability. In this case, the counter is called a
hot field
because every
mutative operation needs to access it.
ConcurrentHashMap
avoids this problem by having
size
enumerate the stripes and add
up the number of elements in each stripe, instead of maintaining a global count. To avoid enu-
merating every element,
ConcurrentHashMap
maintains a separate count field for each
stripe, also guarded by the stripe lock.
[12]
11.4.5. Alternatives to Exclusive Locks
A third technique for mitigating the effect of lock contention is to forego the use of exclusive
locks in favor of a more concurrency-friendly means of managing shared state. These include
using the concurrent collections, read-write locks, immutable objects and atomic variables.
ReadWriteLock
(see
Chapter 13
) enforces a multiple-reader, single-writer locking discip-
line: more than one reader can access the shared resource concurrently so long as none of
them wants to modify it, but writers must acquire the lock excusively. For read-mostly data
structures,
ReadWriteLock
can offer greater concurrency than exclusive locking; for read-
only data structures, immutability can eliminate the need for locking entirely.
Atomic variables (see
Chapter 15
)
offer a means of reducing the cost of updating “hot fields”
such as statistics counters, sequence generators, or the reference to the first node in a linked
data structure. (We used
AtomicLong
to maintain the hit counter in the servlet examples in