module type Timing_wheel =sig
..end
module Time:Timing_wheel_intf.Timing_wheel_time
type 'a
t
type'a
timing_wheel ='a t
type'a
t_now ='a t
<:sexp_of< _ t_now >>
displays only now t
, not all the alarms.module Interval_num:Timing_wheel_intf.Interval_num
module Alarm:sig
..end
include Invariant.S1
module Level_bits:sig
..end
module Config:sig
..end
val create : config:Config.t ->
start:Time.t -> 'a t
create ~config ~start
creates a new timing wheel with current time start
.
For a fixed level_bits
, a smaller (i.e. more precise) alarm_precision
decreases
the representable range of times/keys and increases the constant factor for
advance_clock
.
val alarm_precision : 'a t -> Time.Span.t
val now : 'a t -> Time.t
val start : 'a t -> Time.t
val is_empty : 'a t -> bool
val length : 'a t -> int
val iter : 'a t ->
f:('a Alarm.t -> unit) -> unit
val interval_num : 'a t ->
Time.t -> Timing_wheel_intf.Interval_num.t
interval_num t time
returns the number of the interval that time
is in, where
0
is the interval that starts at start
. interval_num
raises if time
is too
far in the past or future to represent.
now_interval_num t
equals interval_num t (now t)
.
val now_interval_num : 'a t -> Timing_wheel_intf.Interval_num.t
val interval_num_start : 'a t ->
Timing_wheel_intf.Interval_num.t -> Time.t
interval_num_start t n
is the start of the n
'th interval in t
, i.e.:
start t + n * alarm_precision t
interval_start t time
is the start of the half-open interval containing time
,
i.e.:
interval_num_start t (interval_num t time)
interval_start
raises in the same cases that interval_num
does.
val interval_start : 'a t -> Time.t -> Time.t
val advance_clock : 'a t ->
to_:Time.t ->
handle_fired:('a Alarm.t -> unit) -> unit
advance_clock t ~to_ ~handle_fired
advances t
's clock to to_
. It fires and
removes all alarms a
in t
with Time.(<) (Alarm.at t a) (interval_start t to_)
,
applying handle_fired
to each such a
.
If to_ <= now t
, then advance_clock
does nothing.
advance_clock
fails if to_
is too far in the future to represent.
Behavior is unspecified if handle_fired
accesses t
in any way other than
Alarm
functions.
val fire_past_alarms : 'a t ->
handle_fired:('a Alarm.t -> unit) -> unit
fire_past_alarms t ~handle_fired
fires and removes all alarms a
in t
with
Time.( <= ) (Alarm.at t a) (now t)
, applying handle_fired
to each such a
.
fire_past_alarms
visits all alarms in interval now_interval_num
, to check their
Alarm.at
.
Behavior is unspecified if handle_fired
accesses t
in any way other than
Alarm
functions.
val alarm_upper_bound : 'a t -> Time.t
alarm_upper_bound t
returns the upper bound on an at
that can be supplied to
add
. alarm_upper_bound t
is not constant; its value increases as now t
increases.val add : 'a t ->
at:Time.t -> 'a -> 'a Alarm.t
add t ~at a
adds a new value a
to t
and returns an alarm that can later be
supplied to remove
the alarm from t
. add
raises if interval_num t at <
now_interval_num t || at >= alarm_upper_bound t
.
add_at_interval_num t ~at a
is equivalent to add t ~at:(interval_num_start t at)
a
.
val add_at_interval_num : 'a t ->
at:Timing_wheel_intf.Interval_num.t ->
'a -> 'a Alarm.t
val mem : 'a t ->
'a Alarm.t -> bool
val remove : 'a t ->
'a Alarm.t -> unit
remove t alarm
removes alarm
from t
. remove
raises if not (mem t
alarm)
.val reschedule : 'a t ->
'a Alarm.t -> at:Time.t -> unit
reschedule t alarm ~at
mutates alarm
so that it will fire at at
, i.e. so that
Alarm.at t alarm = at
. reschedule
raises if not (mem t alarm)
or if at
is
an invalid time for t
, in the same situations that add
raises.
reschedule_at_interval_num t alarm ~at
is equivalent to:
reschedule t alarm ~at:(interval_num_start t at)
val reschedule_at_interval_num : 'a t ->
'a Alarm.t ->
at:Timing_wheel_intf.Interval_num.t -> unit
val clear : 'a t -> unit
clear t
removes all alarms from t
.val next_alarm_fires_at : 'a t -> Time.t option
next_alarm_fires_at t
returns the minimum time to which the clock can be advanced
such that an alarm will fire, or None
if t
has no alarms. If
next_alarm_fires_at t = Some next
, then for the minimum alarm time min
that
occurs in t
, it is guaranteed that: next - alarm_precision t <= min < next
.
The rest of this interface is not intended to be used with Timing_wheel, but is a
separate data structure used to implement Timing_wheel, and may find use
elsewhere.
module Priority_queue:sig
..end
val sexp_of_t : ('a -> Sexplib.Sexp.t) ->
'a t -> Sexplib.Sexp.t
val sexp_of_t_now : ('a -> Sexplib.Sexp.t) ->
'a t_now -> Sexplib.Sexp.t
<:sexp_of< _ t_now >>
displays only now t
, not all the alarms.null ()
returns an alarm t
such that not (mem timing_wheel t)
for all
timing_wheel
s.Alarm
functions will raise if not (Timing_wheel.mem timing_wheel 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.
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:
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
.
default = [11; 10; 10; 10; 10; 10]
This default uses 61 bits, i.e. max_num_bits
, and less than 10k words of memory.
num_bits t
is the sum of the b_i
in t
.
create
raises if alarm_precision <= 0
.
accessors
default
is create ()
.
durations t
returns the durations of the levels in t
create ~config ~start
creates a new timing wheel with current time start
.
For a fixed level_bits
, a smaller (i.e. more precise) alarm_precision
decreases
the representable range of times/keys and increases the constant factor for
advance_clock
.
Accessors
One can think of a timing wheel as a set of alarms. Here are various container
functions along those lines.
interval_num t time
returns the number of the interval that time
is in, where
0
is the interval that starts at start
. interval_num
raises if time
is too
far in the past or future to represent.
now_interval_num t
equals interval_num t (now t)
.
interval_num_start t n
is the start of the n
'th interval in t
, i.e.:
start t + n * alarm_precision t
interval_start t time
is the start of the half-open interval containing time
,
i.e.:
interval_num_start t (interval_num t time)
interval_start
raises in the same cases that interval_num
does.
advance_clock t ~to_ ~handle_fired
advances t
's clock to to_
. It fires and
removes all alarms a
in t
with Time.(<) (Alarm.at t a) (interval_start t to_)
,
applying handle_fired
to each such a
.
If to_ <= now t
, then advance_clock
does nothing.
advance_clock
fails if to_
is too far in the future to represent.
Behavior is unspecified if handle_fired
accesses t
in any way other than
Alarm
functions.
fire_past_alarms t ~handle_fired
fires and removes all alarms a
in t
with
Time.( <= ) (Alarm.at t a) (now t)
, applying handle_fired
to each such a
.
fire_past_alarms
visits all alarms in interval now_interval_num
, to check their
Alarm.at
.
Behavior is unspecified if handle_fired
accesses t
in any way other than
Alarm
functions.
alarm_upper_bound t
returns the upper bound on an at
that can be supplied to
add
. alarm_upper_bound t
is not constant; its value increases as now t
increases.
add t ~at a
adds a new value a
to t
and returns an alarm that can later be
supplied to remove
the alarm from t
. add
raises if interval_num t at <
now_interval_num t || at >= alarm_upper_bound t
.
add_at_interval_num t ~at a
is equivalent to add t ~at:(interval_num_start t at)
a
.
remove t alarm
removes alarm
from t
. remove
raises if not (mem t
alarm)
.
reschedule t alarm ~at
mutates alarm
so that it will fire at at
, i.e. so that
Alarm.at t alarm = at
. reschedule
raises if not (mem t alarm)
or if at
is
an invalid time for t
, in the same situations that add
raises.
reschedule_at_interval_num t alarm ~at
is equivalent to:
reschedule t alarm ~at:(interval_num_start t at)
clear t
removes all alarms from t
.next_alarm_fires_at t
returns the minimum time to which the clock can be advanced
such that an alarm will fire, or None
if t
has no alarms. If
next_alarm_fires_at t = Some next
, then for the minimum alarm time min
that
occurs in t
, it is guaranteed that: next - alarm_precision t <= min < next
.
The rest of this interface is not intended to be used with Timing_wheel, but is a
separate data structure used to implement Timing_wheel, and may find use
elsewhere.
Timing wheel is implemented as a priority queue in which the keys are
non-negative integers corresponding to the intervals of time. The priority queue is
unlike a typical priority queue in that rather than having a "delete min" operation,
it has a nondecreasing minimum allowed key, which corresponds to the current time,
and an increase_min_allowed_key
operation, which implements advance_clock
.
increase_min_allowed_key
as a side effect removes all elements from the timing
wheel whose key is smaller than the new minimum, which implements firing the alarms
whose time has expired.
Adding elements to and removing elements from a timing wheel takes constant time,
unlike a heap-based priority queue which takes log(N), where N is the number of
elements in the heap. increase_min_allowed_key
takes time proportional to the
amount of increase in the min-allowed key, as compared to log(N) for a heap. It is
these performance differences that motivate the existence of timing wheels and make
them a good choice for maintaing a set of alarms. With a timing wheel, one can
support any number of alarms paying constant overhead per alarm, while paying a
small constant overhead per unit of time passed.
As the minimum allowed key increases, the timing wheel does a lazy radix sort of the
element keys, with level 0 handling the least significant b_0
bits in a key, and
each subsequent level i
handling the next most significant b_i
bits. The levels
hold increasingly larger ranges of keys, where the union of all the levels can hold
any key from min_allowed_key t
to max_allowed_key t
. When a key is added to the
timing wheel, it is added at the lowest possible level that can store the key. As
the minimum allowed key increases, timing-wheel elements move down levels until they
reach level 0, and then are eventually removed.
An Elt.t
represents an element that was added to a timing wheel.
create ?level_bits ()
creates a new empty timing wheel, t
, with length t = 0
and min_allowed_key t = 0
.
length t
returns the number of elements in the timing wheel.
is_empty t
is length t = 0
min_allowed_key t
is the minimum key that can be stored in t
. This only
indicates the possibility; there need not be an element elt
in t
with Elt.key
elt = min_allowed_key t
. This is not the same as the "min_key" operation in a
typical priority queue.
min_allowed_key t
can increase over time, via calls to
increase_min_allowed_key
. It is guaranteed that min_allowed_key t <=
Key.max_representable
.
max_allowed_key t
is the maximum allowed key that can be stored in t
. As
min_allowed_key
increases, so does max_allowed_key
; however it is not the case
that max_allowed_key t - min_allowed_key t
is a constant. It is guaranteed that
max_allowed_key t >= min (Key.max_representable, min_allowed_key t + 2^B - 1
,
where B
is the sum of the b_i in level_bits
. It is also guaranteed that
max_allowed_key t <= Key.max_representable
.
min_elt t
returns an element in t
that has the minimum key, if t
is
nonempty. min_elt
takes time proportional to the size of the timing-wheel data
structure in the worst case. It is implemented via a linear search.
min_key t
returns the key of min_elt t
, if any.
add t ~key value
adds a new value to t
and returns an element that can later
be supplied to remove
the element from t
. add
raises if key <
min_allowed_key t || key > max_allowed_key t
.
remove t elt
removes elt
from t
. It is an error if elt
is not currently
in t
, and this error may or may not be detected.
change_key t elt ~key
changes the key of elt
to key
. change_key
raises if
not (mem t elt) || key < min_allowed_key t || key > max_allowed_key t
.
clear t
removes all elts from t
.
increase_min_allowed_key t ~key ~handle_removed
increases the minimum allowed
key in t
to key
, and removes all elements with keys less than key
, applying
handle_removed
to each element that is removed. If key <= min_allowed_key t
,
then increase_min_allowed_key
does nothing. Otherwise, if
increase_min_allowed_key
returns successfully, min_allowed_key t = key
.
increase_min_allowed_key
raises if key > Key.max_representable
.
increase_min_allowed_key
takes time proportional to key - min_allowed_key t
,
although possibly less time.
Behavior is unspecified if handle_removed
accesses t
in any way other than
Elt
functions.