/ 
Data-HashMap-0.11
/ Data::HashMap

NAME

Data::HashMap - Fast type-specialized hash maps with TTL and LRU, in C

SYNOPSIS

use Data::HashMap::II;

# Keyword API (fastest - bypasses method dispatch)
my $map = Data::HashMap::II->new();
hm_ii_put $map, 42, 100;
my $val = hm_ii_get $map, 42;    # 100
hm_ii_exists $map, 42;           # true
hm_ii_remove $map, 42;

# Method API (convenient - same operations)
$map->put(42, 100);
$val = $map->get(42);            # 100
$map->exists(42);                # true
$map->remove(42);

# Counter operations (integer-value variants only)
my $count = hm_ii_incr $map, 1;  # 1
$count = hm_ii_incr $map, 1;     # 2
$count = hm_ii_decr $map, 1;     # 1

# Iteration
my @keys   = hm_ii_keys $map;
my @values = hm_ii_values $map;
my @pairs  = hm_ii_items $map;   # (k1, v1, k2, v2, ...)
while (my ($k, $v) = hm_ii_each $map) { print "$k=$v\n" }

# Bulk operations
my $href = hm_ii_to_hash $map;   # Perl hashref snapshot
hm_ii_clear $map;                # remove all entries

# LRU cache (max 1000 entries, evicts least-recently-used)
my $lru = Data::HashMap::II->new(1000);

# TTL cache (entries expire after 60 seconds)
my $ttl = Data::HashMap::II->new(0, 60);

# LRU + TTL combined
my $both = Data::HashMap::II->new(1000, 60);

# Per-key TTL
hm_ii_put_ttl $map, 42, 100, 30;   # expires in 30 seconds

# Get or set default
my $v = hm_ii_get_or_set $map, 99, 0;  # insert 0 if key 99 absent

DESCRIPTION

Fourteen hash maps implemented in C, each specialised for one combination of key and value type. Most operations are available both as a keyword, which bypasses method dispatch, and as a method ($map->get($key)); a few are methods only.

Keywords are enabled by use Data::HashMap::XX for the rest of the enclosing lexical scope, normally the file. Each file that calls them needs its own use line; use Data::HashMap::XX () does not enable them. Without it a call still compiles, as a method call, and fails when it runs with Can't locate object method "hm_xx_get" via package "Data::HashMap::XX".

VARIANTS

Data::HashMap::I16 - int16 keys, int16 values (4-byte node)
Data::HashMap::I16A - int16 keys, any Perl value
Data::HashMap::I16S - int16 keys, string values
Data::HashMap::I32 - int32 keys, int32 values (8-byte node)
Data::HashMap::I32A - int32 keys, any Perl value
Data::HashMap::I32S - int32 keys, string values
Data::HashMap::II - int64 keys, int64 values (16-byte node)
Data::HashMap::IA - int64 keys, any Perl value
Data::HashMap::IS - int64 keys, string values
Data::HashMap::SA - string keys, any Perl value
Data::HashMap::SI16 - string keys, int16 values
Data::HashMap::SI32 - string keys, int32 values
Data::HashMap::SI - string keys, int64 values
Data::HashMap::SS - string keys, string values

KEYWORDS

Each variant provides the following keywords (replace xx with the variant prefix: i16, i16a, i16s, i32, i32a, i32s, ia, ii, is, sa, si16, si32, si, ss):

hm_xx_put $map, $key, $value    # insert/update, returns bool
hm_xx_get $map, $key            # lookup, returns value or undef
hm_xx_exists $map, $key         # returns bool
hm_xx_remove $map, $key         # returns bool
hm_xx_take $map, $key           # remove and return value, or undef
hm_xx_drain $map, $n            # remove up to N entries, returns (k1,v1,...)
hm_xx_pop $map                  # remove+return (key,val): LRU tail or next entry
hm_xx_shift $map                # remove+return (key,val): LRU head or prev entry
hm_xx_reserve $map, $n          # pre-allocate capacity for N entries
hm_xx_purge $map                # reap already-expired TTL entries
hm_xx_capacity $map             # current internal table capacity
hm_xx_persist $map, $key        # remove TTL from key (make permanent)
hm_xx_swap $map, $key, $new     # replace value, return old (undef if missing)

Integer-value variants (I16, I32, II, SI16, SI32, SI) also provide:

hm_xx_incr $map, $key           # +1, returns new value (new keys init to 0)
hm_xx_decr $map, $key           # -1, returns new value (new keys init to 0)
hm_xx_incr_by $map, $key, $n    # +N, returns new value (new keys init to 0)
hm_xx_cas $map, $key, $expected, $new  # compare-and-swap, returns bool

All variants also provide:

hm_xx_size $map                 # entry count, including expired entries not yet reaped
hm_xx_keys $map                 # returns list of keys
hm_xx_values $map               # returns list of values
hm_xx_items $map                # returns (k1,v1, k2,v2, ...)

hm_xx_max_size $map             # returns max_size (0 = no LRU)
hm_xx_ttl $map                  # returns default TTL in seconds (0 = no TTL)
hm_xx_lru_skip $map             # returns lru_skip percentage (0 = strict LRU)
hm_xx_clear $map                # remove all entries
hm_xx_to_hash $map              # returns a Perl hashref snapshot
hm_xx_each $map                            # returns (key, value) or empty list
hm_xx_iter_reset $map                      # reset each() iterator to start
hm_xx_put_ttl $map, $key, $val, $seconds   # insert with per-key TTL ($seconds=0 uses map default)
hm_xx_get_or_set $map, $key, $default      # get existing or insert default

String-value variants (SS, IS, I32S, I16S) also provide:

hm_xx_get_direct $map, $key   # zero-copy get (read-only, see CAVEATS)

Method-only operations (no keyword form):

$map->clone                     # copy the map (SV* values per its copy mode)
$map->from_hash(\%h)            # bulk-insert from a Perl hashref
$map->merge($other_map)         # copy in another same-variant map's entries
$map->freeze                    # serialize to binary string (non-SV* variants)
MyVariant->thaw($data)          # rebuild a frozen map (non-SV* variants)

CONSTRUCTOR

my $map  = Data::HashMap::II->new();              # plain (no LRU, no TTL)
my $lru  = Data::HashMap::II->new(1000);          # LRU: max 1000 entries
my $ttl  = Data::HashMap::II->new(0, 60);         # TTL: 60-second expiry
my $both = Data::HashMap::II->new(1000, 60);      # LRU + TTL
my $fast = Data::HashMap::II->new(1000, 0, 90);   # LRU + 90% skip
my $safe = Data::HashMap::SA->new(0, 0, 0, 1);    # SV* variants: copy values

The arguments are max_size, ttl in seconds, and lru_skip, each a non-negative number; the SV* variants take a fourth, copy (see "CAVEATS"). A reference, a non-numeric string or an extra argument croaks; a ttl below one second rounds up to one, and one beyond 2**32 seconds saturates.

LRU eviction

With max_size set, inserting a new key into a full map evicts the least recently used entry. Reading or writing an existing key promotes it: get, get_direct, put, put_ttl, swap, a successful cas, get_or_set and the counters do; exists, persist and a failed cas do not.

lru_skip (0-99, larger values clamp to 99) skips promotion on exactly that percentage of the accesses that would promote: 90 promotes one in ten. The least recently used entry is always promoted when touched, so it cannot be starved, and touching the most recently used one never counts. This trades eviction precision for speed on read-heavy workloads with hot keys; 90 suits most caches.

TTL expiry

With a default ttl, or a per-key one from put_ttl (which also works on a map without a default), entries expire lazily, with one-second resolution: an entry with a TTL of n seconds is readable for between n and n+1 seconds. Iteration (keys, values, items, each, to_hash) skips expired entries, and get, exists and the counters remove one they touch; size counts expired entries until they are removed.

Entries nobody touches again are reaped when the table would otherwise grow, so a map fed never-repeating keys stays bounded, at a few times its live set. purge reaps every expired entry on demand and never removes a live one.

On a map with a default TTL, put and the counters renew an existing entry's lifetime to that default -- even one given its own TTL by put_ttl or made permanent by persist -- so a counter that keeps being hit never expires. swap, cas, get_or_set on an existing key, and reads leave the expiry alone. On a map without a default the counters leave it alone too, while put clears any put_ttl deadline. get_or_set inserts with the default TTL; use put_ttl for a per-key one.

On a map with both max_size and a TTL, eviction takes the least recently used entry whether or not it has expired, and an expired entry keeps its slot and its value until it is reaped: call purge periodically so that expired entries, not live ones, make room.

Expiry is measured against the wall clock (time), so stepping the system clock moves every deadline with it; a clock set backward keeps entries alive longer.

CAVEATS

Keyword syntax

A keyword taking two or more arguments takes a plain comma list with no parentheses: hm_ii_get $m, $k. hm_ii_get($m, $k) fails to compile with "Expected ','", and => is not a separator; one-argument keywords such as hm_xx_size($m) do accept parentheses. A keyword parses like a list operator, so everything after the last comma is the last argument: hm_xx_get $m, $k // $default looks up $k // $default. Parenthesise the call when an operator follows it: (hm_xx_get $m, $k) // $default, (hm_sa_get $m, $id)->{field}. hm_xx_keys, hm_xx_values and hm_xx_items return the entry count in scalar context, which on a TTL map includes expired entries the list form skips. no Data::HashMap::XX does not remove the keywords.

Integers

Keys and values are checked against the variant's range on every call, from_hash included, and croak outside it rather than wrap. NaN croaks wherever a number is expected. INT_MIN and INT_MIN+1 are reserved as keys: put, put_ttl, get_or_set and lookups ignore them, as do swap and cas (returning undef and false), while incr, decr and incr_by croak. An undef key or value coerces as in Perl, to "" or 0, usually with a warning; SV* variants store an undef value as-is. The counters croak rather than overflow, leaving the value unchanged: incr with increment failed, decr with decrement failed and incr_by with incr_by failed. The I16 and I32 croaks name the full type range, reserved values included. A 64-bit perl (use64bitint) is required.

String keys

Identity is the key's bytes. A UTF-8-flagged key whose characters fit in one byte is downgraded first, so "caf\xe9" and its upgraded form are one key, as in a hash. A key that needs UTF-8 is returned with the flag of its most recent put, and collides with its own encoded octets: "\x{263a}" and "\xe2\x98\xba" are one key here and two in a hash, so copying a hash that holds both into a map keeps only one.

Perl values

By default the SV* variants (I16A, I32A, IA, SA) store the SV you pass, not a copy, as 0.08 did. That is the fastest option, but the stored value stays tied to the caller's variable: storing $_ in a while (<$fh>) loop leaves every entry holding the loop's final undef; a substr result, $1 or a foreach variable changes after it is stored; from_hash, clone, merge and to_hash share SVs with their source; and a stored literal is read-only. Store a copy ("$_"), or pass a true fourth argument, copy, to new: the map then copies each value it stores, as a hash does, at the cost of one SV copy per put. In either mode get, values, items and each return the map's own SV, as values %h does, and referents are shared.

Iteration and order

Key order is unspecified and differs between processes, as with Perl's own hashes; sort if you need a stable one. each restarts after clear, and whenever another write resizes or compacts the table (swap, cas and persist only do so by reaping an expired entry), so do not write to the map during each; reads are safe. In scalar context it returns the key, so a while loop over it must guard with defined -- while (defined(my $k = hm_xx_each $map)) -- or it stops early on a false key such as 0 or "". pop, shift and drain keep their own cursor, so they do not move an each in progress unless they compact the table. On an LRU map pop and shift take the least and most recently used entry; drain always goes in table order. In scalar context the three return the last value removed. pop and shift skip expired entries; on an LRU map they also reap them, and on a plain map size keeps counting them until a lookup reaps them.

get_direct

Returns a read-only SV that borrows the map's buffer instead of copying it, for immediate use such as comparing or printing. It is valid until that entry is next changed, removed, reaped or evicted, so on a TTL or LRU map treat it as valid only until the next call on the map. Arguments are evaluated before a call: f($m->get_direct($k), $m->remove($k)) hands f freed memory. my $d = $m->get_direct($k) copies, so $d is safe to keep.

freeze and thaw

The format is native-endian and not portable across byte orders. Output is not byte-stable -- table order drifts across rehashes and, with the per-process hash seed, between runs -- so do not use a frozen blob as a digest or cache key; thaw round-trips the data regardless. Each entry's remaining lifetime is stored, and thaw starts that countdown afresh, so time spent frozen does not count. A thawed LRU map has lost its recency order. A map whose max_size exceeds 4294967295 cannot be frozen: the format stores it in 32 bits, so freeze croaks. All of this applies to Storable too.

from_hash and merge

from_hash croaks on a key or value the matching put would reject, leaving the entries inserted so far in place, skips reserved keys silently, and reads tied hashes. merge copies another map's entries in, the other map winning a conflict; they take this map's TTL rules, not the other map's, so merging into a map without a TTL makes them permanent. Already-expired entries are skipped.

Capacity

A table never shrinks: remove and clear keep its capacity for reuse; build a new map to release the memory. The table is the next power of two at or above 4/3 of the entries it holds, so a full LRU map's table is between about 1.34 and 4 times max_size: smaller while filling, larger after a reserve.

Taint

The string-value variants (I16S, I32S, IS, SS) keep values in plain C buffers, so a tainted string comes back untainted. Under -T do not round-trip untrusted data through them into a sensitive operation; the SV* variants preserve taint. Keys are never tainted, as with Perl's hashes.

STORABLE

Storable's freeze, thaw and dclone work on the ten variants with a native freeze, through that format, and produce a separate map. The four SV* variants croak with freeze not supported for SV* variants; use to_hash + Storable. Clone and other deep copiers that duplicate a blessed scalar without a hook are not supported: the copy would share the C table and free it twice.

THREADS

Maps are not shared between ithreads. Every variant inherits CLONE_SKIP from Data::HashMap, so a child thread keeps the reference but it points at an unblessed undef, and DESTROY never runs on it there; without that, both interpreters would free the same C table. Test with Scalar::Util::blessed($map). A thread that needs a map should build its own, or receive the contents as a plain hash via to_hash.

PERFORMANCE

Measure on your own machine with perl -Mblib bench/all.pl; speed varies with hardware, Perl build and table size, so treat only the shape as portable.

Inserts into an integer-key map beat a Perl hash at every size -- roughly 2x at a thousand entries, widening to several times at 100k; string-key maps are faster too, by a smaller margin. Lookups trade places with size: on a small map a Perl hash is quicker, and the C map pulls ahead as the table fills, so the win is largest on big, long-lived maps. Within one key width the variants run at about the same speed -- the narrower integer types buy memory and range checks, not throughput. A keyword call is a little cheaper than the method form.

MEMORY

Bytes per entry at 1M entries, fork-isolated (16-bit rows at 30k, where int16 caps unique keys near 65k; each row exceeds its node size because the table is a power of two above 4/3 of the entries):

Variant       Bytes/entry   vs Perl hash
I16/I16A/I16S          21      8x less
I32                    30    5.5x less
II                     46    3.5x less
I32S/IS/SI/SI16/SI32   75    2.2x less
I32A/IA                95    1.7x less
SS                    124    1.3x less
SA                    144    1.1x less
perl %h (int/str)  163/170   baseline

LRU adds about 17-21 bytes per entry (two slot indices) and a TTL about 8-13 more (an expiry timestamp); each array is allocated only when its feature is used.

IMPLEMENTATION

  • Open addressing with linear probing; tombstone deletion with automatic compaction

  • xxHash v0.8.3 (XXH3_64bits_withSecret) for integer and string keys, keyed by a secret derived at load time from Perl's hash seed for DoS resistance

  • Resize at 75% load; initial capacity 16

  • LRU and TTL state in parallel arrays indexed by slot, allocated only when used, so a map without them pays one never-taken branch

  • Strings stored as raw C buffers, with the UTF-8 flag in the high bit of the length

DEPENDENCIES

XS::Parse::Keyword (>= 0.40)

AUTHOR

vividsnow

LICENSE

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