Memo: an incremental computation library that powers Dune
summary
Memo is an OCaml incremental-computation library that powers Dune 3.0’s faster file-watching build mode, providing concurrency with fibers, dynamic dependency discovery, error deduplication with attached call stacks, and handling of non-determinism. It uses a proven incremental cycle detector (Bender et al.) but only adds edges when blocking occurs, yielding dramatic speedups: graphs reach tens of millions of nodes with examples of 100 million edges, cycle checks drop to near zero, and the system runs in production for over a year.
AI-written summary · about
chapters (6)
- 0:00Introduction to Dune
- 1:58Build engine example
- 4:45Memo library features
- 8:40Performance challenges
- 12:28Cycle detection algorithm
- 14:44Future work and conclusion
related talks
35mOCaml Package Management with (only!) Dune
22mState of the OCaml Platform 2023
57mDealing with Medusas in your Codebase.
27mTry-Mopsa: Relational Static Analysis in Your Pocket
21mIntegrating Dependency Building with Document Checking in Coq
43mOCaml at LexiFi
22mProject-wide occurrences for OCaml, a progress report
30mReact Compiler