Hacker News Reader

Comment by msvan | Hacker News Reader

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?

View on HN

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) 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) 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).

Happy to answer any questions.

> 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?

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.

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?

If you want conventional shared memory parallelism, then your allocations can't assume thread-locality.

> If you want conventional shared memory parallelism, then your allocations can't assume thread-locality.

I don't really understand why not. Can you expand on it? Doesn't the JVM for example do thread-local allocations in a conventional shared-memory parallel environment?

I was mistaken; wasn't thinking clearly as I responded. JVM can get away with this because it's generational/moving; bump allocator works in the young generation and then objects are subsequently moved. Generational/moving is tricky, especially with C APIs (if the GC moves an object that C has a pointer to, the C code dereferencing the pointer will find potentially garbage data) and I believe they make it difficult to get good STW times, but at this point I'm pretty well out of my depth.

Both current multicore GCs do exactly that to keep allocation cheap but there are different design choices within the constraints we could have gone with.

To avoid frequent synchronisation we could have gone with a (potentially generational) non-moving collector for the minor GC which would still have preserved the C API, probably allowed for very low pauses but would have made allocation more expensive.

In what form will Multicore OCaml support the, you know, multicore stuff? Will it be native OS threads? CSP? Actors? Something else?

I am very excited to use OCaml with multicore abilities but lately I realised that I have no clue how will the initial support even look like in terms of a programming API.

Why don't you use reference counting GC?

Because atomic reference counting (needed for multi-threaded runtime) is well known to have terrible performance.

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?

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?

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.

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.

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.... 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

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

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

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.

I'm an idiot. I meant that objects can't reference objects newer than themselves

Ah, thanks for correcting me. Like I said, I am unfamiliar.

> 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.

Tangent: does GHC ever decide that it's cheaper to just potentially evaluate something twice than to use thunks?

Erlang's gc is excellent and very much concurrent, but depends on architectural assumptions you don't get on other languages.

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.

and all of those copies have to be garbage collected, concurrently to the operations being run. Memory isn't infinite on long-lived servers.

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.

> 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.

It is not "qualified" because the process using a heap is paused while the heap is collected. In a concurrent GC, nothing is paused.

that's a silly distinction, because if you are running multiple threads on a single CPU, or even multiple threads on multiple CPUs, in most situations, then you're simply pushing the 'pausing' down to the hardware/os which is doing the preemption.

Thread preemption has nothing to do with garbage collection pauses. An Erlang process that allocates a lot will spend more time being paused, irrespective of its priority which might otherwise let it run uninterrupted. I'm not going to continue this "argument" further.

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).

> 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.

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.

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.

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.

Maintaining two parallel distributions is a lot of work for a relatively niche language with a small community.

One build has locks, the other does not.

If OCaml wants to remain somewhat viable it will need to be able to use more than one core. The most users of OCaml is always right now. This won't always be the case if they cannot go multicore.

Can you expand on the Erlang history? Really interesting.

Presumably if performance were a key concern you wouldn't have used OCaml to begin with.

Curious claim, considering OCaml fares pretty well in many language comparison benchmarks.

Language comparison benchmarks are a tiny part of actual performance in the real world.

They do translate into real-life performance though and unlike many other languages, for the most part without "writing C in language X".

Extraordinary claims require extraordinary evidence.

Claiming a functional language is as performant as a systems language is a very big claim.

What's a "systems language"? Someone recently posted "awk as a major systems programming language".

Ocaml is used in many performance and latency sensitive domains as a minimal amount of research would show you. Here's an example:

https://www.janestreet.com/tech-talks/building-an-exchange/

It's also got a reputation for pretty predictable performance characteristics, fast compilation and ease of writing correct and concise code, properties C++, for example, does not necessarily share. Part of this is because the compiler is comparatively straightforward in what it does (and same for standard library), with the flip side that you leave some performance on the table. But that might not be a bad trade-off given that ocaml generally seems to be within a factor of ~3x of C++ (which can probably easily baloon up for specific problems, given that ocaml has e.g. poor SIMD and machine size int support). So you probably wouldn't want to write AAA game engines, crypto libs or numerical kernels in it. But my guess is that a language with those characteristics (and much faster iteration times) translates to better real world performance for many other types of tasks.

The same way you ask me to do a "minimal amount of research", you should do the same to answer the question about what is a systems programming language.

Claiming "within ~3x of C++" answers your question. For the problems I work in (some of which you mention) even a 5% is a major deal. 300%? That’s just crazy talk and a non-starter.

That’s what performance means and why most language benchmarks are usually useless: people writing them have no clue of what are the requirements of many fields.

I tend to do my homework – system programming language is not some narrowly defined concept with an universally agreed on definition. People frequently put Go and Swift in that category (see the wikipedia). Are you suggesting Swift is systems programming when Ocaml isn't? If you run docker on Windows or macOS you are running a tcp/ip stack in ocaml (unless something has recently changed).

I assume you mean 105% and 300%? And what are the 105% that are a major deal – the runtime relative to what the hardware could theoretically do? Or 105% relative to what you can get out of C++?

Parts of the Xen Hypervisor, Docker TPC/IP stack integration with the host OS, and the MirageOS are written in OCaml, it looks pretty much systems programming to me.

Likewise, there is an endless amount of compilers in research written in OCaml.

Last time I checked, anything related to compiler toolchains used to be considered systems programming.

Ocaml can be extremely performant - both in terms of throughput and latency - in the single-threaded case. There's a particular set of problems where Ocaml's performance is bottlenecked without multicore, but that's far from most.

Anecdotally, I once worked at an Ocaml trading firm - where microseconds could matter! - and at least at the time, folks there weren't particularly interested in multicore. We have async/lwt already, and we spun up multiple processes for parallelism. A 10% performance drop for multicore support that we didn't need would have been unacceptable for us.

Don't many trading firms explicitly disable cores on their trade execution machines? I know Optiver does.

Sure.

OCaml has an unusual share of latency-sensitive stakeholders, probably only comparable with Go of all garbage-collected languages. As far as I heard, optimizing Go's GC for latency has been an awful lot of work.

Any reasonably widely used language will have users who care about latency. People write user interfaces in Java so clearly it’s users care about latency. Similarly for JavaScript except I would expect a react user interface to produce a lot more allocation pressure than a java one (and so gc latency and throughput both matter). Even emacs lisp cares about latency (the main user visible improvement was not printing “garbage collected” each time the gc ran).

For things like servers, latency can matter to some extent because of the resource usage of in-flight requests. It is desirable to serve requests quickly to free up resources on the server and any clients too.

Similarly one will find plenty of apps which care about throughput too.

> Any reasonably widely used language will have users who care about latency.

Right, but, to the parent's point, OCaml, with its HFT pedigree, has an unusual level of latency sensitivity in its userbase.

I can't speak for Jane Street, but, at the prop shop where I did my time, nobody found it all that peculiar to have major cross-company initiatives to, e.g., shave a couple bytes off a datagram format just to reduce some message's average latency by a fraction of a millisecond.

> People write user interfaces in Java so clearly it’s users care about latency.

GUIs in Java are notoriously bad, and tend to only be used for internal tools (where good UX is not a priority), complex professional tools where functionality was a higher priority than UX, or open-source programs where the same thing is true. Another example is that Java is still an unpopular language for command-line tools that can be used from the shell, whereas OCaml is pretty popular in that use space.

Any reasonably popular language will have someone using it for any given thing, sure - I'm sure there are people out there writing webapp backends in C or numerical batch processes in Ruby - but the core constituency can differ a lot between different languages, and that can (and should!) affect that language's priorities.

Programmer art ,doing everything on the UI thread, and not caring to read books like "Filthy Rich Client" usually are big contributors to that bad experience.

And there is hardly any difference between using something like Swing Material UI widgets or the typical Android app, other than programmer skills.

You don't just wave a magic wand and get your code parallelized, though. Some algorithms are quite hard to parallelize (and it seems OCaml's user base is full of these, like theorem provers and compilers). Remember Amdahl's law.

The original presentation on Concurrent Haskell is dated 1996 (http://www.haskell.org/ghc/docs/papers/concurrent-haskell.ps...)

Reply on news.ycombinator.com