Efficient parallel functional programming with effects

Jatin Arora, Sam Westrick, Umut A. Acar
[doi] [Google Scholar] [DBLP] [Citeseer] [url]

Proc. ACM Program. Lang. 7(PLDI)
Association for Computing Machinery
New York, NY, USA
jun 2023
Note(s): garbage collection, parallelism, effects

Problem: memory management overheads due to handling pointers between the heap used by each thread. (Locking overheads, etc)

Key terminology: “entanglement”: threads have to cooperate in order to perform garbage collection. We want “disentangled” objects for performance and to be able to distinguish them from “entangled” objects so that object sharing overheads are proportional to the amount of entanglement. (Specifically, read/write barrier techniques only need to be used on entangled pointers.)

Threads in Parallel ML (MPL) form a hierarchy (I think because the language uses a form of fork-join concurrency). We can classify entangled pointers as either up-pointers (it came from parent thread), down-pointers (it points to child thread) or cross-pointers (everything else).

The bulk of the paper is about the cost model, GC implementation and the performance evaluation. The evaluation compares performance against other (non-functional) parallel languages and evaluates the relativecost of entangled and disentangled pointers.