NAME
LinkedList::Single::Example::Ordered - an ordered map in a linked list with a small index of markers
SYNOPSIS
use LinkedList::Single::Example::Ordered;
# bucket defaults to $ENV{ LLS_BUCKET_SIZE }, else 3.
my $map = LinkedList::Single::Example::Ordered->new( bucket => 8 );
$map->put( 42 => 'answer' );
my $value = $map->get( 42 ); # undef if absent
my $pairs = $map->range( 10, 50 ); # [ [ key, value ], ... ]
my $gone = $map->cut( 10, 50 ); # the same, removed
my $old = $map->delete( 7 ); # the value removed, or undefDESCRIPTION
An ordered map with numeric keys: put adds or replaces, get and delete return the value or undef, range( $lo, $hi ) returns the entries with lo <= key <= hi in key order as [ $key, $value ] pairs and cut removes them as well. contents (all entries in order), size and buckets look at the map without changing it.
The entries are kept in one LinkedList::Single in key order. Marker nodes divide the list into buckets of at most twice the bucket size, and a small array holds each bucket's lowest key, a cursor on its marker and its count. A binary search of that array finds the bucket and a short walk from the marker finds the entry; an insert or delete is then a change of links. Because the index points only at markers, which do not move while their bucket has entries, it never needs repair when entries come and go. Buckets that lie wholly inside a cut come out of the list in one piece.
Three classes with the same interface keep the same map in perl arrays and hashes: LinkedList::Single::Example::Ordered::Sorted (one sorted array, the test oracle), LinkedList::Single::Example::Ordered::Buckets (an array of small sorted arrays, the same two-level design without the list) and LinkedList::Single::Example::Ordered::Hash (a hash, sorted on demand). The tests drive all four with the same random operations and compare every result.
How it is benchmarked
benchmarks/60-Ordered/compare builds maps of 1,000 to 200,000 entries and reports microseconds per build insert, get, churn operation (half put, half delete), range of about 50 entries, cut of a tenth of the map and full traversal; a sweep of bucket sizes; the memory of a fresh process holding about 190,000 entries; and statements and branches counted in each implementation. benchmarks/60-Ordered/latency times every call separately, at 100,000 and 400,000 entries, and reports the median, the 99.9th percentile and the slowest call.
Why it matters
Keeping a map in order costs either a search that cannot halve (a list) or a move of everything after the change (an array). The two-level design bounds both, and the list's cost hardly grows with the size of the map. Measured on one machine, though, the array of buckets, the same design written with arrays, is faster at every size up to 800,000 entries, its slowest call is no worse, and its code is shorter; the list passes only the plain sorted array, between 200,000 and 400,000 entries. The hash is fastest for single keys and has the one slowest call that grows with the size, its rehash. The measurements and the reasons are in LinkedList::Single::Example::Ordered::POD.
SEE ALSO
LinkedList::Single::Example::Ordered::POD, LinkedList::Single