SieveCache
-
Cmn
class SieveCache<K : Any, V : Any>
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 : Any, V : Any> SieveCache(Creates a new |
Cmn
|
Public functions |
||
|---|---|---|
inline Boolean |
Returns true if all entries match the given |
Cmn
|
Boolean |
any()Returns |
Cmn
|
inline Boolean |
Returns true if at least one entry matches the given |
Cmn
|
operator Boolean |
contains(key: K)Returns true if the specified |
Cmn
|
Boolean |
containsKey(key: K)Returns true if the specified |
Cmn
|
Boolean |
containsValue(value: V)Returns true if the specified |
Cmn
|
Int |
count()Returns the number of entries in this cache. |
Cmn
|
inline Int |
Returns the number of entries matching the given |
Cmn
|
open operator Boolean |
Compares the specified object |
Cmn
|
Unit |
evictAll()Removes all the entries from this cache. |
Cmn
|
inline Unit |
Iterates over every key/value pair stored in this cache by invoking the specified |
Cmn
|
inline Unit |
forEachKey(block: (key) -> Unit)Iterates over every key stored in this cache by invoking the specified |
Cmn
|
inline Unit |
forEachValue(block: (value) -> Unit)Iterates over every value stored in this cache by invoking the specified |
Cmn
|
operator V? |
get(key: K)Returns the value for |
Cmn
|
open Int |
hashCode()Returns the hash code value for this cache. |
Cmn
|
Boolean |
isEmpty()Indicates whether this cache is empty. |
Cmn
|
Boolean |
Returns |
Cmn
|
inline operator Unit |
minusAssign(key: K)Removes the specified |
Cmn
|
inline operator Unit |
minusAssign(keys: Array<K>)Removes the specified |
Cmn
|
inline operator Unit |
minusAssign(keys: Iterable<K>)Removes the specified |
Cmn
|
inline operator Unit |
minusAssign(keys: ObjectList<K>)Removes the specified |
Cmn
|
inline operator Unit |
minusAssign(keys: ScatterSet<K>)Removes the specified |
Cmn
|
inline operator Unit |
minusAssign(keys: Sequence<K>)Removes the specified |
Cmn
|
Boolean |
none()Returns |
Cmn
|
inline operator Unit |
plusAssign(from: Map<K, V>)Puts all the key/value mappings in the |
Cmn
|
inline operator Unit |
plusAssign(from: ScatterMap<K, V>)Puts all the key/value mappings in the |
Cmn
|
inline operator Unit |
plusAssign(from: SieveCache<K, V>)Puts all the key/value mappings in the |
Cmn
|
inline operator Unit |
plusAssign(pair: Pair<K, V>)Puts the key/value mapping from the |
Cmn
|
inline operator Unit |
plusAssign(pairs: Array<Pair<K, V>>)Puts all the |
Cmn
|
inline operator Unit |
plusAssign(pairs: Iterable<Pair<K, V>>)Puts all the |
Cmn
|
inline operator Unit |
plusAssign(pairs: Sequence<Pair<K, V>>)Puts all the |
Cmn
|
V? |
put(key: K, value: V) |
Cmn
|
Unit |
Puts all the key/value mappings in the |
Cmn
|
Unit |
putAll(from: ScatterMap<K, V>)Puts all the key/value mappings in the |
Cmn
|
Unit |
putAll(from: SieveCache<K, V>)Puts all the key/value mappings in the |
Cmn
|
Unit |
Puts all the |
Cmn
|
Unit |
Puts all the |
Cmn
|
Unit |
Puts all the |
Cmn
|
V? |
remove(key: K)Removes the specified |
Cmn
|
Boolean |
remove(key: K, value: V)Removes the specified |
Cmn
|
Unit |
Removes any mapping for which the specified |
Cmn
|
Unit |
Sets the maximum size of the cache to |
Cmn
|
inline operator Unit |
set(key: K, value: V) |
Cmn
|
open String |
toString() |
Cmn
|
Unit |
trimToSize(maxSize: Int)Remove entries until the total size of the remaining entries is less than or equal to |
Cmn
|
Public properties |
||
|---|---|---|
Int |
Returns the number of entries that can be stored in this cache without requiring internal storage reallocation. |
Cmn
|
Int |
Returns the number of elements held in the cache. |
Cmn
|
Int |
Return the maximum size of the cache before adding new elements causes existing elements to be evicted. |
Cmn
|
Int |
Size of the cache in the unit defined by the implementation of |
Cmn
|
Public constructors
SieveCache
<K : Any, V : Any> SieveCache(
maxSize: @IntRange(from = 1, to = 2147483646) Int,
initialCapacity: @IntRange(from = 0, to = 2147483646) Int = DefaultScatterCapacity,
sizeOf: (key, value) -> Int = { _, _ -> 1 },
createValueFromKey: (key) -> V? = { null },
onEntryRemoved: (key, oldValue, newValue?, evicted: Boolean) -> Unit = { _, _, _, _ -> }
)
Creates a new SieveCache.
| Parameters | |
|---|---|
maxSize: @IntRange(from = 1, to = 2147483646) Int |
For caches that do not override |
initialCapacity: @IntRange(from = 0, to = 2147483646) Int = DefaultScatterCapacity |
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. |
sizeOf: (key, value) -> Int = { _, _ -> 1 } |
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. |
createValueFromKey: (key) -> V? = { null } |
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. |
onEntryRemoved: (key, oldValue, newValue?, evicted: Boolean) -> Unit = { _, _, _, _ ->
} |
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 functions
all
inline fun all(predicate: (K, V) -> Boolean): Boolean
Returns true if all entries match the given predicate.
any
inline fun any(predicate: (K, V) -> Boolean): Boolean
Returns true if at least one entry matches the given predicate.
contains
operator fun contains(key: K): Boolean
Returns true if the specified key is present in this cache, false otherwise.
containsKey
fun containsKey(key: K): Boolean
Returns true if the specified key is present in this cache, false otherwise.
containsValue
fun containsValue(value: V): Boolean
Returns true if the specified value is present in this hash map, false otherwise.
count
inline fun count(predicate: (K, V) -> Boolean): Int
Returns the number of entries matching the given predicate.
equals
open operator fun equals(other: Any?): Boolean
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
fun evictAll(): Unit
Removes all the entries from this cache. Upon each removal, onEntryRemoved is invoked with the evicted parameter set to true.
forEach
inline fun forEach(block: (key, value) -> Unit): Unit
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
inline fun forEachKey(block: (key) -> Unit): Unit
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
inline fun forEachValue(block: (value) -> Unit): Unit
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
operator fun get(key: K): V?
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.
hashCode
open fun hashCode(): Int
Returns the hash code value for this cache. The hash code the sum of the hash codes of each key/value pair.
minusAssign
inline operator fun minusAssign(key: K): Unit
Removes the specified key and its associated value from the map.
minusAssign
inline operator fun minusAssign(keys: Array<K>): Unit
Removes the specified keys and their associated value from the map.
minusAssign
inline operator fun minusAssign(keys: Iterable<K>): Unit
Removes the specified keys and their associated value from the map.
minusAssign
inline operator fun minusAssign(keys: ObjectList<K>): Unit
Removes the specified keys and their associated value from the map.
minusAssign
inline operator fun minusAssign(keys: ScatterSet<K>): Unit
Removes the specified keys and their associated value from the map.
minusAssign
inline operator fun minusAssign(keys: Sequence<K>): Unit
Removes the specified keys and their associated value from the map.
plusAssign
inline operator fun plusAssign(from: Map<K, V>): Unit
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
inline operator fun plusAssign(from: ScatterMap<K, V>): Unit
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
inline operator fun plusAssign(from: SieveCache<K, V>): Unit
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
inline operator fun plusAssign(pair: Pair<K, V>): Unit
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
inline operator fun plusAssign(pairs: Array<Pair<K, V>>): Unit
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
inline operator fun plusAssign(pairs: Iterable<Pair<K, V>>): Unit
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
inline operator fun plusAssign(pairs: Sequence<Pair<K, V>>): Unit
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
fun put(key: K, value: V): V?
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
fun putAll(from: Map<K, V>): Unit
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
fun putAll(from: ScatterMap<K, V>): Unit
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
fun putAll(from: SieveCache<K, V>): Unit
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
fun putAll(pairs: Array<Pair<K, V>>): Unit
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
fun putAll(pairs: Iterable<Pair<K, V>>): Unit
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
fun putAll(pairs: Sequence<Pair<K, V>>): Unit
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
fun remove(key: K): V?
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
fun remove(key: K, value: V): Boolean
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
fun removeIf(predicate: (K, V) -> Boolean): Unit
Removes any mapping for which the specified predicate returns true.
resize
fun resize(maxSize: @IntRange(from = 1, to = 2147483646) Int): Unit
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
inline operator fun set(key: K, value: V): Unit
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
fun trimToSize(maxSize: Int): Unit
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.
Public properties
capacity
val capacity: Int
Returns the number of entries that can be stored in this cache without requiring internal storage reallocation.
| See also | |
|---|---|
count |
maxSize
val maxSize: Int
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 |