SieveCache
public final class SieveCache<K extends Object, V extends Object>
SieveCache is an in-memory cache that holds strong references to a limited number of values determined by the cache's maxSize and the size of each value. When a value is added to a full cache, one or more existing values are evicted from the cache using the SIEVE algorithm. Complete details about the algorithm can be found in Zhang et al., 2024, SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches, NSDI'24 (paper).
Contrary to LruCache, SieveCache does not maintain a list of entries based on their access order, but on their insertion order. Eviction candidates are found by keeping track of the "visited" status of each entry. This means that reading a value using get prevents that entry from becoming an eviction candidate. In practice, SieveCache offers better hit ratio compared to LruCache.
The underlying implementation is also designed to avoid all allocations on insertion, removal, retrieval, and iteration. Allocations may still happen on insertion when the underlying storage needs to grow to accommodate newly added entries to the table. In addition, this implementation minimizes memory usage by avoiding the use of separate objects to hold key/value pairs. The implementation follows the implementation of ScatterMap.
By default, the size of the cache is measured in number of entries. The caller can choose the size and size unit of the values by passing their own sizeOf lambda, invoked whenever the cache needs to query the size of a value.
The createValueFromKey lambda can be used to compute values on demand from a key when querying for an entry that does not exist in the cache.
When a cached value is removed, either directly by the caller or via the eviction mechanism, you can use the onEntryRemoved lambda to execute any side effect or perform any necessary cleanup.
This implementation is not thread-safe: if multiple threads access this container concurrently, and one or more threads modify the structure of the map (insertion or removal for instance), the calling code must provide the appropriate synchronization. Multiple threads are safe to read from this map concurrently if no write is happening.
A SieveCache can hold a maximum of Int.MAX_VALUE - 1 entries, independent of their computed size.
Summary
Public constructors |
|---|
<K extends Object, V extends Object> SieveCache(Creates a new |
Public methods |
|
|---|---|
final boolean |
Returns true if all entries match the given |
final boolean |
any()Returns |
final boolean |
Returns true if at least one entry matches the given |
final boolean |
Returns true if the specified |
final boolean |
containsKey(@NonNull K key)Returns true if the specified |
final boolean |
containsValue(@NonNull V value)Returns true if the specified |
final int |
count()Returns the number of entries in this cache. |
final int |
Returns the number of entries matching the given |
boolean |
Compares the specified object |
final void |
evictAll()Removes all the entries from this cache. |
final void |
Iterates over every key/value pair stored in this cache by invoking the specified |
final void |
forEachKey(@NonNull Function1<@NonNull key, Unit> block)Iterates over every key stored in this cache by invoking the specified |
final void |
forEachValue(@NonNull Function1<@NonNull value, Unit> block)Iterates over every value stored in this cache by invoking the specified |
final V |
Returns the value for |
final int |
Returns the number of entries that can be stored in this cache without requiring internal storage reallocation. |
final int |
getCount()Returns the number of elements held in the cache. |
final int |
Return the maximum size of the cache before adding new elements causes existing elements to be evicted. |
final int |
getSize()Size of the cache in the unit defined by the implementation of |
int |
hashCode()Returns the hash code value for this cache. |
final boolean |
isEmpty()Indicates whether this cache is empty. |
final boolean |
Returns |
final void |
minusAssign(@NonNull K key)Removes the specified |
final void |
minusAssign(@NonNull K[] keys)Removes the specified |
final void |
minusAssign(@NonNull Iterable<@NonNull K> keys)Removes the specified |
final void |
minusAssign(@NonNull ObjectList<@NonNull K> keys)Removes the specified |
final void |
minusAssign(@NonNull ScatterSet<@NonNull K> keys)Removes the specified |
final void |
minusAssign(@NonNull Sequence<@NonNull K> keys)Removes the specified |
final boolean |
none()Returns |
final void |
plusAssign(@NonNull Map<@NonNull K, @NonNull V> from)Puts all the key/value mappings in the |
final void |
plusAssign(@NonNull ScatterMap<@NonNull K, @NonNull V> from)Puts all the key/value mappings in the |
final void |
plusAssign(@NonNull SieveCache<@NonNull K, @NonNull V> from)Puts all the key/value mappings in the |
final void |
plusAssign(@NonNull Pair<@NonNull K, @NonNull V> pair)Puts the key/value mapping from the |
final void |
plusAssign(@NonNull Pair[] pairs)Puts all the |
final void |
Puts all the |
final void |
Puts all the |
final V |
|
final void |
Puts all the key/value mappings in the |
final void |
putAll(@NonNull ScatterMap<@NonNull K, @NonNull V> from)Puts all the key/value mappings in the |
final void |
putAll(@NonNull SieveCache<@NonNull K, @NonNull V> from)Puts all the key/value mappings in the |
final void |
Puts all the |
final void |
Puts all the |
final void |
Puts all the |
final V |
Removes the specified |
final boolean |
Removes the specified |
final void |
Removes any mapping for which the specified |
final void |
Sets the maximum size of the cache to |
final void |
|
@NonNull String |
toString() |
final void |
trimToSize(int maxSize)Remove entries until the total size of the remaining entries is less than or equal to |
Public constructors
SieveCache
public <K extends Object, V extends Object> SieveCache(
@IntRange(from = 1, to = 2147483646) int maxSize,
@IntRange(from = 0, to = 2147483646) int initialCapacity,
@NonNull Function2<@NonNull key, @NonNull value, @NonNull Integer> sizeOf,
@NonNull Function1<@NonNull key, V> createValueFromKey,
@NonNull Function4<@NonNull key, @NonNull oldValue, newValue, @NonNull Boolean, Unit> onEntryRemoved
)
Creates a new SieveCache.
| Parameters | |
|---|---|
@IntRange(from = 1, to = 2147483646) int maxSize |
For caches that do not override |
@IntRange(from = 0, to = 2147483646) int initialCapacity |
The initial desired capacity for this cache. The cache will honor this value by guaranteeing its internal structures can hold that many entries without requiring any allocations. The initial capacity can be set to 0. |
@NonNull Function2<@NonNull key, @NonNull value, @NonNull Integer> sizeOf |
Returns the size of the entry for the specified key and value. The size of an entry cannot change after it was added to the cache, and must be >= 0. |
@NonNull Function1<@NonNull key, V> createValueFromKey |
Called after a cache miss to compute a value for the specified key. Returning null from this lambda indicates that no value can be computed. |
@NonNull Function4<@NonNull key, @NonNull oldValue, newValue, @NonNull Boolean, Unit> onEntryRemoved |
Called for entries that have been removed by the user of the cache, or automatically evicted. The lambda is supplied with multiple parameters. The |
Public methods
all
public final boolean all(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)
Returns true if all entries match the given predicate.
any
public final boolean any(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)
Returns true if at least one entry matches the given predicate.
contains
public final boolean contains(@NonNull K key)
Returns true if the specified key is present in this cache, false otherwise.
containsKey
public final boolean containsKey(@NonNull K key)
Returns true if the specified key is present in this cache, false otherwise.
containsValue
public final boolean containsValue(@NonNull V value)
Returns true if the specified value is present in this hash map, false otherwise.
count
public final int count(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)
Returns the number of entries matching the given predicate.
equals
public boolean equals(Object other)
Compares the specified object other with this cache for equality. The two objects are considered equal if other:
-
Is a
SieveCache -
Contains key/value pairs equal to this cache's pair
evictAll
public final void evictAll()
Removes all the entries from this cache. Upon each removal, onEntryRemoved is invoked with the evicted parameter set to true.
forEach
public final void forEach(@NonNull Function2<@NonNull key, @NonNull value, Unit> block)
Iterates over every key/value pair stored in this cache by invoking the specified block lambda. The iteration order is not specified.
NOTE: Iterating over the content of the cache does not mark entries as recently visited, and therefore does not affect which entries get evicted first.
forEachKey
public final void forEachKey(@NonNull Function1<@NonNull key, Unit> block)
Iterates over every key stored in this cache by invoking the specified block lambda.
NOTE: Iterating over the content of the cache does not mark entries as recently visited, and therefore does not affect which entries get evicted first.
forEachValue
public final void forEachValue(@NonNull Function1<@NonNull value, Unit> block)
Iterates over every value stored in this cache by invoking the specified block lambda.
NOTE: Iterating over the content of the cache does not mark entries as recently visited, and therefore does not affect which entries get evicted first.
get
public final V get(@NonNull K key)
Returns the value for key if it exists in the cache or can be created by createValueFromKey. Return null if a value is not present in the cache and cannot be created.
getCapacity
public final int getCapacity()
Returns the number of entries that can be stored in this cache without requiring internal storage reallocation.
| See also | |
|---|---|
count |
getCount
public final int getCount()
Returns the number of elements held in the cache.
| See also | |
|---|---|
capacity |
getMaxSize
public final int getMaxSize()
Return the maximum size of the cache before adding new elements causes existing elements to be evicted. The unit of maxSize is defined by the implementation of sizeOf. Using the default implementation of sizeOf, maxSize indicates the a maximum number of elements.
| See also | |
|---|---|
size |
getSize
public final int getSize()
Size of the cache in the unit defined by the implementation of sizeOf (by default, the number of elements).
| See also | |
|---|---|
maxSize |
hashCode
public int hashCode()
Returns the hash code value for this cache. The hash code the sum of the hash codes of each key/value pair.
isNotEmpty
public final boolean isNotEmpty()
Returns true if this cache is not empty.
minusAssign
public final void minusAssign(@NonNull K key)
Removes the specified key and its associated value from the map.
minusAssign
public final void minusAssign(@NonNull K[] keys)
Removes the specified keys and their associated value from the map.
minusAssign
public final void minusAssign(@NonNull Iterable<@NonNull K> keys)
Removes the specified keys and their associated value from the map.
minusAssign
public final void minusAssign(@NonNull ObjectList<@NonNull K> keys)
Removes the specified keys and their associated value from the map.
minusAssign
public final void minusAssign(@NonNull ScatterSet<@NonNull K> keys)
Removes the specified keys and their associated value from the map.
minusAssign
public final void minusAssign(@NonNull Sequence<@NonNull K> keys)
Removes the specified keys and their associated value from the map.
plusAssign
public final void plusAssign(@NonNull Map<@NonNull K, @NonNull V> from)
Puts all the key/value mappings in the from map into this map. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
plusAssign
public final void plusAssign(@NonNull ScatterMap<@NonNull K, @NonNull V> from)
Puts all the key/value mappings in the from map into this map. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
plusAssign
public final void plusAssign(@NonNull SieveCache<@NonNull K, @NonNull V> from)
Puts all the key/value mappings in the from map into this map. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
plusAssign
public final void plusAssign(@NonNull Pair<@NonNull K, @NonNull V> pair)
Puts the key/value mapping from the pair in this cache, using the first element as the key, and the second element as the value. See put for more details about the insertion behavior.
plusAssign
public final void plusAssign(@NonNull Pair[] pairs)
Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value. Calling this * method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
plusAssign
public final void plusAssign(@NonNull Iterable<@NonNull Pair<@NonNull K, @NonNull V>> pairs)
Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value. Calling this * method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
plusAssign
public final void plusAssign(@NonNull Sequence<@NonNull Pair<@NonNull K, @NonNull V>> pairs)
Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value. Calling this * method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
put
public final V put(@NonNull K key, @NonNull V value)
Adds value to the cache using the specific key. If key is already present in the map, the association is modified and the previously associated value is replaced with value. If key is not present, a new entry is added to the map. If an existing value is replaced, onEntryRemoved will be invoked with the evicted parameter set to false.
When value is added to the cache, sizeOf is invoked to query its size. If the total size of the cache, including the new value's size, is greater than maxSize, existing entries will be evicted. On each removal due to an eviction, onEntryRemoved will be invoked with the evicted parameter set to true.
Return the previous value associated with the key, or null if the key was not present in the cache.
putAll
public final void putAll(@NonNull Map<@NonNull K, @NonNull V> from)
Puts all the key/value mappings in the from map into this cache. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
putAll
public final void putAll(@NonNull ScatterMap<@NonNull K, @NonNull V> from)
Puts all the key/value mappings in the from map into this cache. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
putAll
public final void putAll(@NonNull SieveCache<@NonNull K, @NonNull V> from)
Puts all the key/value mappings in the from cache into this cache. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
putAll
public final void putAll(@NonNull Pair[] pairs)
Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
putAll
public final void putAll(@NonNull Iterable<@NonNull Pair<@NonNull K, @NonNull V>> pairs)
Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
putAll
public final void putAll(@NonNull Sequence<@NonNull Pair<@NonNull K, @NonNull V>> pairs)
Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.
remove
public final V remove(@NonNull K key)
Removes the specified key and its associated value from the cache. If the key was present in the cache, this function returns the value that was present before removal, otherwise it returns null. On successful removal, sizeOf will be invoked to query the size of the removed element, and onEntryRemoved will be invoked with the evicted parameter set to false.
remove
public final boolean remove(@NonNull K key, @NonNull V value)
Removes the specified key and its associated value from the cache if the associated value equals value. If the key was present in the cache, this function returns true, otherwise it returns false. On successful removal, sizeOf will be invoked to query the size of the removed element, and onEntryRemoved will be invoked with the evicted parameter set to false.
removeIf
public final void removeIf(
@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate
)
Removes any mapping for which the specified predicate returns true.
resize
public final void resize(@IntRange(from = 1, to = 2147483646) int maxSize)
Sets the maximum size of the cache to maxSize, in the unit defined by the implementation of sizeOf. The size must be strictly greater than 0. If the current total size of the entries in the cache is greater than the new maxSize, entries will be removed until the total size is less than or equal to maxSize. Upon each removal, onEntryRemoved is invoked with the evicted parameter set to true.
set
public final void set(@NonNull K key, @NonNull V value)
Adds value to the cache using the specific key. If key is already present in the cache, the association is modified and the previously associated value is replaced with value. If key is not present, a new entry is added to the map. If an existing value is replaced, onEntryRemoved will be invoked with the evicted parameter set to false.
When value is added to the cache, sizeOf is invoked to query its size. If the total size of the cache, including the new value's size, is greater than maxSize, existing entries will be evicted. On each removal due to an eviction, onEntryRemoved will be invoked with the evicted parameter set to true.
trimToSize
public final void trimToSize(int maxSize)
Remove entries until the total size of the remaining entries is less than or equal to maxSize. The size of the entries is defined by the implementation of sizeOf. Upon each removal, onEntryRemoved is invoked with the evicted parameter set to true.
If maxSize is set to -1 (or any negative value), all entries are removed.