Module `Tjr_lib_core.Lru_two_gen_v3pure`

Internal module

A two-generation LRU with batch eviction. Compared to v3, this is the pure part only (no monad or handling of slow operations).

This tries to take advantage of the extremely good performance of hashtables.

We assume a limit N on the number of most-recent items we want to track.

The idea is to maintain two maps (hence "two generations"). The first is of size n1 <=N, and contains the n1 most recently used elements. The second is typically of size N, and the next (N-n1) most-recent elements are contained in this set. In the case where the set is of size n2 < N, then only the most recent n1+n2 items are tracked (FIXME?)

When the first map reaches the limit N, it is demoted to the second map, and the second map is dropped. At this point, we need to expunge multiple elements from the cache, so this is "batch eviction".

Looking up an item consults the first map first, then the second, then the underlying map.

Compared to standard LRU, the implementation is likely simpler and faster. Of course, you don't have full information about the ordering of the most-recently used items. But in the case where you are maintaining a cache, this doesn't matter so much.

NOTE a quick google search finds that this may be similar: https://github.com/dominictarr/hashlru , with some benchmarking here: https://github.com/dominictarr/bench-lru

Don't open - record field clashes, type clashes

Version with delete

type 'v entry = [ | `Inserted of 'v | `Deleted | `Lower_some of 'v | `Lower_none ]

Entries in the internal maps can record that an entry has been deleted, or that an entry is present in the lower map m3;

type 'v entry = [ `Inserted of 'v | `Deleted | `Lower_some of 'v | `Lower_none ]

type 'v dirty_entry = [ | `Inserted of 'v | `Deleted ]

module Cache_state : sig ... end: Cache state; internal

type ('k, 'v, 'c) ops = { find_raw : c:'c -> 'k -> 'v entry option; insert : c:'c -> 'k -> 'v -> unit; insert_raw : c:'c -> 'k -> 'v entry -> unit; delete : c:'c -> 'k -> unit; needs_trim : c:'c -> bool; trim : c:'c -> ('k * 'v entry) list; bindings : c:'c -> ('k * 'v entry) list; dirties : c:'c -> ('k * 'v dirty_entry) list; clean : c:'c -> ('k * 'v dirty_entry) list; debug : c:'c -> ('k, 'v entry) Tjr_lib_core__.Hashtbl.t * ('k, 'v entry) Tjr_lib_core__.Hashtbl.t; }: API; 'c is the cache type

module type S = sig ... end

module type T = sig ... end

module Make : functor (S : S) -> T with module S = S: For some applications, we want very precise control of the cache, ie not to have the cache state hidden inside functions, but instead be referenced explicitly