Module Timing_wheel.Level_bits
type t
The timing-wheel implementation uses an array of "levels", where level
i
is an array of length2^b_i
, where theb_i
are the "level bits" specified viaLevel_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, wherenum_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 fixednum_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 ofadd
andincrease_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
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 theb_i
inbits
hasb_i <= 0
, or if the sum of theb_i
inbits
is greater thanmax_num_bits
. With~extend_to_max_num_bits:true
, the resultingt
is extended with sufficientb_i = 1
so thatnum_bits t = max_num_bits
.
val default : t
default
returns the default value oflevel_bits
used byTiming_wheel.create
andTiming_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 theb_i
int
.