Class Striped<L>
- java.lang.Object
-
- com.google.common.util.concurrent.Striped<L>
-
- Direct Known Subclasses:
Striped.PowerOfTwoStriped
@Beta @GwtIncompatible public abstract class Striped<L> extends java.lang.Object
A stripedLock/Semaphore/ReadWriteLock
. This offers the underlying lock striping similar to that ofConcurrentHashMap
in a reusable form, and extends it for semaphores and read-write locks. Conceptually, lock striping is the technique of dividing a lock into many stripes, increasing the granularity of a single lock and allowing independent operations to lock different stripes and proceed concurrently, instead of creating contention for a single lock.The guarantee provided by this class is that equal keys lead to the same lock (or semaphore), i.e.
if (key1.equals(key2))
thenstriped.get(key1) == striped.get(key2)
(assumingObject.hashCode()
is correctly implemented for the keys). Note that ifkey1
is not equal tokey2
, it is not guaranteed thatstriped.get(key1) != striped.get(key2)
; the elements might nevertheless be mapped to the same lock. The lower the number of stripes, the higher the probability of this happening.There are three flavors of this class:
Striped<Lock>
,Striped<Semaphore>
, andStriped<ReadWriteLock>
. For each type, two implementations are offered: strong and weakStriped<Lock>
, strong and weakStriped<Semaphore>
, and strong and weakStriped<ReadWriteLock>
. Strong means that all stripes (locks/semaphores) are initialized eagerly, and are not reclaimed unlessStriped
itself is reclaimable. Weak means that locks/semaphores are created lazily, and they are allowed to be reclaimed if nobody is holding on to them. This is useful, for example, if one wants to create aStriped<Lock>
of many locks, but worries that in most cases only a small portion of these would be in use.Prior to this class, one might be tempted to use
Map<K, Lock>
, whereK
represents the task. This maximizes concurrency by having each unique key mapped to a unique lock, but also maximizes memory footprint. On the other extreme, one could use a single lock for all tasks, which minimizes memory footprint but also minimizes concurrency. Instead of choosing either of these extremes,Striped
allows the user to trade between required concurrency and memory footprint. For example, if a set of tasks are CPU-bound, one could easily create a very compactStriped<Lock>
ofavailableProcessors() * 4
stripes, instead of possibly thousands of locks which could be created in aMap<K, Lock>
structure.- Since:
- 13.0
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
Striped.CompactStriped<L>
Implementation of Striped where 2^k stripes are represented as an array of the same length, eagerly initialized.(package private) static class
Striped.LargeLazyStriped<L>
Implementation of Striped where up to 2^k stripes can be represented, using a ConcurrentMap where the key domain is [0..2^k).private static class
Striped.PaddedLock
private static class
Striped.PaddedSemaphore
private static class
Striped.PowerOfTwoStriped<L>
(package private) static class
Striped.SmallLazyStriped<L>
Implementation of Striped where up to 2^k stripes can be represented, using an AtomicReferenceArray of size 2^k.
-
Field Summary
Fields Modifier and Type Field Description private static int
ALL_SET
A bit mask were all bits are set.private static int
LARGE_LAZY_CUTOFF
If there are at least this many stripes, we assume the memory usage of a ConcurrentMap will be smaller than a large array.private static Supplier<java.util.concurrent.locks.ReadWriteLock>
READ_WRITE_LOCK_SUPPLIER
-
Constructor Summary
Constructors Modifier Constructor Description private
Striped()
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description java.lang.Iterable<L>
bulkGet(java.lang.Iterable<?> keys)
Returns the stripes that correspond to the passed objects, in ascending (as pergetAt(int)
) order.private static int
ceilToPowerOfTwo(int x)
abstract L
get(java.lang.Object key)
Returns the stripe that corresponds to the passed key.abstract L
getAt(int index)
Returns the stripe at the specified index.(package private) abstract int
indexFor(java.lang.Object key)
Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key).private static <L> Striped<L>
lazy(int stripes, Supplier<L> supplier)
static Striped<java.util.concurrent.locks.Lock>
lazyWeakLock(int stripes)
Creates aStriped<Lock>
with lazily initialized, weakly referenced locks.static Striped<java.util.concurrent.locks.ReadWriteLock>
lazyWeakReadWriteLock(int stripes)
Creates aStriped<ReadWriteLock>
with lazily initialized, weakly referenced read-write locks.static Striped<java.util.concurrent.Semaphore>
lazyWeakSemaphore(int stripes, int permits)
Creates aStriped<Semaphore>
with lazily initialized, weakly referenced semaphores, with the specified number of permits.static Striped<java.util.concurrent.locks.Lock>
lock(int stripes)
Creates aStriped<Lock>
with eagerly initialized, strongly referenced locks.static Striped<java.util.concurrent.locks.ReadWriteLock>
readWriteLock(int stripes)
Creates aStriped<ReadWriteLock>
with eagerly initialized, strongly referenced read-write locks.static Striped<java.util.concurrent.Semaphore>
semaphore(int stripes, int permits)
Creates aStriped<Semaphore>
with eagerly initialized, strongly referenced semaphores, with the specified number of permits.abstract int
size()
Returns the total number of stripes in this instance.private static int
smear(int hashCode)
-
-
-
Field Detail
-
LARGE_LAZY_CUTOFF
private static final int LARGE_LAZY_CUTOFF
If there are at least this many stripes, we assume the memory usage of a ConcurrentMap will be smaller than a large array. (This assumes that in the lazy case, most stripes are unused. As always, if many stripes are in use, a non-lazy striped makes more sense.)- See Also:
- Constant Field Values
-
READ_WRITE_LOCK_SUPPLIER
private static final Supplier<java.util.concurrent.locks.ReadWriteLock> READ_WRITE_LOCK_SUPPLIER
-
ALL_SET
private static final int ALL_SET
A bit mask were all bits are set.- See Also:
- Constant Field Values
-
-
Method Detail
-
get
public abstract L get(java.lang.Object key)
Returns the stripe that corresponds to the passed key. It is always guaranteed that ifkey1.equals(key2)
, thenget(key1) == get(key2)
.- Parameters:
key
- an arbitrary, non-null key- Returns:
- the stripe that the passed key corresponds to
-
getAt
public abstract L getAt(int index)
Returns the stripe at the specified index. Valid indexes are 0, inclusively, tosize()
, exclusively.- Parameters:
index
- the index of the stripe to return; must be in[0...size())
- Returns:
- the stripe at the specified index
-
indexFor
abstract int indexFor(java.lang.Object key)
Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key).
-
size
public abstract int size()
Returns the total number of stripes in this instance.
-
bulkGet
public java.lang.Iterable<L> bulkGet(java.lang.Iterable<?> keys)
Returns the stripes that correspond to the passed objects, in ascending (as pergetAt(int)
) order. Thus, threads that use the stripes in the order returned by this method are guaranteed to not deadlock each other.It should be noted that using a
Striped<L>
with relatively few stripes, andbulkGet(keys)
with a relative large number of keys can cause an excessive number of shared stripes (much like the birthday paradox, where much fewer than anticipated birthdays are needed for a pair of them to match). Please consider carefully the implications of the number of stripes, the intended concurrency level, and the typical number of keys used in abulkGet(keys)
operation. See Balls in Bins model for mathematical formulas that can be used to estimate the probability of collisions.- Parameters:
keys
- arbitrary non-null keys- Returns:
- the stripes corresponding to the objects (one per each object, derived by delegating to
get(Object)
; may contain duplicates), in an increasing index order.
-
lock
public static Striped<java.util.concurrent.locks.Lock> lock(int stripes)
Creates aStriped<Lock>
with eagerly initialized, strongly referenced locks. Every lock is reentrant.- Parameters:
stripes
- the minimum number of stripes (locks) required- Returns:
- a new
Striped<Lock>
-
lazyWeakLock
public static Striped<java.util.concurrent.locks.Lock> lazyWeakLock(int stripes)
Creates aStriped<Lock>
with lazily initialized, weakly referenced locks. Every lock is reentrant.- Parameters:
stripes
- the minimum number of stripes (locks) required- Returns:
- a new
Striped<Lock>
-
semaphore
public static Striped<java.util.concurrent.Semaphore> semaphore(int stripes, int permits)
Creates aStriped<Semaphore>
with eagerly initialized, strongly referenced semaphores, with the specified number of permits.- Parameters:
stripes
- the minimum number of stripes (semaphores) requiredpermits
- the number of permits in each semaphore- Returns:
- a new
Striped<Semaphore>
-
lazyWeakSemaphore
public static Striped<java.util.concurrent.Semaphore> lazyWeakSemaphore(int stripes, int permits)
Creates aStriped<Semaphore>
with lazily initialized, weakly referenced semaphores, with the specified number of permits.- Parameters:
stripes
- the minimum number of stripes (semaphores) requiredpermits
- the number of permits in each semaphore- Returns:
- a new
Striped<Semaphore>
-
readWriteLock
public static Striped<java.util.concurrent.locks.ReadWriteLock> readWriteLock(int stripes)
Creates aStriped<ReadWriteLock>
with eagerly initialized, strongly referenced read-write locks. Every lock is reentrant.- Parameters:
stripes
- the minimum number of stripes (locks) required- Returns:
- a new
Striped<ReadWriteLock>
-
lazyWeakReadWriteLock
public static Striped<java.util.concurrent.locks.ReadWriteLock> lazyWeakReadWriteLock(int stripes)
Creates aStriped<ReadWriteLock>
with lazily initialized, weakly referenced read-write locks. Every lock is reentrant.- Parameters:
stripes
- the minimum number of stripes (locks) required- Returns:
- a new
Striped<ReadWriteLock>
-
ceilToPowerOfTwo
private static int ceilToPowerOfTwo(int x)
-
smear
private static int smear(int hashCode)
-
-