NAME
Data::Fenwick::Shared - shared-memory Fenwick tree (binary indexed tree; point or range update) for Linux
SYNOPSIS
use Data::Fenwick::Shared;
# a tree over positions 1..1_000_000, anonymous mapping
my $fen = Data::Fenwick::Shared->new(undef, 1_000_000);
$fen->update(5, 3); # add 3 at position 5
$fen->update(9, 7); # add 7 at position 9
$fen->prefix(9); # 10 (sum of positions 1..9)
$fen->range(5, 9); # 10 (sum of positions 5..9)
$fen->point(5); # 3 (value at position 5)
$fen->total; # 10 (sum of all positions)
$fen->set(5, 100); # set position 5 to 100 (returns the old value)
# rank / weighted lookup: smallest position whose prefix sum reaches a target
$fen->find(50); # first position i with prefix(i) >= 50
# share across processes via a backing file
my $shared = Data::Fenwick::Shared->new("/tmp/counts.fen", 1_000_000);
# range-update mode: add to a whole range in O(log n), then query ranges
my $rng = Data::Fenwick::Shared->new_range(undef, 1_000_000);
$rng->range_add(10, 20, 5); # add 5 to every position in [10, 20]
$rng->range(10, 20); # 55 (sum over the range)
# freeze and ship: query it read-only (lock-free) on other machines
$shared->freeze;
my $ro = Data::Fenwick::Shared->new_readonly("/tmp/counts.fen");
$ro->prefix(500_000);DESCRIPTION
A Fenwick tree (binary indexed tree) in shared memory: a fixed-size array of n signed 64-bit integer positions that supports point update and prefix-sum query in O(log n) each, plus an O(log n) binary search for the position at which a running total is reached. It is the compact, update-friendly structure behind cumulative-frequency tables, running rank/order statistics, and weighted random sampling.
Positions are numbered 1 to n (1-indexed). update($i, $delta) adds a (possibly negative) delta at position $i; prefix($i) returns the sum of positions 1..$i; range($l, $r) the sum of $l..$r; point($i) the current value at a single position; and total the sum of everything. set overwrites a position with an absolute value. find($target) returns the smallest position whose prefix sum is at least $target (meaningful when all stored values are non-negative) -- the operation that turns a Fenwick tree into a weighted sampler or a rank index.
The tree lives in a shared mapping, so several processes update and query one structure: any process that opens the same backing file, inherits the anonymous mapping across fork, or reopens a passed memfd sees the others' updates and contributes its own. A write-preferring futex rwlock with dead-process recovery guards mutation, so many processes may update and query concurrently. Two trees of equal size n can be merged by element-wise addition (a Fenwick tree is linear, so the merge of tree(A) and tree(B) is tree(A+B)).
Values are signed 64-bit integers; sums that overflow 64 bits wrap, as with any native integer arithmetic. Memory is (n+1) * 8 bytes for the tree plus a fixed header. Linux-only. Requires 64-bit Perl.
Range-update mode
A tree created with new_range supports range update as well as range query: range_add($l, $r, $delta) adds a delta to every position in [$l, $r] in O(log n), and prefix/range/point/total report the resulting sums. It uses the classic two-BIT technique (a second binary indexed tree tracking the weighted difference), so a range-mode tree costs twice the memory (2 * (n+1) * 8 bytes) but adds O(log n) range updates a plain Fenwick tree cannot do. update($i, $delta) and set still work (a point update is just range_add($i, $i, $delta)). find and merge are not available in range mode (the two-BIT layout has no single-BIT binary lift); use a point tree for those. The mode is recorded in the header, so a reopened segment stays range mode. Note that the 0.02 on-disk format is incompatible with 0.01: a file created by 0.01 cannot be opened and must be recreated.
METHODS
Constructors
my $fen = Data::Fenwick::Shared->new($path, $n);
my $fen = Data::Fenwick::Shared->new(undef, $n); # anonymous
my $fen = Data::Fenwick::Shared->new_memfd($name, $n);
my $fen = Data::Fenwick::Shared->new_from_fd($fd);
my $ro = Data::Fenwick::Shared->new_readonly($path); # frozen file, read-only
# range-update mode (two BITs) -- same arguments
my $fen = Data::Fenwick::Shared->new_range($path, $n);
my $fen = Data::Fenwick::Shared->new_range_memfd($name, $n);$path is the backing file (undef or omitted for an anonymous mapping). $n is the number of positions (at least 1); positions are then addressed as 1..$n. new and new_memfd croak if $n is less than 1 or exceeds the tree cap. When reopening an existing file or memfd, the stored n wins and the caller's $n argument is ignored -- but a positive $n placeholder is still required, since the constructor validates $n before the stored value wins. new_memfd creates a Linux memfd (transferable via its memfd descriptor); new_from_fd reopens one in another process. The descriptor you pass is duplicated (F_DUPFD_CLOEXEC), so it stays yours to close and closing it does not disturb the handle. new_readonly opens a frozen file read-only for lock-free querying (see "FROZEN (READ-ONLY) MODE"). An optional file mode may be passed as the last argument to new (e.g. 0660) to opt a newly-created backing file into cross-user sharing; it defaults to 0600 (owner-only).
Updating
$fen->update($i, $delta); # add $delta at position $i (1 <= $i <= n)
$fen->range_add($l, $r, $delta); # add $delta to every position in [$l, $r] (range mode)
my $old = $fen->set($i, $value); # set position $i to $value; returns the old value
$fen->clear; # reset every position to 0range_add adds a delta to a whole inclusive range in O(log n) and requires a range-mode tree (new_range); it croaks on a point-mode tree. update adds a signed delta at a single position and returns nothing. set overwrites a position with an absolute value and returns its previous value (it is update($i, $value - point($i)) done atomically under one lock). Both croak if $i is outside 1..n. clear zeroes the whole tree.
Querying
my $s = $fen->prefix($i); # sum of positions 1..$i (0 <= $i <= n; prefix(0) == 0)
my $s = $fen->range($l, $r); # sum of positions $l..$r (1 <= $l <= $r <= n)
my $v = $fen->point($i); # value at position $i
my $t = $fen->total; # sum of all positions (== prefix(n))
my $i = $fen->find($target); # smallest position with prefix >= $targetprefix, range, point, and total are O(log n) reads returning signed integers. find binary-searches the tree for the smallest position whose prefix sum is at least $target, returning that position or n+1 if no prefix reaches it. find is only meaningful when every stored value is non-negative (a cumulative distribution): it is the core of weighted sampling (draw $target uniformly in [1, total] and find the bucket) and of order-statistic / rank queries. Out-of-range positions croak. find requires a point-mode tree (it croaks in range mode).
Merging, introspection, lifecycle
$fen->merge($other); # element-wise add (point mode; both must have equal n)
$fen->size; # n, the number of positions
$fen->is_range; # true for a range-mode (two-BIT) tree
$fen->stats; # { size, total, ops, mmap_size, range }
$fen->path; $fen->memfd; $fen->sync; $fen->unlink;merge adds another tree's contents into this one position by position; both trees must have the same n or it croaks, and both must be point-mode (merge croaks in range mode). The other tree is snapshotted under its own read lock, so two processes may merge concurrently without deadlock. is_range reports whether the tree is range mode. size (also capacity) is n. sync flushes the mapping to its backing store (a no-op for anonymous and memfd trees); unlink removes the backing file (also callable as Class->unlink($path)); path returns the backing path (undef for anonymous, memfd, or fd-reopened trees) and memfd the backing descriptor -- the memfd of a new_memfd tree or the dup'd fd of a new_from_fd tree, and -1 for file-backed or anonymous trees.
STATS
stats() returns a hashref: size (the number of positions n), total (the current sum of all positions), ops (running count of write-path calls -- update, range_add, set, merge, clear), mmap_size (bytes of the shared mapping), range (1 for a range-mode tree, 0 for a point-mode tree), frozen (1 if the tree has been sealed by freeze and is immutable, else 0), and readonly (1 if this handle is a read-only view -- from new_readonly, or the handle that called freeze -- else 0).
SHARING ACROSS PROCESSES
The tree lives in a shared mapping, shared the same three ways as the rest of the family: a backing file (every process calls new($path, $n) on the same path with a matching $n), an anonymous mapping inherited across fork, or a memfd whose descriptor is passed to an unrelated process (over a UNIX socket via SCM_RIGHTS, or via /proc/$pid/fd/$n) and reopened with new_from_fd($fd). Because the mapping is shared, every process updates and queries the same tree.
# producer and consumer share one running-sum tree with no coordination
my $fen = Data::Fenwick::Shared->new(undef, 1000); # before fork
unless (fork) { $fen->update($_, 1) for 1 .. 500; exit }
wait;
print $fen->total, "\n"; # 500 -- the child's updatesFROZEN (READ-ONLY) MODE
A file-backed tree can be frozen and then shipped to other machines, where consumers open it read-only and query it with no locking at all.
# producer: build, freeze, ship the file
my $fen = Data::Fenwick::Shared->new("/tmp/counts.fen", 1_000_000);
$fen->update($_, $counts{$_}) for keys %counts;
$fen->freeze; # seal: now immutable, and $fen itself is read-only
# ... copy /tmp/counts.fen to another host ...
# consumer (any process, same architecture): read-only, lock-free
my $ro = Data::Fenwick::Shared->new_readonly("/tmp/counts.fen");
$ro->prefix($_) for @queries;freeze takes the write lock, marks the tree permanently immutable (there is no unfreeze -- rebuild the file to change it), and flushes the seal to disk. A frozen tree rejects every mutator (update, range_add, set, clear, merge) with a croak, and a read-write reopen (new($path, ...) or new_from_fd) of a sealed file is refused -- so a shipped artifact can never be silently mutated out from under its readers.
new_readonly($path) maps the file O_RDONLY / PROT_READ and requires it to be frozen (it croaks on a file that was never freezed). Because a sealed tree's values and geometry are immutable, prefix, range, point, total, find, and stats read them directly, taking no reader lock -- the mapping is never written, so a read-only view works from a read-only file descriptor or a read-only filesystem, and any number of processes can share one PROT_READ mapping. frozen and readonly report the two states. A range-mode tree (new_range) can be frozen and reopened read-only the same way as a point-mode one; find and merge stay unavailable in range mode regardless of the frozen state.
Portability. The on-disk format is native binary (native-endian 64-bit words), so a frozen file may be copied only between machines of the same architecture; a wrong-endian file is rejected at open by the magic check. Copy the file to each consumer -- do not share one file over a network filesystem: the lock is a Linux futex (process-local to one kernel), and the "no live writer" contract assumes a static copy. Linux-only; 64-bit Perl.
SECURITY
Backing files are created with mode 0600 (owner-only) by default. To share a backing file across users, pass an explicit octal file mode such as 0660 as the last argument to new; the mode is applied when the file is created, and when a file left behind by an interrupted create is re-initialized (see "CRASH SAFETY"); a file already in use keeps its own permissions. The file is opened with O_NOFOLLOW (a symlink at the path is refused) and O_EXCL; the on-disk header is validated when the file is attached. Any process you grant write access to a shared mapping is trusted not to corrupt it while others are using it.
CRASH SAFETY
Mutation is guarded by a futex-based write-preferring rwlock with PID-encoded ownership; if a holder dies, the next contender detects the dead owner and recovers. Each update is a short O(log n) sequence of int64 stores, so a crash leaves the tree consistent up to the last completed operation. Limitation: PID reuse is not detected (very unlikely in practice).
Reader-slot exhaustion (slotless readers): dead-process recovery attributes a crashed lock holder's contribution through its reader-slot. The slot table holds 1024 entries (one per concurrent reader process). If more than that many reader processes share one mapping at once, a reader that cannot claim a slot proceeds "slotless" -- it still takes the read lock but leaves no per-process record. If such a slotless reader is then killed while holding the read lock, its share of the lock cannot be attributed to a dead process, so writer recovery cannot reclaim it and writers may block until the mapping is recreated. Reaching this needs more than 1024 concurrent reader processes on one mapping plus a crash in the brief read-lock window; the dead-process slot reclaim keeps the table from filling with stale entries, so in practice it is very unlikely.
An interrupted create is recovered too. A creator killed after the backing file is sized but before its header is committed leaves a full-size, all-zero file. new re-initializes such a file automatically, but only when it is exactly the size the requested geometry needs, is owned by your effective uid, and is still entirely zero -- a file holding data is never re-initialized. If the creator got as far as writing part of the header, the file cannot be told apart from a corrupt one and new croaks with incomplete Fenwick tree file left by an interrupted create; remove it and retry. A file left behind by an interrupted create never held data, so removing it is safe -- but a file whose header was corrupted after the fact reaches the same croak, so confirm it is an abandoned create before deleting anything you care about.
SEE ALSO
Data::SortedSet::Shared (order-statistics ZSET), Data::NDArray::Shared (dense numeric arrays), Data::Histogram::Shared (HdrHistogram), and the rest of the Data::*::Shared family.
AUTHOR
vividsnow
LICENSE
This is free software; you can redistribute it and/or modify it under the same terms as Perl itself.