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.