ringo

Caches (bounded-size key-value stores) and other bounded-size stores
IN THIS PACKAGE
Module Ringo

Ringo

Ringo is a library for caches.

Preamble

module type UNBOXED_COLLECTION = sig ... end

A mutable structure that holds at most a fixed number of values of a same type. Values are not removed by hand, instead, once the limit is reached, adding a value replaces the oldest one in the buffer.

Ring is a potentially useful module that is used internally to manage bounded, FIFO collections of items. The documentation is available in UNBOXED_COLLECTION.

Dll is a potentially useful module that is used internally to manage bounded, LRU collections of items. The documentation is available in UNBOXED_COLLECTION.

Caches

module type CACHE_MAP = sig ... end

A Mutable structure akin to a hash-table, but with a size bound. Note that, different caches have different policies towards the size bounds: some uphold the bound strictly, some treat the bound as a suggestion. In addition, some caches count their elements somewhat sloppily.

module type CACHE_SET = sig ... end

A Mutable structure akin to a set, but with a size bound. Note that, different caches have different policies towards the size bounds: some uphold the bound strictly, some treat the bound as a suggestion. In addition, some caches count their elements somewhat sloppily.

All caches of Ringo have either the CACHE_MAP interface (for key-value stores) or the CACHE_SET interface (for value stores). Their behavior can be tweaked by the parameters below.

Cache policies

type replacement =
| LRU
| FIFO

replacement is for defining the replacement policy of a cache. LRU is for "Least Recently Used", meaning that when a supernumerary item is inserted in the cache, the least recently used item is removed to make room. FIFO is for "First-In, First-Out" meaning that when a supernumerary item is inserted in the cache, the oldest inserted element is removed to make room.

type overflow =
| Strong
| Weak

overflow is for defining the overflow policy of a cache. Strong means that the cache never holds more element than is specified when calling create (see MAP_MAKER and SET_MAKER below and CACHE_MAP and CACHE_SET). Weak means that the cache may hold more elements than specified when calling create but that supernumerary elements may be collected by the Garbage Collector.

type accounting =
| Precise
| Sloppy

accounting is for defining the accounting policy of a cache.

Precise means that the cache counts its number of elements precisely: when an element is added, the count increases, when an element is removed, the count decreases, when an already present element is re-inserted the count is unchanged.

Sloppy means that the cache may count some elements that are not in the cache as still being held by the cache. As a result, adding a new element into the cache may lead to another element being removed even though the size limit was not actually reached.

The element-count of a Sloppy cache may become offset by one when an element is removed or when an element that is already present in the cache is re-added. This effect is cumulative and the element count can be off by more than one if multiple, say, removals happen.

The element-count eventually restores itself if enough new elements are added.

Additional details of the accounting in Sloppy caches are implementation dependent. Use Precise only if you use remove a lot, if you might insert the same key multiple times often, or if you need strong guarantees on the number of elements.

Note that when requesting a Sloppy cache, the library might give you a Precise cache if there is no additional runtime cost. In general, Sloppy caches are more efficient, but depending on the other parameters they might be only as-efficient-as (not strictly more efficient than) Precise caches.

Cache instantiating

module type MAP_MAKER = functor (H : Hashtbl.HashedType) -> CACHE_MAP with type key = H.t

A MAP_MAKER is a functor that instantiates CACHE_MAPs based on a given type and its associated hash function.

type map_maker = (module MAP_MAKER)
val map_maker : replacement:replacement -> overflow:overflow -> accounting:accounting -> map_maker

map_maker ~replacement ~overflow ~accounting is a first-class MAP_MAKER that instantiates caches with the policies specified by replacement, overflow, and accounting.

module EmptyMap (H : Hashtbl.HashedType) : sig ... end

EmptyMap(H) is a map module but it only supports the empty map: a map with zero elements.

module SingletonMap (H : Hashtbl.HashedType) : sig ... end

SingletonMap(H) is a map module but it only supports singleton maps: maps with at most one element.

module type SET_MAKER = functor (H : Hashtbl.HashedType) -> CACHE_SET with type elt = H.t

A SET_MAKER is a functor that instantiates CACHE_SETs based on a given type and its associated hash function.

type set_maker = (module SET_MAKER)
val set_maker : replacement:replacement -> overflow:overflow -> accounting:accounting -> set_maker

set_maker ~replacement ~overflow ~accounting is a first-class SET_MAKER that instantiates caches with the policies specified by replacement, overflow, and accounting.

module EmptySet (H : Hashtbl.HashedType) : sig ... end

EmptySet(H) is a set module but it only supports the empty set: a set with zero elements.

module SingletonSet (H : Hashtbl.HashedType) : sig ... end

SingletonSey(H) is a set module but it only supports singleton sets: sets with at most one element.