Crates.io | hashcons |
lib.rs | hashcons |
version | 0.1.2 |
source | src |
created_at | 2018-07-28 21:53:19.232275 |
updated_at | 2020-01-21 19:52:43.415392 |
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.