4 ms·

OCaml Labs breakthrough – good things come to those who wait

32 points by virtualwhys 6y ago

k0t0n0 6y ago
Neat ! So does that mean before 2022 we will have multi-core ocaml?
- pjmlp 6y ago
  https://discuss.ocaml.org/tag/multicore-monthly https://discuss.ocaml.org/tag/multicore-monthly
brundolf 6y ago
Can anyone give a tl;dr for why this was so difficult, and how they solved it? Don't FP languages typically lend themselves more easily to parallelism?
- blandflakes 6y ago
  My understanding was that the challenge wasn't in getting things "right", it was in introducing parallelism in a way that didn't negatively impact core performance. In other words, they didn't want to go back. Though, OCaml is also not purely functional - I don't know to what degree OCaml's various escape hatches would have hindered multicore. All the text I've seen is about avoiding regression.
- brmgb 6y ago
  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 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."

32 points by virtualwhys 6y ago

k0t0n0 6y ago

Neat ! So does that mean before 2022 we will have multi-core ocaml?

pjmlp 6y ago
https://discuss.ocaml.org/tag/multicore-monthly https://discuss.ocaml.org/tag/multicore-monthly

brundolf 6y ago

Can anyone give a tl;dr for why this was so difficult, and how they solved it? Don't FP languages typically lend themselves more easily to parallelism?

blandflakes 6y ago
My understanding was that the challenge wasn't in getting things "right", it was in introducing parallelism in a way that didn't negatively impact core performance. In other words, they didn't want to go back. Though, OCaml is also not purely functional - I don't know to what degree OCaml's various escape hatches would have hindered multicore. All the text I've seen is about avoiding regression.
brmgb 6y ago
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 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."