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(
    maxSize: @IntRange(from = 1, to = 2147483646) Int,
    initialCapacity: @IntRange(from = 0, to = 2147483646) Int,
    sizeOf: (key, value) -> Int,
    createValueFromKey: (key) -> V?,
    onEntryRemoved: (key, oldValue, newValue?, evicted: Boolean) -> Unit
)

Creates a new SieveCache.
Cmn

Public functions
inline Boolean
all(predicate: (K, V) -> Boolean)

Returns true if all entries match the given predicate.
Cmn
Boolean
any()

Returns true if this cache has at least one entry.
Cmn
inline Boolean
any(predicate: (K, V) -> Boolean)

Returns true if at least one entry matches the given predicate.
Cmn
operator Boolean
contains(key: K)

Returns true if the specified key is present in this cache, false otherwise.
Cmn
Boolean
containsKey(key: K)

Returns true if the specified key is present in this cache, false otherwise.
Cmn
Boolean
containsValue(value: V)

Returns true if the specified value is present in this hash map, false otherwise.
Cmn
Int

Returns the number of entries in this cache.
Cmn
inline Int
count(predicate: (K, V) -> Boolean)

Returns the number of entries matching the given predicate.
Cmn
open operator Boolean
equals(other: Any?)

Compares the specified object other with this cache for equality.
Cmn
Unit

Removes all the entries from this cache.
Cmn
inline Unit
forEach(block: (key, value) -> Unit)

Iterates over every key/value pair stored in this cache by invoking the specified block lambda.
Cmn
inline Unit
forEachKey(block: (key) -> Unit)

Iterates over every key stored in this cache by invoking the specified block lambda.
Cmn
inline Unit
forEachValue(block: (value) -> Unit)

Iterates over every value stored in this cache by invoking the specified block lambda.
Cmn
operator V?
get(key: K)

Returns the value for key if it exists in the cache or can be created by createValueFromKey.
Cmn
open Int

Returns the hash code value for this cache.
Cmn
Boolean

Indicates whether this cache is empty.
Cmn
Boolean

Returns true if this cache is not empty.
Cmn
inline operator Unit
minusAssign(key: K)

Removes the specified key and its associated value from the map.
Cmn
inline operator Unit
minusAssign(keys: Array<K>)

Removes the specified keys and their associated value from the map.
Cmn
inline operator Unit

Removes the specified keys and their associated value from the map.
Cmn
inline operator Unit

Removes the specified keys and their associated value from the map.
Cmn
inline operator Unit

Removes the specified keys and their associated value from the map.
Cmn
inline operator Unit

Removes the specified keys and their associated value from the map.
Cmn
Boolean

Returns true if this cache has no entries.
Cmn
inline operator Unit
plusAssign(from: Map<K, V>)

Puts all the key/value mappings in the from map into this map.
Cmn
inline operator Unit
plusAssign(from: ScatterMap<K, V>)

Puts all the key/value mappings in the from map into this map.
Cmn
inline operator Unit
plusAssign(from: SieveCache<K, V>)

Puts all the key/value mappings in the from map into this map.
Cmn
inline operator Unit
plusAssign(pair: Pair<K, V>)

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.
Cmn
inline operator Unit
plusAssign(pairs: Array<Pair<K, V>>)

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value.
Cmn
inline operator Unit
plusAssign(pairs: Iterable<Pair<K, V>>)

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value.
Cmn
inline operator Unit
plusAssign(pairs: Sequence<Pair<K, V>>)

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value.
Cmn
V?
put(key: K, value: V)

Adds value to the cache using the specific key.
Cmn
Unit
putAll(from: Map<K, V>)

Puts all the key/value mappings in the from map into this cache.
Cmn
Unit
putAll(from: ScatterMap<K, V>)

Puts all the key/value mappings in the from map into this cache.
Cmn
Unit
putAll(from: SieveCache<K, V>)

Puts all the key/value mappings in the from cache into this cache.
Cmn
Unit
putAll(pairs: Array<Pair<K, V>>)

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value.
Cmn
Unit
putAll(pairs: Iterable<Pair<K, V>>)

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value.
Cmn
Unit
putAll(pairs: Sequence<Pair<K, V>>)

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value.
Cmn
V?
remove(key: K)

Removes the specified key and its associated value from the cache.
Cmn
Boolean
remove(key: K, value: V)

Removes the specified key and its associated value from the cache if the associated value equals value.
Cmn
Unit
removeIf(predicate: (K, V) -> Boolean)

Removes any mapping for which the specified predicate returns true.
Cmn
Unit
resize(maxSize: @IntRange(from = 1, to = 2147483646) Int)

Sets the maximum size of the cache to maxSize, in the unit defined by the implementation of sizeOf.
Cmn
inline operator Unit
set(key: K, value: V)

Adds value to the cache using the specific key.
Cmn
open String
Cmn
Unit
trimToSize(maxSize: Int)

Remove entries until the total size of the remaining entries is less than or equal to maxSize.
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 sizeOf (by default, the number of elements).
Cmn

Public constructors

SieveCache

Cmn 
<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 sizeOf, this is the maximum number of entries in the cache. For all other caches, this is the maximum sum of the sizes of the entries in this cache. The maximum size must be strictly greater than 0 and must be less than or equal to Int.MAX_VALUE - 1.
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 key of the entry being removed or evicted. The original value (oldValue) of the entry if the entry is being evicted or replaced. The new value (newValue) for the key, if it exists. If non-null, the removal was caused by a put() or a set(), otherwise it was caused by an eviction or a removal. A boolean (evicted) set to true if the entry was evicted to make space in the cache, or set to false if the removal happened on demand or while replacing an existing value with put.

Public functions

all

Cmn
Added in 1.5.0-alpha01
inline fun all(predicate: (K, V) -> Boolean): Boolean

Returns true if all entries match the given predicate.

any

Cmn
Added in 1.5.0-alpha01
fun any(): Boolean

Returns true if this cache has at least one entry.

any

Cmn
Added in 1.5.0-alpha01
inline fun any(predicate: (K, V) -> Boolean): Boolean

Returns true if at least one entry matches the given predicate.

contains

Cmn
Added in 1.5.0-alpha01
operator fun contains(key: K): Boolean

Returns true if the specified key is present in this cache, false otherwise.

containsKey

Cmn
Added in 1.5.0-alpha01
fun containsKey(key: K): Boolean

Returns true if the specified key is present in this cache, false otherwise.

containsValue

Cmn
Added in 1.5.0-alpha01
fun containsValue(value: V): Boolean

Returns true if the specified value is present in this hash map, false otherwise.

count

Cmn
Added in 1.5.0-alpha01
fun count(): Int

Returns the number of entries in this cache.

count

Cmn
Added in 1.5.0-alpha01
inline fun count(predicate: (K, V) -> Boolean): Int

Returns the number of entries matching the given predicate.

equals

Cmn 
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

  • Has the same size and count as this cache

  • Contains key/value pairs equal to this cache's pair

evictAll

Cmn
Added in 1.5.0-alpha01
fun evictAll(): Unit

Removes all the entries from this cache. Upon each removal, onEntryRemoved is invoked with the evicted parameter set to true.

forEach

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
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

Cmn 
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.

isEmpty

Cmn
Added in 1.5.0-alpha01
fun isEmpty(): Boolean

Indicates whether this cache is empty.

isNotEmpty

Cmn
Added in 1.5.0-alpha01
fun isNotEmpty(): Boolean

Returns true if this cache is not empty.

minusAssign

Cmn
Added in 1.5.0-alpha01
inline operator fun minusAssign(key: K): Unit

Removes the specified key and its associated value from the map.

minusAssign

Cmn
Added in 1.5.0-alpha01
inline operator fun minusAssign(keys: Array<K>): Unit

Removes the specified keys and their associated value from the map.

minusAssign

Cmn 
inline operator fun minusAssign(keys: Iterable<K>): Unit

Removes the specified keys and their associated value from the map.

minusAssign

Cmn
Added in 1.5.0-alpha01
inline operator fun minusAssign(keys: ObjectList<K>): Unit

Removes the specified keys and their associated value from the map.

minusAssign

Cmn
Added in 1.5.0-alpha01
inline operator fun minusAssign(keys: ScatterSet<K>): Unit

Removes the specified keys and their associated value from the map.

minusAssign

Cmn 
inline operator fun minusAssign(keys: Sequence<K>): Unit

Removes the specified keys and their associated value from the map.

none

Cmn
Added in 1.5.0-alpha01
fun none(): Boolean

Returns true if this cache has no entries.

plusAssign

Cmn 
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

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
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

Cmn 
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

Cmn 
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

Cmn 
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

Cmn 
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

Cmn
Added in 1.5.0-alpha01
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

Cmn 
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

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
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

Cmn 
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

Cmn 
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

Cmn 
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

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
fun removeIf(predicate: (K, V) -> Boolean): Unit

Removes any mapping for which the specified predicate returns true.

resize

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
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.

toString

Cmn 
open fun toString(): String

trimToSize

Cmn
Added in 1.5.0-alpha01
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

Cmn
Added in 1.5.0-alpha01
val capacity: Int

Returns the number of entries that can be stored in this cache without requiring internal storage reallocation.

See also
count

count

Cmn
Added in 1.5.0-alpha01
val count: Int

Returns the number of elements held in the cache.

See also
capacity

maxSize

Cmn
Added in 1.5.0-alpha01
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

size

Cmn
Added in 1.5.0-alpha01
val size: Int

Size of the cache in the unit defined by the implementation of sizeOf (by default, the number of elements).

See also
maxSize