Provably Space Efficient Parallel Functional Programming
summary
Proves that determinacy‑race‑free parallel ML runs need at most O(R · P) space and at most O(W + R · P) work by integrating a heap scheduler with work‑stealing: partitioning the heap into bubbles assigned to processors so each can allocate without syncing and collect locally using closures, remembered sets and snapshotting. Implementation in the Maple/MPL compiler uses private moving collectors and concurrent non‑moving public collectors and matches highly optimized Java/Go sorting on up to 70 cores in time while keeping space blowup well under the theoretical P factor.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 1:07Procedural languages
- 1:41Functional languages
- 3:36Memory Management Challenges
- 4:45Memory Management Techniques
- 5:52Performance Comparison
- 7:51Heap Runtime
- 8:20Heap Tree
- 10:41Space Bound
- 12:44Entanglement
- 14:00Collecting Bubbles
- 15:11Heap Collection
- 16:35Maple
- 16:58Benchmarks
- 18:34Blowups
- 19:35Public Collections
- 21:17Summary