Lazy Incremental Copying and Structure Sharing

28 concepts10 papers1 proposal

In computational linguistics and logic programming, unification is the fundamental operation used to merge feature structures, directed acyclic graphs (DAGs), or logical terms. However, because parsing and logic execution are inherently non-deterministic, systems must explore multiple alternative paths. If an operation modifies a graph directly—known as destructive unification—it corrupts that data structure for alternative search branches.

To preserve the original states for backtracking, traditional engines performed a full copy of the input structures before every merge operation. This preemptive copying creates a massive computational bottleneck, wasting memory and processing time duplicating large, complex structures for operations that might fail immediately or only modify a tiny, localized region.

The solution to this bottleneck is lazy structure sharing and incremental copying. The core intuition is simple: treat existing data structures as immutable, share them across different versions, and defer duplication until a modification is guaranteed and strictly necessary.

The Core Intuition: Share First, Copy on Demand

Instead of copying an entire graph upfront, a structure-sharing system allows multiple contexts to point to the same physical memory.

Early unification environments, such as the D-PATR system developed by Karttunen, identified that avoiding data structure duplication was the single most critical factor for scaling parser performance (D-PATR: A Development Environment for Unification-Based Grammars). To achieve this, Karttunen et al. introduced a lazy copying approach using binary trees in Structure Sharing with Binary Trees.

When a search path branches, the system initially duplicates only the root node of the data structure. All child nodes are shared via pointers back to the original structure. Unchanged data remains shared across multiple versions indefinitely; a subordinate node is only copied if a destructive update is explicitly required within that specific branch.

Initial State (Shared):
Branch A Root ----> [ Root Node ]
                     /        \
                    v          v
            [ Left Child ]   [ Right Child ]
                                   ^
Branch B Root ----> [ New Root ] --/  (Lazy copy of root only)

Wroblewski advanced this concept by integrating the copying process directly into the unification traversal itself in Nondestructive Graph Unification. By augmenting graph nodes with dedicated copy pointers and status indicators, the algorithm tracks the relationship between original and new structures in real time. This ensures that new nodes are only constructed along successful merge paths, completely eliminating the wasted effort of copying structures for operations that fail prematurely.

Overcoming the Path Copying Problem

While lazy copying reduces upfront costs, a naive implementation suffers from the path copying problem. If a deeply nested leaf node must be modified, every ancestor node along the path from the root down to that leaf must also be duplicated to maintain structural integrity and prevent the modification from leaking into shared contexts.

Path Copying Problem:
[Root] -> [Node 1] -> [Node 2] -> [Modified Leaf]
  |         |          |          |
  v         v          v          v
[Copy] -> [Copy 1] -> [Copy 2] -> [New Leaf Value]
(Every ancestor must be duplicated just to change one leaf)

To mitigate this overhead, Godden applied functional programming principles to graph unification in Lazy Unification. Instead of copying an entire path, the system performs incremental copying by replicating only the specific node undergoing modification. The children of this newly copied node are transformed into suspended closures (thunks). Evaluation and replication of the lower branches are deferred until they are explicitly accessed, effectively bounding the memory footprint to the active path.

Emele formalized this as Lazy Incremental Copying (LIC) in Unification with Lazy Non-Redundant Copying. LIC relies on partial path sharing, allowing newly generated graph structures to point directly back to unchanged segments of the original data structures.

Furthermore, the system uses a generation-based tracking system to implement conditional structure duplication. If a node is already part of the current computation's active generation, the system performs an in-place merge or a simple pointer update rather than allocating new memory, reducing total processing time by up to 70%.

Tracking Dependencies for Safe Reuse

To safely share structures without causing side effects across different search paths, the system must carefully track node dependencies and modification states.

Kogure introduced a formal copy-dependency mechanism in Strategic Lazy Incremental Copy Graph Unification. This mechanism explicitly maps which nodes depend on others for copying, providing a structured framework to manage exactly when and where a graph requires duplication during a merge.

This tracking becomes especially powerful when combined with quasi-destructive unification. As Tomabechi demonstrated in Quasi-Destructive Graph Unification with Structure-Sharing, data-structure sharing can be managed with minimal overhead by returning an extra flag during traversal. This flag indicates whether a node or any of its descendants have been modified. A modified copying function uses this flag to reuse existing nodes directly, eliminating redundant, early, or over-copying.

Quasi-Destructive Sharing with Metadata:
[ Node Structure ]
 ├── Data / Features
 ├── Copy Pointer (Points to new instance if copied)
 ├── Reuse Field  (Tracks left/right input origin)
 └── Modified Flag (True if descendants changed)

To prevent invalid sharing configurations where nodes from different inputs might conflict, Kogure introduced a dedicated reuse field within the node metadata in Structure Sharing Problem and Its Solution in Graph Unification. This field tracks whether a node belongs to the left input, the right input, or both. During unification, the system checks this field to verify whether a node can be safely reused in place or if it must be isolated, ensuring absolute correctness during complex graph merges.

Broader Applications

As summarized by Kiefer et al. in A Bag of Useful Techniques for Efficient and Robust Parsing, the ultimate goal of these strategies is to avoid the overhead of creating new data structures entirely until a successful merge is guaranteed, maximizing the reuse of input components.

While heavily developed within the context of natural language parsing and graph unification, the principle of lazy structure sharing generalizes to any non-shared memory or distributed computing environment where data copying degrades performance.

For instance, Zhang et al. applied this concept to parallel Prolog implementations in A Non-shared Binding Scheme for Parallel Prolog Implementation. By implementing tail sharing for list structures, new lists are allowed to reference the memory of existing list tails. This optimization cuts data-copying overhead in half across distributed execution environments while fully preserving the independence of local execution contexts.

Key Foundational Work

Structure Sharing with Binary Trees (1985) — contributed 2 concept elements to this direction.
D-PATR: A Development Environment for Unification-Based Grammars (1986) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_lazy_structure_sharing_bb373660,
  title = {lazy structure sharing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lazy-structure-sharing/rdr_bb37366001d84f40bec25038b26a41e3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_lazy_structure_sharing_bb373660_v1,
  title = {lazy structure sharing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lazy-structure-sharing/rdr_bb37366001d84f40bec25038b26a41e3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake