OCaml and Multithreading

As Doctor House said one day: "There was that philosopher Ocaml..." Stop, wrong start! Try again.

1. OCaml story

OK, some time ago, in a somehow better world, I became attracted to the OCaml language because of its speed, elegance, light syntax, algebraic data structures and automatic type inference (as you meanwhile might know, I'm a bit of a typing fan). I must admit, it was my first functional language, so maybe I'm a little sentimental about it. Later on I somehow didn't give it much love and affection, mostly because I got distracted by other, more fashionable languages like Clojure, F# and Haskell (shame on me!).

Nonetheless, although this one is rather an obscure language, one company has been using it big time to do some highly parallel, high-performance data processing. This company is Jane Street and they are a financial market player. The reason they chose OCaml were that the owners wanted to read every line of code performing financial transactions*:

"Early on, a couple of the most senior traders (including one of the founders) committed to reading every line of code that went into the core trading systems, before those systems went into production"

"In 2003, Jane Street began a rewrite of its core trading systems in Java. The rewrite was eventually abandoned, in part because the resulting code was too difficult to read and reason about—far more difficult, indeed, than the VBA that was being replaced."

 "The VBA code was written in a terse, straight-ahead style that was fairly easy to follow. But somehow when coding in Java we built up a nest of classes that left people scratching their heads when they wanted to understand..."

 "In 2005, emboldened by the success of the research group, Jane Street initiated another rewrite of its core trading systems, this time in OCaml."

So somehow the functional-style code was more readable than a pile of Java classes: can we put that to the superiority of functional languages in general or just to bad training of Java programmers? An open question.

OK, there are additional technical reasons as well: the type inference that makes the code concise (thus more readable) while retaining type safety. Additionally it's runtime performance is pretty good! A double win against for example Python.

2. Multithreading?

For a long time they remained the single serious industry user of which I knew, but recently also Facebook started using OCaml in their Hack and Flow language typing add-ons for PHP and Javascript implementations. Surprise! And a very nice one, my pet language got appreciated at last! Everything OK?

Not quite: when I listened to that presentation, I was surprised to learn that OCaml's mutlithreading support is pretty much completely broken. How can that be? Why didn't I notice that first place?

Well, after some more digging, I received this link from a fellow programmer. It makes it pretty clear to us all that OCaml designers were quite a nasty bunch of "multicore deniers":

"The goals of OCaml threads are (2) and (3) but not (1)"

Where (1) denotes "Parallelism on shared-memory multiprocessors"! And then:

"Shared-memory multiprocessors have never really "taken off", at least in the general public.  For large parallel computations, clusters (distributed-memory systems) are the norm. For desktop use, monoprocessors are plenty fast."

 "What about hyperthreading?  Well, I believe it's the last convulsive movement of SMP's corpse :-)"

Yes, they didn't like it, to say the least. But there's another reason as well: the GC implementation in OCaml is single-threaded and thus it could be made very fast, which was an important factor in OCaml's initial successes. But then this (ironically) proved detrimental to trying to make the language MT-safe**.

The only way to do parallel processing in OCaml is thus multiprocessing + message passing. As I learned Jane Street wrote the Parallel library to support that:

"Parallel is a library for spawning processes on a cluster of machines, and passing typed messages between them. The aim is to make using another processes as easy as possible. Parallel was built to take advantage of multicore computers in OCaml, which can't use threads for parallelism due to it's non reentrant runtime

The Facebook people went one step further: they

"...use the same model for multithreading: a specially mmap'd region shared between different fork'd processes, containing a shared, lockless hash table. "

Thus they have multithreading without threads - a couple of processes sharing the memory space (or a part of it), faking the SMP model! You must admit it's rather brilliant - you spare yourself all that serialization, deserialization, and message passing that normally shave off a significant part of the performance.

3. So why OCaml?

Apparently, despite the mutithreading disaster, companies find OCaml worth trying out. Why? I'd say the reasons are:

  1. It supports functional style (but it allows dirty tricks when they must be done)

  2. Has strong typing unlike Lisp, Python, etc.

  3. Not bound to Windows and .NET like F#
  4. Not Haskell, you'll be able to read and understand it.***

And finally, maybe this whole multithreading business isn't worth the hassle? Facebook clearly need it, but Jane Street don't. I remember having heard Yaron Minsky (of Jane Street) saying somewhere that parallel processing plus message passing is a much safer model that multithreading. And in finance you need that safety.

I can accept this argument in a more general setting as well, because the only reason we have threads are performance gains (OK, a deceptively "natural" programming model too). And if the performance of forking + message passing is sufficient, that's definitely a gain! Jane Street does some massive parallel processing in real time, so the performance seems to be not that bad after all...

Or maybe the fork+pass model is slower, but they are gaining on the excellent low-latency CG? Jon Harrop puts it like that:

"OCaml has a nice (~10ms) low latency GC and it is easy to optimise OCaml code for low latency. In contrast, the .NET GC is much more complicated and, therefore, harder to optimise for and, in my experience, has >10x higher latency. I suspect that would be a major drawback for Jane Street."

So before you port OCaml's GC to multicore, overcomplicating it and losing its excellent performance, maybe paying some price for the workarounds pays out better?

Having said that, there's recent work on improving the GC-performance even more, and even a new attempt on multicore OCaml. Maybe this time they will be successful. And be wary, not everyone likes OCaml, for some "OCAML sucks" - http://www.podval.org/~sds/ocaml-sucks.html!

Update: an impressive list of companies using OCaml: https://ocaml.org/learn/companies.html (via @jonharrop). So it's not only Jane Street and Facebook!
Update2: Facebook continues working on OCaml ecosystem - Reason, a "new interface to OCaml" ... "provides a new syntax and toolchain for editing, building, and sharing code". Plus Infer - the iOS/Android app checking tool!

--
* "OCaml for the masses" - http://queue.acm.org/detail.cfm?id=2038036

** "The rise and fall of OCaml" - http://flyingfrogblog.blogspot.co.uk/2010/08/rise-and-fall-of-ocaml.html

 ***  As someone said, Haskell was created to do research on Haskell (and OCaml was created to write theorem provers).

Monads, who's afraid of Monads (and C++)?

Nowadays every programmer has heard of Monads, and either has a PhD in CS or is afraid of them (or both...). When I first heard of it (my university years are quite distant, and the category theory wasn't en vogue yet in that distant time) I though: "Monadology? Leibniz? WTF? Didn't Kant disprove that?"

Because writing a monad tutorial is sooo last decade, I will just reference one quite good, practical introduction to that stuff that is using Javascript (Javascript! => nice, no need to learn a new, unreadable & incomprehensible language first! 😀). I think it's <praise> practical enough to be useful, but then again not shirking back from maths in order to please the reader</praise>.

If you don't want to read it, and are smug enough to think that a 10.000 feet view is all you'll ever need, voila - there's a short summary:

Monads Summary

1. Functor

An object encapsulating a value, plus an interface (called "fmap" for historical reasons) taking some function to act on that value. Because of the immutability/pure functions stuff it doesn't change the contained value, of course, but produces a new functor instance.

            +------------+                                  +------------+
            |   value    |                                  |  newvalue  |
      f     |            |     fmap()                       |            |
  +-------> |   fmap()   |  +--------->  f(value) +-------> |   fmap()   |
            |            |                                  |            |
            +------------+                                  +------------+

Is the picture clear enough? OK, let's continue.

2. Monad

Is a Functor which has a "collapse" and "wrap" methods. Collapse (also called "join" in some contexts) will remove one level of the packaging added by the functor, "wrap" (also called "return") will remove it. Simple like that!

  +-------------------------------+                               
  |                               |                               
  |            +-------------+    |                 +------------+
  |            |             |    |       join      |            |
  |   value =  |    value    |    |   +---------->  |   value    |
  |            |             |    |                 |            |
  |            +-------------+    |                 +------------+
  |                               |                               
  +-------------------------------+                               

                         +------------+
               wrap      |            |
   value   +---------->  |   value    |
                         |            |
                         +------------+

Well not quite, the classic usage case** that made the whole concept famous, hinges on another method called "mbind" which allows us to apply several functions to the monadic value in a row, an emulation of imperative programming (imperative always means in this context "evil, evil") standard sequential flow of control. But wait a minute: isn't that simply "fmap" + "join"? Yeah, you guessed it, it is***.

Simple? Yes, I think so. Was it that complicated? No. So why all that fuss? Don't know, won't comment here, make your own mind.

But why should this be useful? Again, I don't want to write a monad tutorial here (it's so ...), read the Javascript  book, or maybe some general functional programming resources. Start with error handling and the Maybe type.

High level enough? If not, take on with this classic explanation: "Monad is just a monoid in category of endofunctors, what's the problem?"*. Here you'll need some category theory/maths, there's no mercy:

Another Summary

1. Endofunctor

A functor (see above) mapping values to values of the same type. On that level, functor is a mapping between categories, where a category is a set of values plus all the functions between the values. Thus our functor above maps values of type A to values of type B and functions A->A to functions B->B, respecting some common sense restrictions on its way.

You see, it's getting pretty messy quite quickly, but take it as a mathematical recreation and follow through.

2. Category of endofunctors

All endofunctors plus functions mapping one endofuctor (i.e. a functor, i.e a mapping from one "set" of object+mappings to another) to another.

3. Monoid in that category...

Monoid is a "set" of objects having a function A->A defined for them (usually called "m-append", you get it, basically a glorified string or array) plus a neutral element. Now just imagine that for the category of endofunctors, do some math, an you will see that all that gunk collapses to our old, trusty monad as described above.

Why so complicated? Well, that's maths (and mathematicians) for you. But don't despair, it's only a construction of a human mind, so everyone can get a grip of it. The question is only if that does feel like fun for you or not. In all cases, don't mythologize!

And That's It!

Now if you feel like that, you can try out this things in C++, there are a couple libraries implementing this stuff like this, this or that. Simple, self-sufficient implementation is possible too! There was even a C++ language proposal for a monadic expected class to be used for error handling, so somehow this stuff is coming. Now as you are not intimidated anymore, go and try it!

But first read the Javascript online book to familiarize yourself with the concepts. And yes, you don't need to learn Haskell**** and then read Haskell books for that! So do not fear.

Maybe you'd even like to go further and investigate monadic parsers (because I like F# you'll get this link and this link), applicatives & applicative parsers (sorry no link here, didn't find anything which is simple enough) or free monads. Who knows, the sky is the limit now, an you do not fear anything! At least you can read the jargon without cold shivers running down your spine.

PS: Maths guys, please no hair-splitting, I didn't cross-checked it with MacLane & Avodey, just wrote it down as I remembered it. However notice the "set" usage ;) ...


Update: If you want to continue in a similar vein, that's an interesting page demythologizing func. prog. on its own: github.hemanth.functional-programming-jargon!

--
* famously attributed to Phillip Wadler, but it's rather a joke, as the real sentence was:

"All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor."

** by..., you guessed it, Phil Wadler: "Monads for functional programming" (it's CS + FP but nonetheless quite readable, you may risk a try now when you fear nothing!)

*** in some contexts "point" and "flatMap" are used, the first for "wrap", the second for "fmap" + "collapse"

**** "I'm Haskell, the language of purebloods..." 😉