#merkle-tree #shared-data #memoization #serialization #representation #immutability

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

#1611 in Data structures

Download history 146/week @ 2024-07-22 250/week @ 2024-07-29 249/week @ 2024-08-05 112/week @ 2024-08-12 40/week @ 2024-08-19 240/week @ 2024-08-26 150/week @ 2024-09-02 117/week @ 2024-09-09 51/week @ 2024-09-16 57/week @ 2024-09-23 49/week @ 2024-09-30 66/week @ 2024-10-07 39/week @ 2024-10-14 16/week @ 2024-10-21 68/week @ 2024-10-28 42/week @ 2024-11-04

172 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.6MB
~35K SLoC