Comparison
Copy-on-writevsStructural sharing
Copy-on-write
the copy was free until somebody wrote to it, and only then did the data actually get duplicated.
Sharing one underlying representation between a value and its copies until one of them is modified, at which point that one is duplicated. It gives value semantics at reference-semantics cost for the common read-only case, and it is how several standard library collections and most process forks work. Its performance cliff is the write nobody expected to be expensive, which is the same shape as every other lazy optimisation.
Full entry →Structural sharing
the new version copied five nodes rather than ten thousand elements, because everything unchanged is the same objects.
The technique that makes persistent data structures practical: an update copies only the path to the changed node and reuses every untouched subtree. It turns an apparent full copy into something logarithmic in the size of the structure. It only works because the shared parts are immutable, which is the clearest illustration of why immutability buys performance rather than only costing it.
Full entry →