LNATION

Modules · Data · 0.03

HAMT

Persistent maps, sets and vectors on a hash array mapped trie.

An update returns a new container and leaves the one it was called on exactly as it was. The two share nearly all their memory, so keeping the old one costs a few small nodes, not a copy: a snapshot, an undo step or a value handed to code that must not change it is as cheap as holding a reference.

On MetaCPAN 

use HAMT::Map;

my $config = HAMT::Map->new(db => 'prod', timeout => 30);
my $trial  = $config->set(timeout => 5);    # a new map; $config is unchanged

print $config->get('timeout'), "\n";        # 30
print $trial->get('timeout'), "\n";         # 5

# what changed between two versions, looking only where they differ
$config->diff($trial, sub {
    my ($key, $was, $now, $kind) = @_;
    print "$kind $key: $was -> $now\n";     # change timeout: 30 -> 5
});

What you get

  • Persistent

    An update returns a new container and leaves the old one exactly as it was. Changing a key replaces the few nodes between the root and that key, and every other node is shared between the versions.

  • Map, Set and Vector

    HAMT::Map and HAMT::Set are a hash array mapped trie, 32 wide. HAMT::Vector is the same kind of tree read by position, with push, insert, slice and concat.

  • Compare versions by their differences

    merge, equals and diff look only where two versions differ, so a set compared with its earlier self costs what changed, not its size.

  • Transients for building

    To build, use new, from_hash or a transient: an update at a time in a loop is several times slower than any of them.

  • Values are read-only

    A stored value is copied and the copy is read-only, shared by every version. This is shallow: what a stored reference points at is still the caller's to change.

In use

use HAMT::Set;
use HAMT::Vector;

my $before = HAMT::Set->new(qw(read write));
my $after  = $before->add('admin')->remove('write');
print join(',', sort $after->members), "\n";        # admin,read
print $before->has('write') ? "kept\n" : "lost\n";  # kept

my $v  = HAMT::Vector->new(1 .. 5);
my $v2 = $v->push(6)->set(0, 'one');
print join(',', $v2->list), "\n";                   # one,2,3,4,5,6

Measured in its POD

One run on one machine (Apple M5, perl 5.42.0), as the module's POD records it, with the scripts in its bench/ directory:

One set on 10,000 keys: 3,000 times faster than copying the hash. A union of two versions of a set: 5,000 times faster than (%a, %b). A thousand versions of a 10,000-key map: 1/249 the memory of a thousand copies. A million keys: 0.69 times the memory of a hash.

And the costs: a get of a present key is 2.1 times slower than a hash fetch, and building 100,000 keys 1.4 to 1.9 times slower than a hash.

For C

hamt_abi.h, installed with the module and found through ExtUtils::Depends, gives another extension's C everything the three classes do from Perl: reading, updating, walking, merging, comparing, cutting and joining, with no Perl call in between. The table is versioned and resolved at run time, so the two distributions upgrade independently.

Get it

cpanm HAMT

HAMT on MetaCPAN Every module