| Crates.io | hashcons |
| lib.rs | hashcons |
| version | 0.1.2 |
| created_at | 2018-07-28 21:53:19.232275+00 |
| updated_at | 2020-01-21 19:52:43.415392+00 |
| description | Hash cons'ing for compact representations of shared, immutable data structures |
| homepage | https://github.com/Adapton/hashcons.rust/ |
| repository | https://github.com/Adapton/hashcons.rust/ |
| max_upload_size | |
| id | 76415 |
| size | 31,513 |
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.
Merkle<_> is implemented and tested.Hc<_> is a minor variation; it remains as future work.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).
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.