package core_kernel

  1. Overview
  2. Docs
package core_kernel
Legend:
Library
Module
Module type
Parameter
Class
Class type
type t

The timing-wheel implementation uses an array of "levels", where level i is an array of length 2^b_i, where the b_i are the "level bits" specified via Level_bits.create_exn [b_0, b_1; ...].

A timing wheel can handle approximately 2 ** num_bits t intervals/keys beyond the current minimum time/key, where num_bits t = b_0 + b_1 + ....

One can use a Level_bits.t to trade off run time and space usage of a timing wheel. For a fixed num_bits, as the number of levels increases, the length of the levels decreases and the timing wheel uses less space, but the constant factor for the running time of add and increase_min_allowed_key increases.

include Ppx_sexp_conv_lib.Sexpable.S with type t := t
val t_of_sexp : Sexplib0.Sexp.t -> t
val sexp_of_t : t -> Sexplib0.Sexp.t
include Core_kernel.Invariant.S with type t := t
val invariant : t -> unit
val max_num_bits : int

max_num_bits is how many bits in a key the timing wheel can use, i.e. 61. We subtract 3 for the bits in the word that we won't use:

  • for the tag bit
  • for negative numbers
  • so we can do arithmetic around the bound without worrying about overflow
val create_exn : ?extend_to_max_num_bits:bool -> int list -> t

In create_exn bits, it is an error if any of the b_i in bits has b_i <= 0, or if the sum of the b_i in bits is greater than max_num_bits. With ~extend_to_max_num_bits:true, the resulting t is extended with sufficient b_i = 1 so that num_bits t = max_num_bits.

val default : t

default returns the default value of level_bits used by Timing_wheel.create and Timing_wheel.Priority_queue.create.

default = [11; 10; 10; 10; 10; 10]

This default uses 61 bits, i.e. max_num_bits, and less than 10k words of memory.

val num_bits : t -> int

num_bits t is the sum of the b_i in t.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct