7 ms·

Languages like Haskell and Go already have multicore GCs. How does OCaml's multicore GC compare? Is the work taking a long time because it is doing something br

by msvan 7y ago

Languages like Haskell and Go already have multicore GCs. How does OCaml's multicore GC compare? Is the work taking a long time because it is doing something brand new in the design space, or is it simply hard to integrate it with a mature language that was designed to be single core?

throwaway894345 7y ago
It's hard to make a concurrent GC that also allows for the kind of super-cheap allocation that OCaml depends on for its performance characteristics. Allocation is expensive in Go, for example, but this is okay because Go has value semantics and an imperative model (no need to allocate memory on every little operation). Not sure how Haskell's GC works, but I'm guessing it more or less depends on Haskell's immutability guarantees. EDIT: Downvoters, I'm genuinely interested in hearing from you. Did I accidentally cause offense or am I mistaken?
- gpderetta 7y ago
  Java does have cheap allocations and a (many?) scalable multithread friendly GCs though. I guess they did require many many man hours to implement and count as hard?
  - throwaway894345 7y ago
    Java's GC is an impressive piece of engineering with a whole lot of investment, and even then (at least until very recently) it came at the cost of high stop-the-world pause times.
    - pjmlp 7y ago
      It wasn't recently if you were willing to shell out the bucks. Aonix, PTC, Aicas, IBM have been selling real time JVMs for embedded OSes and bare metal deployments for quite several years, before Azul came into the picture with their pause-less GC for multi-GB heaps (which still does minimal pauses anyway). So recently is more the addition of Azul's ideas into Shenandoah, ZGC in OpenJDK, and Metronome in OpenJ9 as free beer GC for the Java community.
    - The_rationalist 7y ago
      ZGC say hello :)
- kccqzy 7y ago
  I didn't downvote you, but you are mistaken. I don't know about Go GC but your comment about Haskell is very off. > Not sure how Haskell's GC works, but I'm guessing it more or less depends on Haskell's immutability guarantees. This is false. Just because you see immutability on the surface doesn't mean the GC still sees a lot of immutability. Several reasons. The first is that even pure code can depend on interior mutability in a safe way using the ST monad, or in an unsafe way using the IO monad. (The GC can't just say, I give up when a user uses an unsafe function.) You might think that interior mutability is rarely used, but that'd still be wrong. Even something as commonplace as a hash map (from unordered-containers) uses interior mutability under the hood. Just read the source code and you'll see it. Here: http://hackage.haskell.org/package/unordered-containers-0.2.10.0/docs/src/Data.HashMap.Base.html http://hackage.haskell.org/package/unordered-containers-0.2.... Just grep for runST. The bigger problem is laziness. How is laziness implemented? A value is represented as an unevaluated thunk, a closure to compute the value. When the value is needed, the closure is run and then replaced by the resulting data. This is mutability. And this is something that almost every Haskell program relies on. I've explained this many times on HN. See eg https://news.ycombinator.com/item?id=21674749 https://news.ycombinator.com/item?id=21674749
  - __s 7y ago
    It isn't entirely false. Haskell's GC can take some shortcuts when dealing with immutable objects as they can't reference objects older than themselves, including referencing themselves
    - hope-striker 7y ago
      Really? I have no experience with Haskell's internals, but self-referential objects are fairly common in Haskell thanks to its non-strictness. The simplest one is probably the list with one element repeated forever. ones = 1:ones
    - kccqzy 7y ago
      If objects can't reference themselves, do you think recursion is impossible in Haskell? powersOf2 = 0 : scanl (+) 1 (tail powersOf2) fibonacci = 0 : scanl (+) 1 fibonacci As I have already explained, immutable objects in Haskell often use laziness. And laziness requires mutability.
- dnautics 7y ago
  Erlang's gc is excellent and very much concurrent, but depends on architectural assumptions you don't get on other languages.
  - jeremyjh 7y ago
    Erlang doesn't really have concurrent gc, instead it uses shared nothing heaps and copies values everytime a process sends a message to another process.
    - dnautics 7y ago
      and all of those copies have to be garbage collected, concurrently to the operations being run. Memory isn't infinite on long-lived servers.
      - jeremyjh 7y ago
        No, there is no concurrent garbage collection happening. When a process is running user code, it is not being garbage collected and vice versa. It happens at an individual process level, but the process is definitely paused while its heap is collected. It has similar benefits to concurrent garbage collection such as the fact that there is never a stop-the-world-pause, and short pauses (since the heaps are typically very small), but it is not the same and means different trade-offs and tuning may be required at the extremes.
        dnautics 7y ago
        > When a process is running user code, it is not being garbage collected and vice versa That doesn't make it 'not a garbage collector' and it also doesn't make it 'not concurrent'. > tuning may be required at the extremes that is very rare, and if that is disqualifying for a concurrent GC, then Java is disqualified as a concurrent GC.
        jeremyjh 7y ago
        It is not "qualified" because the process using a heap is paused while the heap is collected. In a concurrent GC, nothing is paused.
UncleOxidant 7y ago
Some of both I'd guess. Go was probably written from the start with multicore in mind. Not sure when Haskell went multicore. Taking an existing language implementation like OCaml's from single to multicore is a lot of work. Much of this work is in the GC. As I understand it, they're also not wanting to impact single core performance (I believe that's an INRIA requirement in order for them to accept the changes).
- nerpderp82 7y ago
  > not wanting to impact single core performance That seems like an over burdensome requirement given that we are swimming in cores. A 10% loss in single core performance vs 1.2x-Nx multicore performance increase would be an adequate tradeoff. The only other option I can think of is having two different backends, one that is entirely single threaded and doesn't incur any multicore performance penalty.
  - dna_polymerase 7y ago
    But I'd have to adapt my old code to more cores, and it isn't always easy to just split and distribute a workload onto more cores.
  - YawningAngel 7y ago
    By definition OCaml's entire userbase consists of programs that run on a single core, so a 10% regression in single core performance is going to be a pretty hard sell.
    - nerpderp82 7y ago
      I would argue that single core only OCaml could be released in parallel (heh) with a multicore OCaml. Legacy users could opt for the single core runtime distribution. As soon as you get parallel gc, MPMC queues, parallel sorting, set intersection, etc. Many programs will see about a 1.x speed up making the point moot. Erlang went through this same transition.
      - 7y ago
sadiq 7y ago
Disclaimer: I don't speak for OCaml or OCaml Labs but I am a contributor to multicore. It is indeed that it is hard to retrofit parallelism on to an existing language while trying to retain backwards compatibility _and_ performance. Backwards compatibility is tricky because there's lots of C code using the C API. Performance is hard because OCaml users are used to well performing code, with low and predictable pause times from the GC (<10ms). The community is small and it seems like there wasn't appetite for maintaining two distinct runtimes with very different performance characteristics. The current implementation for multicore GC (https://github.com/ocaml-multicore/ocaml-multicore https://github.com/ocaml-multicore/ocaml-multicore) is reasonably close to upstream in performance on single threaded code and yet will scale up to multiple threads. It requires a change to the C API though. There's a modified multicore GC (https://github.com/ctk21/ocaml-multicore/tree/stw_minor_gc https://github.com/ctk21/ocaml-multicore/tree/stw_minor_gc) that doesn't require the C API change and we're currently writing up a paper that contrasts the two wit a fairly substantial amount of benchmarking (https://github.com/ocamllabs/sandmark https://github.com/ocamllabs/sandmark). Happy to answer any questions.
- throwaway894345 7y ago
  > Performance is hard because OCaml users are used to well performing code, with low and predictable pause times from the GC (<10ms). I would expect that low pause times are easy enough (or relatively easy considering the difficult domain of GC optimization), but keeping the allocations cheap is (one of) the key constraints, no?
  - sadiq 7y ago
    Yes, it's very easy to make pause times low if you're willing to make allocation expensive - it's all trade-offs. In multicore's case it's about keeping low pause times while also keeping allocation cheap _and_ maintaining throughput.
    - chrisseaton 7y ago
      Why would allocation become more expensive in parallel? Surely you’re allocating in thread-local space? It’s like two machine instructions. Where does the extra overhead come from?

by msvan 7y ago

throwaway894345 7y ago

It's hard to make a concurrent GC that also allows for the kind of super-cheap allocation that OCaml depends on for its performance characteristics. Allocation is expensive in Go, for example, but this is okay because Go has value semantics and an imperative model (no need to allocate memory on every little operation). Not sure how Haskell's GC works, but I'm guessing it more or less depends on Haskell's immutability guarantees. EDIT: Downvoters, I'm genuinely interested in hearing from you. Did I accidentally cause offense or am I mistaken?

gpderetta 7y ago
Java does have cheap allocations and a (many?) scalable multithread friendly GCs though. I guess they did require many many man hours to implement and count as hard?
- throwaway894345 7y ago
  Java's GC is an impressive piece of engineering with a whole lot of investment, and even then (at least until very recently) it came at the cost of high stop-the-world pause times.
  - pjmlp 7y ago
    It wasn't recently if you were willing to shell out the bucks. Aonix, PTC, Aicas, IBM have been selling real time JVMs for embedded OSes and bare metal deployments for quite several years, before Azul came into the picture with their pause-less GC for multi-GB heaps (which still does minimal pauses anyway). So recently is more the addition of Azul's ideas into Shenandoah, ZGC in OpenJDK, and Metronome in OpenJ9 as free beer GC for the Java community.
  - The_rationalist 7y ago
    ZGC say hello :)
kccqzy 7y ago
I didn't downvote you, but you are mistaken. I don't know about Go GC but your comment about Haskell is very off. > Not sure how Haskell's GC works, but I'm guessing it more or less depends on Haskell's immutability guarantees. This is false. Just because you see immutability on the surface doesn't mean the GC still sees a lot of immutability. Several reasons. The first is that even pure code can depend on interior mutability in a safe way using the ST monad, or in an unsafe way using the IO monad. (The GC can't just say, I give up when a user uses an unsafe function.) You might think that interior mutability is rarely used, but that'd still be wrong. Even something as commonplace as a hash map (from unordered-containers) uses interior mutability under the hood. Just read the source code and you'll see it. Here: http://hackage.haskell.org/package/unordered-containers-0.2.10.0/docs/src/Data.HashMap.Base.html http://hackage.haskell.org/package/unordered-containers-0.2.... Just grep for runST. The bigger problem is laziness. How is laziness implemented? A value is represented as an unevaluated thunk, a closure to compute the value. When the value is needed, the closure is run and then replaced by the resulting data. This is mutability. And this is something that almost every Haskell program relies on. I've explained this many times on HN. See eg https://news.ycombinator.com/item?id=21674749 https://news.ycombinator.com/item?id=21674749
- __s 7y ago
  It isn't entirely false. Haskell's GC can take some shortcuts when dealing with immutable objects as they can't reference objects older than themselves, including referencing themselves
  - hope-striker 7y ago
    Really? I have no experience with Haskell's internals, but self-referential objects are fairly common in Haskell thanks to its non-strictness. The simplest one is probably the list with one element repeated forever. ones = 1:ones
  - kccqzy 7y ago
    If objects can't reference themselves, do you think recursion is impossible in Haskell? powersOf2 = 0 : scanl (+) 1 (tail powersOf2) fibonacci = 0 : scanl (+) 1 fibonacci As I have already explained, immutable objects in Haskell often use laziness. And laziness requires mutability.
dnautics 7y ago
Erlang's gc is excellent and very much concurrent, but depends on architectural assumptions you don't get on other languages.
- jeremyjh 7y ago
  Erlang doesn't really have concurrent gc, instead it uses shared nothing heaps and copies values everytime a process sends a message to another process.
  - dnautics 7y ago
    and all of those copies have to be garbage collected, concurrently to the operations being run. Memory isn't infinite on long-lived servers.
    - jeremyjh 7y ago
      No, there is no concurrent garbage collection happening. When a process is running user code, it is not being garbage collected and vice versa. It happens at an individual process level, but the process is definitely paused while its heap is collected. It has similar benefits to concurrent garbage collection such as the fact that there is never a stop-the-world-pause, and short pauses (since the heaps are typically very small), but it is not the same and means different trade-offs and tuning may be required at the extremes.
      - dnautics 7y ago
        > When a process is running user code, it is not being garbage collected and vice versa That doesn't make it 'not a garbage collector' and it also doesn't make it 'not concurrent'. > tuning may be required at the extremes that is very rare, and if that is disqualifying for a concurrent GC, then Java is disqualified as a concurrent GC.
        jeremyjh 7y ago
        It is not "qualified" because the process using a heap is paused while the heap is collected. In a concurrent GC, nothing is paused.

UncleOxidant 7y ago

Some of both I'd guess. Go was probably written from the start with multicore in mind. Not sure when Haskell went multicore. Taking an existing language implementation like OCaml's from single to multicore is a lot of work. Much of this work is in the GC. As I understand it, they're also not wanting to impact single core performance (I believe that's an INRIA requirement in order for them to accept the changes).

nerpderp82 7y ago
> not wanting to impact single core performance That seems like an over burdensome requirement given that we are swimming in cores. A 10% loss in single core performance vs 1.2x-Nx multicore performance increase would be an adequate tradeoff. The only other option I can think of is having two different backends, one that is entirely single threaded and doesn't incur any multicore performance penalty.
- dna_polymerase 7y ago
  But I'd have to adapt my old code to more cores, and it isn't always easy to just split and distribute a workload onto more cores.
- YawningAngel 7y ago
  By definition OCaml's entire userbase consists of programs that run on a single core, so a 10% regression in single core performance is going to be a pretty hard sell.
  - nerpderp82 7y ago
    I would argue that single core only OCaml could be released in parallel (heh) with a multicore OCaml. Legacy users could opt for the single core runtime distribution. As soon as you get parallel gc, MPMC queues, parallel sorting, set intersection, etc. Many programs will see about a 1.x speed up making the point moot. Erlang went through this same transition.
    - 7y ago

sadiq 7y ago

Disclaimer: I don't speak for OCaml or OCaml Labs but I am a contributor to multicore. It is indeed that it is hard to retrofit parallelism on to an existing language while trying to retain backwards compatibility _and_ performance. Backwards compatibility is tricky because there's lots of C code using the C API. Performance is hard because OCaml users are used to well performing code, with low and predictable pause times from the GC (<10ms). The community is small and it seems like there wasn't appetite for maintaining two distinct runtimes with very different performance characteristics. The current implementation for multicore GC (https://github.com/ocaml-multicore/ocaml-multicore https://github.com/ocaml-multicore/ocaml-multicore) is reasonably close to upstream in performance on single threaded code and yet will scale up to multiple threads. It requires a change to the C API though. There's a modified multicore GC (https://github.com/ctk21/ocaml-multicore/tree/stw_minor_gc https://github.com/ctk21/ocaml-multicore/tree/stw_minor_gc) that doesn't require the C API change and we're currently writing up a paper that contrasts the two wit a fairly substantial amount of benchmarking (https://github.com/ocamllabs/sandmark https://github.com/ocamllabs/sandmark). Happy to answer any questions.

throwaway894345 7y ago
> Performance is hard because OCaml users are used to well performing code, with low and predictable pause times from the GC (<10ms). I would expect that low pause times are easy enough (or relatively easy considering the difficult domain of GC optimization), but keeping the allocations cheap is (one of) the key constraints, no?
- sadiq 7y ago
  Yes, it's very easy to make pause times low if you're willing to make allocation expensive - it's all trade-offs. In multicore's case it's about keeping low pause times while also keeping allocation cheap _and_ maintaining throughput.
  - chrisseaton 7y ago
    Why would allocation become more expensive in parallel? Surely you’re allocating in thread-local space? It’s like two machine instructions. Where does the extra overhead come from?