hashcons

Crates.iohashcons
lib.rshashcons
version0.1.2
sourcesrc
created_at2018-07-28 21:53:19.232275
updated_at2020-01-21 19:52:43.415392
descriptionHash cons'ing for compact representations of shared, immutable data structures
homepagehttps://github.com/Adapton/hashcons.rust/
repositoryhttps://github.com/Adapton/hashcons.rust/
max_upload_size
id76415
size31,513
Matthew Hammer (matthewhammer)

documentation

https://docs.rs/hashcons

README

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.

Commit count: 8

cargo fmt