module Level_bits:sig
..end
type
t
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 Invariant.S
val max_num_bits : int
val create_exn : int list -> t
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
.val default : Word_size.t -> t
default
returns the default value of level_bits
used by Timing_wheel.create
and Timing_wheel.Priority_queue.create
. It varies based on the machine's word
size. Here are the the values and the amount of space used for the level arrays.
| word | bits used | level_bits | space used |
|------+-----------+--------------------------+-------------|
| 32 | 29 | 10; 10; 9
| < 4k words |
| 64 | 61 | 11; 10; 10; 10; 10; 10
| < 10k words |
val num_bits : t -> int
num_bits t
is the sum of the b_i
in t
.val t_of_sexp : Sexplib.Sexp.t -> t
val sexp_of_t : t -> Sexplib.Sexp.t
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
.default
returns the default value of level_bits
used by Timing_wheel.create
and Timing_wheel.Priority_queue.create
. It varies based on the machine's word
size. Here are the the values and the amount of space used for the level arrays.
| word | bits used | level_bits | space used |
|------+-----------+--------------------------+-------------|
| 32 | 29 | 10; 10; 9
| < 4k words |
| 64 | 61 | 11; 10; 10; 10; 10; 10
| < 10k words |
num_bits t
is the sum of the b_i
in t
.