Introduction
Overview of relevant concepts.
Hashing
Producing a signature of an objects based on its contents.
Hash Consing
A constructor is a function which runs automatically to setup an object. The constructor must run to obtain a new object.
Strengths
- Pointer equality
- Saving space
Issues
- Overhead on construction.
- Hash table can become large.
Immutability
Strengths
- Great for shared data. Multiple threads can share the same data with no synchronization issues.
Issues
- Requires more copy on write, which can cause copy overhead.
Reference Counting
Reference Counting @ Wikipedia
Strengths
- Shared ownership of data.
- Prevents use-after-free. A reference is necessary to use the data, and the data will be there as long as at least one reference exists.
- References are cheap to pass and copy.
Issues
- Cannot reclaim reference cycles.
- Overhead for incrementing/decrementing reference counts, which must be atomic because the count is shared.
- Necessary indirection, even when the data is small. This may decrease performance by adding unprefetched random memory accesses.
Persistent Data Structures
Persistent Data Structures @ Wikipedia
Strengths
- Avoid storing duplicate information.
- Can make copies and updates faster, by reducing copying of data.
Directed Acyclic Graph
Directed Acyclic Graph @ Wikipedia
Directed graph is a structure composed on nodes/vertices connected by edges with a direction.
Strengths
- Clearer ownership compared to a graph with cycles
Merkle Tree
Strengths
- Integrity
Issues
- Overhead of performing hashing and storing hashes
- Requires data to be immutable
- Requires more copy on write, which can cause copy overhead.
Rewriting
Relevant search terms: "Term rewriting", "DAG rewriting", "Rewrite rules" (results for this one are typically overwhelmed by URL rewrite rules for web servers).
Strengths
- Systematic modification of structure data
Memoization
Strengths
- Avoiding redundant work
Issues
- Cache invalidation problem