#merkle-tree #memoization #structures

hashcons

Hash cons'ing for compact representations of shared, immutable data structures

2 releases

0.1.2 Jan 21, 2020
0.1.1 Jul 28, 2018

#1953 in Data structures

Download history 28/week @ 2024-12-11 57/week @ 2025-01-01 58/week @ 2025-01-08 84/week @ 2025-01-15 6/week @ 2025-01-22 14/week @ 2025-01-29 164/week @ 2025-02-05 160/week @ 2025-02-12 328/week @ 2025-02-19 173/week @ 2025-02-26 305/week @ 2025-03-05 105/week @ 2025-03-12 36/week @ 2025-03-19 55/week @ 2025-03-26

520 downloads per month

MPL-2.0 license

15KB
239 lines

Hash Cons'ing for Rust

Sometimes, an Rc<T> is insufficient for efficient, compact immmutable structures.

By contrast:

  • A Merkle<T> gives a compact serialization in the presence of sharing.

  • A Hc<T> gives a unique representation in the presence of sharing.

Status

  • The type Merkle<_> is implemented and tested.
  • The type Hc<_> is a minor variation; it remains as future work.

Background

Sometimes, we want a shared instance of some type T that serializes once, not once per reference, as is the case with the Rc type.

Unlike a "bare" Rc<T>, a Merkle<T> enjoys the practical property that, when a structure holding multiple (shared) instances of Merkle<T> is serialized, this serialized output holds only one occurrence of each T's serialized representation; the other occurrences merely consist of the T's unique identifier (the serialization of an Id, single machine word on modern machines).

Implementation summary

A Merkle<T> has a unique ID (computed as a hash) that permits table-based indirection, via temporary storage used by serialization and serialization logic.

By contrast, a bare Rc<T> lacks this indirection, and thus, it lacks a compact serialized representation for structures with abundant sharing. Generally, abundant sharing via many shared Rc<_>s leads to exponential blow up in terms of serialized space and time.

Dependencies

~0.7–1.5MB
~33K SLoC