On This Page
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
package 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 ... endSignature of types with measurable weight.
module F : sig ... endFunctional LRU map.
module M : sig ... endMutable LRU map.
One-off memoization
val memo :
?hashed:(('a -> int) * ('a -> 'a -> bool)) ->
?weight:('b -> int) ->
cap:int ->
(('a -> 'b) -> 'a -> 'b) ->
'a ->
'bmemo ?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.
On This Page