Although functional programming languages simplify writing safe parallel
programs by helping programmers to avoid data races, they have traditionally
delivered poor performance. Recent work improved performance by using a
hierarchical memory architecture that allows processors to allocate and reclaim
memory independently without any synchronization, solving thus the key
performance challenge afflicting functional programs. The approach, however,
restricts mutation, or memory effects, so as to ensure "disentanglement", a
low-level memory property that guarantees independence between different heaps
in the hierarchy.

This paper proposes techniques for supporting entanglement and for allowing
functional programs to use mutation at will. Our techniques manage entanglement
by distinguishing between disentangled and entangled objects and shielding
disentangled objects from the cost of entanglement management. We present a
semantics that formalizes entanglement as a property at the granularity of
memory objects, and define several cost metrics to reason about and bound the
time and space cost of entanglement. We present an implementation of the
techniques by extending the MPL compiler for Parallel ML. The extended compiler
supports all features of the Parallel ML language, including unrestricted
effects. Our experiments using a variety of benchmarks show that MPL incurs a
small time and space overhead compared to sequential runs, scales well, and is
competitive with languages such as C++, Go, Java, OCaml. These results show that
our techniques can marry the safety benefits of functional programming with
performance.