/ 
Data-Deque-Shared-0.04
/ Data::Deque::Shared

NAME

Data::Deque::Shared - Shared-memory double-ended queue for Linux

SYNOPSIS

use Data::Deque::Shared;

my $dq = Data::Deque::Shared::Int->new(undef, 100);
$dq->push_back(1);
$dq->push_back(2);
$dq->push_front(0);
say $dq->pop_front;   # 0
say $dq->pop_back;    # 2

# String variant (fixed max_len per entry)
my $sq = Data::Deque::Shared::Str->new(undef, 100, 64);
$sq->push_back("hello");
say $sq->pop_front;   # hello

# blocking with timeout
$dq->push_back_wait(42, 5.0);
my $v = $dq->pop_front_wait(5.0);

# file-backed / memfd
$dq = Data::Deque::Shared::Int->new('/tmp/dq.shm', 100);
$dq = Data::Deque::Shared::Int->new_memfd("my_dq", 100);
my $fd = $dq->memfd;
$dq = Data::Deque::Shared::Int->new_from_fd($fd);

DESCRIPTION

Double-ended queue (deque) in shared memory. Ring buffer with CAS-based push/pop at both ends. Futex blocking when empty or full.

Linux-only. Requires 64-bit Perl. Capacity must be <= 2^31.

Used only as a FIFO (push_back + pop_front), it's effectively a fixed-slot lock-free string queue: 1.3x-4.7x faster than Data::Queue::Shared::Str under multi-producer contention, at the cost of per-slot fixed memory (capacity × max_len).

Concurrency

Push and pop are safe under multi-producer / multi-consumer workloads. Each slot carries a 64-bit control word (state + generation) that acts as a publication gate: a pusher atomically transitions the slot through empty → writing → filled, and a popper transitions it through filled → reading → empty with the generation bumped on completion. A consumer that claims position n via the head/tail CAS therefore always observes the publication transition of the corresponding push before reading the value.

drain is safe under concurrent push/pop: it spin-waits on any slot whose pusher is mid-publish, then releases each slot through the state machine. If a pusher crashes after winning its position CAS but before publishing the value (i.e. anywhere in the cursor-CAS to publish window), drain waits ~2 seconds and then force-recovers the slot via a generation bump (counted in stats->{recoveries}). A stalled- but-live pusher whose slot was force-recovered will silently drop its late publish rather than resurrect the slot as FILLED.

Compatibility

File format bumped to v2 in this release (per-slot control array added for MPMC safety). Opening a v1 file (magic DEQ1) created by Data::Deque::Shared <= 0.02 will croak on header validation. Re-create the deque with the new version; anonymous and memfd-backed usage is unaffected.

METHODS

Push / Pop

$dq->push_back($val);          $dq->push_front($val);
$dq->push_back_wait($val, $t); $dq->push_front_wait($val, $t);
my $v = $dq->pop_front;        my $v = $dq->pop_back;
my $v = $dq->pop_front_wait($t); my $v = $dq->pop_back_wait($t);

Status

$dq->size;  $dq->capacity;  $dq->is_empty;  $dq->is_full;
$dq->clear;    # NOT concurrency-safe
my $n = $dq->drain;  # concurrency-safe, returns count drained
$dq->stats;    # {size, capacity, pushes, pops, waits, timeouts, recoveries, mmap_size}

Common

$dq->path;  $dq->memfd;  $dq->sync;  $dq->unlink;

eventfd

$dq->eventfd;  $dq->notify;  $dq->eventfd_consume;
$dq->eventfd_set($fd);  $dq->fileno;

STATS

stats() returns: size, capacity, pushes, pops, waits, timeouts, recoveries, mmap_size. recoveries counts slots that drain force-skipped because a pusher crashed (or stalled > 2s) between winning the cursor CAS and publishing the value.

SECURITY

The mmap region is writable by all processes that open it. Do not share backing files with untrusted processes.

BENCHMARKS

Single-process (1M ops, x86_64 Linux, Perl 5.40):

push_back + pop_front (FIFO)    6.5M/s
push_back + pop_back (LIFO)     6.3M/s
push_front + pop_front (LIFO)   6.4M/s
push_front + pop_back (FIFO)    6.5M/s

Multi-process (8 workers, 200K ops each):

cap=16     5.7M/s aggregate
cap=64     5.9M/s aggregate
cap=256    5.8M/s aggregate

SEE ALSO

Data::Stack::Shared - LIFO stack

Data::Queue::Shared - FIFO queue

Data::ReqRep::Shared - request-reply

Data::Pool::Shared - fixed-size object pool

Data::Log::Shared - append-only log (WAL)

Data::Buffer::Shared - typed shared array

Data::Sync::Shared - synchronization primitives

Data::HashMap::Shared - concurrent hash table

Data::PubSub::Shared - publish-subscribe ring

Data::Heap::Shared - priority queue

Data::Graph::Shared - directed weighted graph

Data::BitSet::Shared - shared bitset (lock-free per-bit ops)

Data::RingBuffer::Shared - fixed-size overwriting ring buffer

AUTHOR

vividsnow

LICENSE

This is free software; you can redistribute it and/or modify it under the same terms as Perl itself.