# Module `Lru`

Scalable LRU caches

`Lru`

provides weight-bounded finite maps that can remove the least-recently-used (LRU) bindings in order to maintain a weight constraint. Two implementations are provided: one is functional, the other imperative.

The functional map is backed by a priority search queue. Operations on individual elements are `O(log n)`

.

The mutable map is backed by the standard `Hashtbl`

paired with a doubly-linked list. Operations on individual elements incur an `O(1)`

overhead on top of hash table access.

Both versions support differentially weighted bindings, and have a capacity parameter that limits the combined weight of the bindings. To limit the maps by the number of bindings, use `let weight _ = 1`

.

*v0.3.0 — homepage*

## Semantics

A pretty accurate model of a functional `k -> v`

map is an association list (`(k * v) list`

) with unique keys.

Adding a bindings `k -> v`

to `kvs`

means `List.remove_assoc k kvs @ [(k, v)]`

, finding a `k`

means `List.assoc_opt k kvs`

, and removing it means `List.remove_assoc k kvs`

.

The LRU binding is then the first element of the list.

Promoting a binding `k -> v`

means removing, and then re-adding it.

Trimming `kvs`

means retaining the longest suffix with the sum of `weight v`

not larger than capacity.

The imperative LRU map is like the above, but kept in a reference cell.

## Lru

`module type Weighted = sig ... end`

Signature of types with measurable weight.

`module F : sig ... end`

Functional LRU map.

`module M : sig ... end`

Mutable LRU map.

## One-off memoization

`val memo : ?hashed:(('a -> int) * ('a -> 'a -> bool)) -> ?weight:('b -> int) -> cap:int -> (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b`

`memo ?hashed ?weight ~cap f`

is a new memoized instance of`f`

, using LRU caching.`f`

is an open recursive function of one parameter.`~hashed`

are hashing and equality over the arguments`'a`

. It defaults to`(Hashtbl.hash, Pervasives.(=))`

.`~weight`

is the weighting function over the results`'b`

. It defaults to`fun _ -> 1`

.`~cap`

is the total cache capacity.- raises Invalid_argument
when

`cap < 0`

.