Parallel traversal effect handlers for OCaml
This is an idea proposed in 2024 as a Cambridge Computer Science Part II project, and is currently being worked on by Sky Batchelor. It is co-supervised with Patrick Ferris.
Most existing uses of effect handlers perform synchronous execution of handled
effects. Xie et al proposed a traverse handler for parallelisation of
independent effectful computations whose effect handlers are outside the
parallel part of the program. The paper [1] gives a sample implementation as a
Haskell library with an associated λp calculus that formalises the parallel
handlers.
This project aims to:
- implement the
traversehandler in OCaml 5, using single-shot handlers [2] - identify a selection of parallel-friendly data structures that might benefit from such parallel traversals
- investigate handlers for alternative traversal strategies beyond the folds support by
traverse - evaluate the performance of such parallel handlers, for instance using Eio's
Domain_pool[3] on a many core machine (ranging from 8--128 cores)
Related reading
-
Parallel Algebraic Effect Handlers describes the
↩︎︎traverseeffect -
Retrofitting effect handlers onto OCaml, PLDI 2021 describes how the effect system in OCaml works.
↩︎︎ -
EIO is a high-performance direct-style IO library we have been developing for OCaml.
↩︎︎
ideasRelated News
- Retrofitting effect handlers onto OCaml / Jun 2021
- OCaml Labs / Jan 2012