package incr_map

  1. Overview
  2. Docs

A version of collate with caching.

We use Incr_memoize to cache incremental nodes for the result of a particular:

  • order,
  • (order, filter), and
  • (order, filter, range_bucket)

so that even if the Collate.t Incr.t changes, as long as it changes back before the result is evicted from the cache, we can resume a cached incremental computation instead of discarding it and computing it from scratch.

Note that if an earlier incremental node is evicted from its cache, its children in subsequent caches are no longer used. This is to ensure we don't duplicate computations from building later nodes on top of semantically identical but physically distinct earlier nodes.

For example, if the order cache is LRU with size 2, and order_filter_range is LRU with size 10, you could get 10 cached final values if they only use two distinct orderings, but if they were to each have a distinct ordering, only two will be usable.

module Range_memoize_bucket : sig ... end
val collate__sort_first : filter_equal:('filter -> 'filter -> bool) -> order_equal:('order -> 'order -> bool) -> ?order_cache_params:'order Store_params.t -> ?order_filter_cache_params:('order * 'filter) Store_params.t -> ?order_filter_range_cache_params: ('order * 'filter * Range_memoize_bucket.t) Store_params.t -> ?range_memoize_bucket_size:int -> filter_to_predicate:('filter -> (key:'k -> data:'v -> bool) option) -> order_to_compare:('order -> ('k, 'v, 'cmp) Compare.t) -> (('k, 'v, 'cmp) Core.Map.t, 'w) Incremental.t -> (('k, 'filter, 'order) Collate.t, 'w) Incremental.t -> ('k, 'v, unit, 'w) t
val collate_and_fold__sort_first : filter_equal:('filter -> 'filter -> bool) -> order_equal:('order -> 'order -> bool) -> ?order_cache_params:'order Store_params.t -> ?order_filter_cache_params:('order * 'filter) Store_params.t -> ?order_filter_range_cache_params: ('order * 'filter * Range_memoize_bucket.t) Store_params.t -> ?range_memoize_bucket_size:int -> filter_to_predicate:('filter -> (key:'k -> data:'v -> bool) option) -> order_to_compare:('order -> ('k, 'v, 'cmp) Compare.t) -> fold:('k, 'v, 'fold_result) Fold.t -> (('k, 'v, 'cmp) Core.Map.t, 'w) Incremental.t -> (('k, 'filter, 'order) Collate.t, 'w) Incremental.t -> ('k, 'v, 'fold_result, 'w) t

Like collate__sort_first, but also gives an opportunity to perform a fold over the post-filtered, pre-range-restricted data.

OCaml

Innovation. Community. Security.