Module Tjr_fs_shared.Write_back_cache_v3

A write-back cache; a wrapper around pqwy/lru.

This version avoids the extra ty var in v1.

Notes

$(FIXME("odoc.css bold seems to render not bold; this will be fixed in new version of odoc"))

Note on pqwy/lru pqwy/lru is here: github and ocamldoc

add promotes binding to the most recently used; trim needs to be invoked explicitly after add; find does not promote.

Additional operations beyond pqwy/lru: we want to evict in batches; so we have a high capacity and a low capacity. We call low_cap just cap, and high_cap is low_cap+delta. We want a trim operation which trimes to low_cap.

We are also interested in whether entries are "clean" (can be evicted with no further action) or "dirty" (in which case, we need to flush to the lower level).

Note our find and insert do promote (cf pqwy, which does not promote automatically).

API

NOTE since we store a dirty flag (bool) with each value, some of the operations take/return a 'v*bool rather than a v

The operations:

  • create: takes a capacity, and delta, the default number of lru-elts to remove on trim
  • find, insert, delete; find and insert promote automatically; delete is used for B-tree freeing blks (we could trim instead)
  • promote: to touch a key so that it has just been used; probably we don't use this (find and insert promote automatically)
  • needs_trim: return true iff sz > cap+delta
  • trim - pop lru clean and dirty elements until cap size reached; the returned list only contains the dirty entries
  • clean: get all the dirty entries, and return them, together with a fully clean, trimmed, cache; actually, since cleaning a large cache is very expensive, we just return an empty cache for now
  • bindings: return all (clean and dirty) bindings

$(TODO(""" At the moment, we use the pqwy functional implementation, but this is much slower than the imperative version which we should use in production; when we use a mutable version, we can also efficiently implement clean). """))

NOTE: for delete, we typically expect that any existing v binding is not dirty, but this is not checked at runtime

$(ABBREV("wbc is short for write-back cache"))

type ('k, 'v, 't) wbc_ops = {
size : 't -> int;
find : 'k -> 't -> ('v * bool) option * 't;

For find, if None is returned, the cache is guaranteed to be unaltered

insert : 'k -> ('v * bool) -> 't -> 't;
delete : 'k -> 't -> 't;
needs_trim : 't -> bool;
trim : 't -> ('k * 'v) list * 't;
clean : 't -> ('k * 'v) list * 't;
bindings : 't -> ('k * ('v * bool)) list;
}
type wbc_params = < cap : int; delta : int; >
type ('k, 'v, 't) wbc_ops_plus = < empty : 't; cap : int; delta : int; ops : ('k, 'v, 't) wbc_ops; >
type ('k, 'v, 't) wbc_factory = < make_wbc : cap:int -> delta:int -> ('k, 'v, 't) wbc_ops_plus; >
module type K = Stdlib.Map.OrderedType
module type V = sig ... end
module Make : functor (K : K) -> functor (V : V) -> sig ... end