NAME
LinkedList::Single::Example::Timer - a queue of messages that dispatches those whose start time has passed, held in a linked list
SYNOPSIS
use LinkedList::Single::Example::Timer;
my $queue = LinkedList::Single::Example::Timer->new( window => 60 );
$queue->enqueue( $start, 'send', $mail );
my $batch = $queue->take; # everything due now, or undef
# nothing is held while the batch is worked on
my $sent = $queue->process( $batch, sub( $start, @job ) { ... } );
$queue->requeue( $batch ); # what the window cut offDESCRIPTION
A queue of messages, each with the time it may start, kept in start order. enqueue( $start, @msg ) adds one. A dispatcher works in rounds: take( $now ) cuts every message whose start has passed off the front of the queue as one batch; process( $batch, $handler, $deadline ) hands the batch's messages to the handler in order until the clock reaches the deadline (by default window seconds, 60, from the call) or the batch is used up; and requeue( $batch ) puts what is left back in front of the queue, ahead of anything queued meanwhile. Nothing is dropped. The queue is not held while the batch is worked on. size, left, next_start, contents (earliest first), walked and merged look at it without changing it. The clock is passed to new, so the tests and the demonstration never sleep.
The queue is a LinkedList::Single behind a permanent anchor node, with a cursor kept on the last message. A message that starts no earlier than the last one is pushed on the end without a search; any other is placed by walking from the front. The batch is a Fragment of the list, so taking it and putting its unused part back are relinks, not copies. If a message whose start has already passed arrived while the batch was out, the batch is put back one message at a time, each in its place, and counted in merged.
LinkedList::Single::Example::Timer::Array has the same interface over a perl array, written as well as it can be: a binary search for the cut and for out-of-order messages, splice to take and unshift to put back. It is the test oracle: the tests drive both with the same random schedule and compare everything they report.
How it is benchmarked
benchmarks/70-Timer/compare measures the memory of 200,000 queued messages and of a queue drained to 10 after a burst; enqueue in start order (1,000 to 200,000 messages) and out of order (500 to 8,000); the dispatch cycle (take, requeue) for 10 to 10,000 due messages in front of 10,000 and 200,000 others; requeue of the unused part of a batch; and statements and branches in each implementation's code. benchmarks/70-Timer/latency times every call on its own, in a fresh process three times per case, on the thread's CPU-time clock, and reports the median, the 99th and 99.9th percentiles and the slowest call.
Why it matters
A dispatcher that works within a window has to put back what it did not reach, and the hope was that a list makes putting it back "nearly zero" time and the slowest call lower than an array's. Neither holds today. Putting the part back does not depend on the length of the queue, but it does grow with the size of the part, because the module walks the Fragment to find its tail; the array's unshift is cheaper still. The array is faster at every operation measured, its slowest calls are lower in steady state, and its one spike (a reallocation as it grows) stays under a millisecond up to two million messages. A change to the module that makes the re-attach constant was prototyped and measured, and is only a proposal (a known-tail argument to append_to and a detach_through); this example runs on the module as it is. The list's own advantages are that the batch is one object owned by the dispatcher and that its memory follows what is queued. The measurements, the background and the references are in LinkedList::Single::Example::Timer::POD.
This is an example, not a scheduler for production use: it has no persistence, no retry limit and no thread safety.
SEE ALSO
LinkedList::Single::Example::Timer::POD, LinkedList::Single::Example::Timer::Array, LinkedList::Single