structural sharing
A key mechanism by which persistent data structures achieve low copying cost. When immutable data is modified, unaffected parts are reused and only the path from the modification point to the root node is newly created, so the cost of a single update is of the same order as for a mutable structure.
Timeline (last 90 days)
Structural sharing is the key mechanism by which persistent data structures achieve low copying cost, reusing unaffected parts upon modification and creating only the path from the modification point to the root node.
Inserting an element into a persistent balanced tree requires copying only O(log n) nodes, with the remaining subtrees shared via pointers, so the cost of a single update is of the same order of magnitude as for mutable structures.
The cost of structural sharing lies in extra pointer indirection and poorer cache locality, which is one reason pure FP lags behind C on some memory-intensive workloads.
All Facts (3)
Structural sharing is the key mechanism by which persistent data structures achieve low copying cost, reusing unaffected parts upon modification and creating only the path from the modification point to the root node.
50%UnverifiedInserting an element into a persistent balanced tree requires copying only O(log n) nodes, with the remaining subtrees shared via pointers, so the cost of a single update is of the same order of magnitude as for mutable structures.
50%UnverifiedThe cost of structural sharing lies in extra pointer indirection and poorer cache locality, which is one reason pure FP lags behind C on some memory-intensive workloads.
50%