NAME

LinkedList::Single::Example::Handoff - a work queue handed from producer to consumer, with cancel by handle, kept in a linked list

SYNOPSIS

use LinkedList::Single::Example::Handoff;

my $queue   = LinkedList::Single::Example::Handoff->new;

my $id      = $queue->enqueue( 'send', $mail );

$queue->cancel( $id );                 # still queued? then gone

my $batch   = $queue->take( 50 );      # or ->drain for all of it

# the lock is not held for any of this

my $done    = $queue->process( $batch, sub( $id, @job ) { ... }, 20 );

$queue->requeue( $batch );             # whatever was left

DESCRIPTION

A producer puts work on a queue with enqueue, which returns a handle (an integer id); cancel( $id ) takes that item out again if it is still queued. A consumer takes a batch under the lock, either the whole queue (drain) or at most $k items from the front (take), and works through it with the lock released: process passes each item to a handler, optionally stopping after a limit, and requeue puts the part of a batch that was not done back at the front. left counts what is still in a batch; contents, size, walked and purged look at the queue without changing it.

The queue is a LinkedList::Single list behind a permanent anchor node, with a cursor on its last node and a hash from each id to a cursor on the node before that item. A batch is a Fragment cut off the list. Every method that touches the queue runs inside LinkedList::Single::Example::Lock, a stand-in lock that records how often and for how long it was held (perl ithreads cannot share a linked list, so there are no real threads).

Two classes with the same interface keep the queue in perl arrays: LinkedList::Single::Example::Handoff::Array (hand-off by swapping the array reference, or by copying, and cancel by search) and LinkedList::Single::Example::Handoff::Marked (an array plus a hash from id to item, with cancel by marking). The tests drive all of them with the same random schedule and compare every result.

How it is benchmarked

benchmarks/40-Handoff/compare runs, at queue lengths of 1,000, 20,000 and 200,000: a whole-queue hand-off, 100 bounded batches of 50, 200 cancels by handle, and 200 rounds of take 100, process 50, requeue 50. It reports the seconds the lock was held and the total seconds (best of 3), the nodes or elements stepped over under the lock, the resident memory of a fresh process holding 200,000 items, the bytes left after a burst and after cancelling 90% of a queue, and statements and branches counted in the lock-held code.

Why it matters

Everything done while a lock is held is time the other side waits. Under the lock the list's whole-queue hand-off is constant time, but so is the array's reference swap, and the list is slower than the arrays at taking a bounded batch, at requeueing, and at processing. Its one lasting advantage is cancel: constant time, with the item's memory returned at once, where an array either searches or leaves a husk behind. The measurements, the background and the references are in LinkedList::Single::Example::Handoff::POD.

This is an example, not a queue for production use: there are no real threads, no blocking and no priorities.

SEE ALSO

LinkedList::Single::Example::Handoff::POD, LinkedList::Single