HAMT: persistent maps, sets and vectors for Perl

HAMT is a new CPAN distribution that gives Perl three persistent containers: HAMT::Map, HAMT::Set and HAMT::Vector. "Persistent" here means an update never changes the container you call it on. It returns a new one, and the old one stays exactly as it was.

That sounds expensive. With a Perl hash it is: to keep the old version you copy/clone the whole hash, so one change to a 100,000 key hash costs 100,000 copies. HAMT makes the same change by building four or five small nodes, and the new version shares everything else with the old one.

This is useful anywhere a program copies a hash or array only so it can change it safely.

A quick tour

Every update method returns a new container. The receiver never changes.

use HAMT::Map;

my $m  = HAMT::Map->new(a => 1, b => 2);
my $m2 = $m->set(c => 3);
my $m3 = $m2->set(a => 10)->delete('b');

$m->get('a');        # 1: $m is what it always was
$m->exists('c');     # false
$m2->get('c');       # 3
$m3->get('a');       # 10, and $m2 still says 1

Sets have the usual algebra:

use HAMT::Set;

my $s  = HAMT::Set->new(qw(a b c));
my $s3 = $s->add('d')->remove('a');

my $both   = $s->intersect($s3);
my $either = $s->union($s3);
my $mine   = $s->difference($s3);
$both->is_subset($s);       # true

Vectors index from zero and also join and cut cheaply:

use HAMT::Vector;

my $v    = HAMT::Vector->new(qw(a b c));
my $v2   = $v->push('d')->set(0, 'A');
my $both = $v->concat($v2);          # a b c A b c d
my $mid  = $both->slice(2, 3);       # c A b
my $more = $both->insert(1, 'x');    # a x b c A b c d

Calling an update in void context is almost always a habit carried over from hashes, so it warns and does nothing:

$m->set(k => 1);    # Useless use of HAMT::Map::set in void context

Comparing versions

Two versions of one map can be merged, compared or diffed. The cost is proportional to what differs between them, not to their size:

my $n = $old->diff($new, sub {
    my ($key, $was, $now, $kind) = @_;   # kind: add, remove or change
    print "$kind $key\n";
});

my $sum = $m->merge($other, sub {
    my ($key, $mine, $theirs) = @_;
    return $mine + $theirs;
});

Batches of updates

When you build a large map in one go, a transient skips the per step copying. It is changed in place, then closed into an ordinary map:

my $t = $m->transient;
$t->set("key$_" => $_) for 1 .. 100_000;
my $m2 = $t->persistent;      # $m is unchanged

Values are shared and read-only

A stored value is copied once and made readonly, and every version shares that one scalar. This is shallow: a stored array ref cannot be replaced, but the array it points to can still be changed. Store data you do not intend to change, or a HAMT container, which is safe all the way down.

How it works: the hash array mapped trie

HAMT stands for hash array mapped trie, the structure Phil Bagwell described in 2001 and that Clojure and Scala later made the standard for persistent maps. HAMT::Map uses the CHAMP refinement of it. The idea fits in a few steps.

1. The hash is the path

Every key is hashed to 64 bits. Suppose the low bits of "apple" hash as below. The trie reads that hash five bits at a time, and each five-bit group is a number from 0 to 31: which of 32 branches to take at that level.

hash of "apple"  ...  00111  10010  01101
                      level 2 level 1 root
                        7      18     13

So "apple" lives at position 13 of the root, then position 18 of that child, and so on down. A key only goes as deep as it needs to: it stops at the first level where no other key shares its prefix. With 32 branches per level, 100,000 keys need about four levels, and a million need about five.

The hash is seeded per process. Without a seed, anyone feeding keys into a map could choose keys that all share one path.

2. Nodes store only what is there

A node with 32 pointer slots, most of them empty, would waste a lot of memory. Instead each node has a 32-bit bitmap with one bit per position, and an array holding only the occupied positions. To find the slot for position p, count the set bits below p:

slot(p) = popcount(bitmap & ((1 << p) - 1))

popcount is a single CPU instruction on modern hardware, so this is as fast as indexing a full array. A node holding three things is allocated with room for about three, not 32.

CHAMP splits that bitmap in two. datamap marks positions holding a key and value; nodemap marks positions holding a child node. Entries are packed at the front of the array and children at the back, which keeps a node's entries together for fast iteration and makes equality checks simpler.

3. Inserting

Follow the hash down until one of three things happens:

1. The position is empty. Set its bit in datamap and put the entry there.
2. The same key is there. Replace its value.
3. A different key is there. Both keys share the hash bits so far, so make a new child node, move the old entry into it, and insert the new key into that child at the next five bits. Repeat if they still share bits.

Twelve levels use 60 bits of the hash. Two keys whose hashes agree on all 60 bits go into a small collision node: a plain list, searched one by one. With a decent hash this almost never happens.

Deleting runs the other way. When a child is left holding a single entry, that entry moves back up into its parent and the child is freed. So a given set of keys always produces the same tree shape, however it was built. That property matters later.

4. Path copying

This is the step that makes the structure persistent. An update never writes into an existing node. It copies only the nodes on the path from the root to the key, changes the copies, and points the new root at them. Every node off that path is shared, by pointer, between the old version and the new one.

$m2 = $m->set(apple => 2)

$m                                $m2

root                              root *
 |-- A                             |-- A            (the same node)
 |-- P                             |-- P *
 |    |-- apple: 1                 |    |-- apple: 2 *
 |    `-- C                        |    `-- C       (the same node)
 `-- B                             `-- B            (the same node)

* = allocated by the set

The new root, the one node on the path, and the node holding "apple" are new. A, B and C each exist once in memory, and both versions point at them.

At four levels deep, a set on a 100,000 key map allocates four small nodes. The other several thousand nodes are shared. Both versions are complete, independent maps, and each node is reference counted, so a node is freed when the last version using it goes away.

5. Why comparing versions is cheap

Path copying gives merge, equals and diff a shortcut. When two maps came from the same ancestor, every subtree they did not both change is the same node, at the same address. Comparing two identical pointers answers "are these subtrees equal?" without looking inside.

So $old->diff($new) walks both trees together and skips every shared node. It only descends where the pointers differ, which is along the paths that were actually updated. The canonical shape from step 3 is what makes this safe: two maps with the same keys always have the same shape, so differing subtrees can be compared position by position.

6. Not copying when nobody is looking

Copying a node is only needed if someone else can see it. Each node carries a reference count, and a node whose count is one belongs to a single version. A transient uses this: it edits nodes it owns in place and copies only those still shared with the map it came from. Building 100,000 keys through a transient therefore copies each node at most once, not once per key.

The vector: the same tree, read by position

HAMT::Vector uses the same 32-wide tree, with path copying, but indexes it by position instead of by hash. Values sit in leaves of 32. To find index i, take five bits of i per level, highest level first:

index 1000 = 00000 11111 01000
             root  child  leaf
              0     31     8

There is no bitmap here. A vector that has only been pushed to is dense: every leaf is full except the last, so the five bits are the slot.

The tail

The last 1 to 32 values are kept outside the tree in a leaf of their own, called the tail. A push adds to the tail and a pop takes from it, so nearly every push and pop touches one small node and no path. Only when the tail fills is it moved into the tree as a full leaf, one path copy per 32 pushes.

Relaxed nodes, for concat and slice

Joining two vectors, or cutting a slice out of one, leaves some nodes along the join or the cut only part full. Now the index bits no longer give the slot directly. Those nodes become relaxed: each carries a small table of how many values lie under its first child, its first two, and so on. A lookup guesses the child from the index bits, then steps forward along the table a place or two.

This is the RRB tree (relaxed radix balanced), from Bagwell and Rompf, 2011. To keep lookups close to the dense case, concat and slice repack the nodes along each seam until only a few spare slots remain. That keeps the tree's height near what a dense vector would have.

With concat and slice cheap, insert and remove in the middle of a vector follow for free: cut at the point, then join the pieces with the new values between them. No values that stay put are copied.

A C ABI for other XS modules

Everything the classes do from Perl can also be done from another extension's C, with no Perl call in between. The interface is one installed header, hamt_abi.h, found through ExtUtils::Depends:

my $pkg = ExtUtils::Depends->new('My::Module', 'HAMT');

Nothing is linked against. The function table is looked up once at load time and is versioned, so the two distributions can be upgraded independently.

Getting it

HAMT 0.02 is on CPAN. It needs perl 5.10 or later and a C compiler, and has no other dependencies.

cpanm HAMT

It is released under the Artistic License 2.0. Bug reports and ideas are welcome.