KC Sivaramakrishnan, Stephen Dolan, Leo White
Sadiq Jaffer, Tom Kelly, Anmol Sahoo, Sudha Parimala, Atul Dhiman, Anil Madhavapeddy
2020 · arXiv
OCaml is an industrial-strength, multi-paradigm programming language, widely used in industry and academia. OCaml is also one of the few modern managed system programming languages to lack support for shared memory parallel programming. This paper describes the design, a full-fledged implementation and evaluation of a mostly-concurrent garbage collector (GC) for the multicore extension of the OCaml programming language. Given that we propose to add parallelism to a widely used programming language with millions of lines of existing code, we face the challenge of maintaining backwards compatibility--not just in terms of the language features but also the performance of single-threaded code running with the new GC. To this end, the paper presents a series of novel techniques and demonstrates that the new GC strikes a balance between performance and feature backwards compatibility for sequential programs and scales admirably on modern multicore processors.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
13 selected excerpts · 13 total mentions
Signals and Threads had an interview with Anil Madhavapeddy last year: https://signalsandthreads.com/what-is-an-operating-system/ He talked about the work to put a multicore-ready memory model[1] and GC[2] under OCaml. [1] https://anil.recoil.org/papers/2018-pldi-memorymodel.pdf [2] https://arxiv.org/abs/2004.11663
Along with the graphs from the PR in the sibling comment, there's also the extensive benchmarking from the ICFP2020 paper: https://arxiv.org/pdf/2004.11663.pdf Work on this is on-going via the sandmark benchmarking suite: https://github.com/ocaml-bench/sandmark In short the expectation should be that single-threaded code performs roughly the same (single digit percentage changes) as on the sequential runtime. Parallel code on multicore can see close to linear speedups on 64 cores, though it depends significantly on your workload. If you're interested in parallelising existing OCaml code, I gave an example-driven OCaml workshop talk in 2020: https://www.youtube.com/watch?v=Z7YZR1q8wzI
I am going to put a direct link to the paper because it's basically an answer to this question: https://dl.acm.org/doi/epdf/10.1145/3408995 If you don't want to read much, just read parts 1.3 and 1.4. Quoting the introduction to each parts should give you an idea of what is discussed. The article is well written. Introduction "Adding shared-memory parallelism to an existing language presents an interesting set of challenges. As well as the difficulties of memory management in a parallel setting, we must maintain as much backwards compatibility as practicable. This includes not just compatibility of the language semantics, but also of the performance profile, memory usage…
and C bindings." 1.1 - Performance Backwards Compatibility "The main challenge in adding support for shared-memory parallelism to OCaml is the implementation of the multicore-capable GC. OCaml users have come to rely on allocation and memory access being relatively cheap (for a managed language) in order to write performant code" 1.2 - Feature Backwards Compatibility "Given the millions of lines of OCaml code in production, it would serve us well to ensure that the addition of parallelism to OCaml breaks as little code as possible. OCaml is a type-safe language and the addition of parallelism should not break type safety under data races." 1.3 - Requirements "In summary, we strive towards the following ideal goals in our parallel extension of OCaml: R1 - A well behaved serial program does not break on the parallel extension. That is, a well-typed serial program remains well-typed in the parallel extension, and the semantics of such a program remains the same on the serial and parallel runtimes. R2 - The performance profile of a serial program on the parallel runtime remains the same as the serial runtime. That is, the program on the parallel runtime should run as fast as it does on serial runtime. Additionally, the GC pause times of the serial program on the parallel runtime remain the same as the serial runtime. R3 - The parallel programs should aim to minimize pause times, and then aim to run as fast as possible on the available cores. We order the sub goals this way since minimising pause times in the GC is much harder than achieving good throughput. We believe that once the pause times are optimised for, optimising for throughput is easier, but the vice versa is much harder." 1.4 - Contributions "Our contributions are to present: • the design of a mostly-concurrent, non-moving, mark-and-sweep GC for the older generation that minimizes pause times for a parallel extension of OCaml. • two collector designs for the young generation: (i) a concurrent collector that minimizes pause times at the cost of breaking the C API and; (ii) a stop-the-world parallel collector that retains the backwards compatibility of the existing C API. • extensions of our baseline collectors to advanced language features that interact with the GC such as lazy values, finalisers, weak references and ephemerons. Our novel design minimizes the number of global synchronizations necessary for collecting a deeply nested hierarchy of ephemerons. This design has been verified in the SPIN model checker. • support for fibers that run in parallel, which are language level lightweight threads imple- mented as runtime managed stack segments. The implementation of fibers is similar to lightweight threads in Haskell GHC and Goroutines in the Go language. While the details of the language support for fibers is beyond the scope of the paper, we describe the subtle interaction of our concurrent GC algorithm with fibers. • extensive evaluation of the collector designs in a full-fledged implementation of a parallel ex- tension of OCaml. Our experiments illustrate that (i) serial programs retain their performance profile on the new collectors, and (ii) parallel programs achieve good multicore scalability while preserving low pause times with increasing number of cores."
No breaking changes with the parallel minor collector (ParMinor). This is the design which will be upstreamed. See https://arxiv.org/pdf/2004.11663.pdf for details.
It involved a fair amount of research and there were many technical challenges. Maintaining backwards compatibility in terms of language features and single-threaded performance puts constraints around what you can implement. Also from my personal experience, debugging segfaults in parallel programs that could be caused by GC bugs is a painstaking process. We've written a couple of papers detailing the internals and the trade-offs involved: https://arxiv.org/abs/2004.11663 (for parallelism) and https://arxiv.org/abs/2104.00250 (for effects) Added to that is the complexity of tracking a moving target. Multicore had to be rebased through 12 releases of OCaml, which in itself was a non-trivial amount of work.
Our paper from ICFP last year has extensive benchmarks against stock OCaml: https://arxiv.org/abs/2004.11663 In short there should be very little performance difference against stock. As KC has linked in a sibling comment there's a project going to explore using effects to write high performance IO libraries and that has some early benchmarks.
As the sibling comment mentions, the hard part is actually retrofitting multicore whilst maintaining compatibility _and_ performance. Our paper last year covers most of why this is tricky: https://arxiv.org/abs/2004.11663
Multicore is almost entirely backwards compatible with stock OCaml. One issue is C libraries that use so-called naked pointers but these are discouraged anyway and 4.12 ships a detector to find these: https://discuss.ocaml.org/t/ann-a-dynamic-checker-for-detect... There are also two functions on the Obj module which aren't supported because they're unsafe to do concurrently. These are clearly marked as "not for the casual user" so their use is relatively rare. With regards to performance, you can find a fairly detailed analysis in our ICFP 20 paper: https://arxiv.org/abs/2004.11663 In short, the impact is 3-4% across those benchmarks. You can grab the current multicore compiler on https://github.com/ocaml-multicore/ocaml-multicore and give it a spin to see, today.
Unfortunately some of this information is out of date and refers to Multicore with the concurrent minor collector - a collector we don't plan to upstream. We plan to upstream the parallel minor collector, which has a shared minor heap across all domains. It maintains compatibility with the existing C API and seems to perform well. You can find more information on both the concurrent minor collector and the parallel minor collector in the recent ICFP paper: https://dl.acm.org/doi/10.1145/3408995 You can also see KC's talk on the paper here: https://www.youtube.com/watch?v=ASX79I0jm6M&feature=youtu.be... -- The TL;DR on Domains is that they're heavyweight threads. You essentially want as many as you have cores. Our talk (separate to the one above) at the OCaml Workshop also covers a lot of the terminology and how to get started with Multicore today: https://www.youtube.com/watch?v=Z7YZR1q8wzI&list=PLKO_ZowsIO...
Just to add to this good summary, OCaml already has some support for parallelism that would be useful for scientific computation. Essentially you can already have multi-threaded OCaml programs as long as only one thread is using the OCaml runtime at any point in time. For numerical code where you might be spending the vast majority of your time in external libraries this ends up not being a major problem. It's not a dissimilar story for where Python is. What Multicore OCaml adds is the ability to run multiple threads of OCaml code at the same time (we call them Domains, to avoid confusing them with existing Threads - which can coexist). There's an entry on the Multicore…
wiki that gives some more depth: https://github.com/ocaml-multicore/ocaml-multicore/wiki/Conc... In terms of the project you can also follow progress in the Multicore Monthlies: https://discuss.ocaml.org/tag/multicore-monthly as well as see the in-progress and merged multicore PRs that are hitting upstream ocaml: https://github.com/ocaml/ocaml/pulls?q=is%3Apr+label%3Amulti... If you want to know more about how the multicore runtime works the recent ICFP2020 paper has a lot of detail: https://arxiv.org/abs/2004.11663 and KC's presentation is worth a watch: https://www.youtube.com/watch?v=ASX79I0jm6M&feature=youtu.be...
Better throughput, and almost no impact on latency overall. See https://arxiv.org/abs/2004.11663 section 6.2 for parallel performance evaluation.
(Multicore OCaml hacker here - speaking for myself though) Nice to see people having a look at this. It's an early draft chapter that Sudha, one of the Multicore team, has been working on. If you have feedback or suggestions I'm sure she'd welcome it on the draft's PR: https://github.com/prismlab/parallel-programming-in-multicor... If you're new to Multicore OCaml the repo is at https://github.com/ocaml-multicore/ocaml-multicore . It has installation instructions near the bottom (easiest way is via OPAM). The latest June update of our progress is available at https://discuss.ocaml.org/t/multicore-ocaml-june-2020/6047 For a technical deep dive on how Multicore OCaml works our recent ICFP paper has a lot of detail: https://arxiv.org/abs/2004.11663
We have a preprint up of our paper that details the design of Multicore OCaml along with a range of performance comparisons: https://arxiv.org/abs/2004.11663 In terms of performance it varies. The benchmarks in that paper it ranges from a 20% slowdown to a 20% speedup - most macro benchmarks are <10%. There's also still some more performance work we can do to chip away at that further.
More from the same topics.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
Ross Mcilroy, Jaroslav Sevcik, Tobias Tebbi +2
The recent discovery of the Spectre and Meltdown attacks represents a watershed moment not just for the field of Computer Security, but also of Programming Languages.
Daniel Ingalls
This paper presents a personal view of the evolution of six generations of Smalltalk in which the author played a part, starting with Smalltalk-72 and progressing through Smalltalk-80 to Squeak and Etoys.
Donald E. Knuth