Cap'n Proto v0.2: Compiler rewritten from Haskell to C++11 | Hacker News Reader

Cap'n Proto v0.2: Compiler rewritten from Haskell to C++11

kentonv.github.io

84 pointskentonv46 comments

So basically he's concluding, having written some Haskell that he's not confident enough to maintain/improve a large project in the language?

Seems fair enough to me really?

Yes, that is basically it.

I really wanted to like Haskell...But the compiler is now C++.

Been down that road a few times myself.

C++ is a language only a mother could love, and only if that mother is a systems programmer who wants more abstraction than you can get with C. But for some reason that I don't think anyone has ever been able to explain, you can do some things in C++ that would be prohibitively difficult in any other language.

Interestingly, the Xen folks are now using OCaml for a bunch of system stuff. That could be worth checking out.

OCaml is much more forgiving in letting you "cheat" and also being strictly evaluated makes OCaml easier to reason about performance for programmers used to strictly evaluated languages.

The Xen folks have been using OCaml for years. I interviewed with them back in 2006 (ish) because I had some Ocaml experience & a bunch of their top developers had just quit to go form a database company (not that I knew that at the time).

Looking at the code for the 0.1.0 release, it looks like you were using parsec as opposed to attoparsec (which typically has better performance). About virtual tables, I'm not exactly sure of what you were trying to do, but the usual solution to having different kind of stuff you want to put in a single collection is to just use a sum type - though it assumes you know in advance what kind of things you want in your collection, or at worst, use existential types. But the FFI question is a good point.

Performance wasn't actually a goal, since it was just a code generator tool and was still much faster than the C++ compiler that runs on its output. I was also using Integer rather than Int everywhere (I didn't realize when I started that Integer = BigInt).

Yeah, most (perhaps all) design challenges where I want vtables can be solved elegantly in some other way in Haskell, but the solution depends on the use case and isn't a simple bijection. It's just tough to rewire the way the designs form in my head before I write the code. If I had infinite time...

Heh. I'll be the last person to claim that Haskell is a low-maintenance language :)

> But with the schema parser written in C++, things become much simpler. [see article for more context]

I think this is debatable part.

First, calling Haskell from Python is quite easy. I've wanted that once and things went surprisingly well, see yourself: https://github.com/drdaeman/haskell-library-ffi-example

Second, not everyone has C++ compiler installed and readily available (although, it's true that it's far more likely that there's already a C++ compiler than Haskell one). But in the end, I don't think it really matters whenever one does `$package-install-command g++` or `$package-install-command ghc`, as, I believe, neither comes on out of box installs on most popular non source-based GNU distros, and certainly not on Windows. I don't know how things are in *BSD land.

Do you really want two garbage collectors running in one process? Isn't one already one too many? :)

Seriously, though, yeah, it's definitely debatable. If I had been loving writing my code in Haskell, the challenges of FFI probably wouldn't have been enough to sway me.

Hm. If not, you have the problem of making sure that the calling runtime handles memory correctly for the non-GCed space, so it is definitely debatable.

E.g. RMagick was famous for suffering from problems of that kind.

This seems like a reasonable conclusion. Trying to learn the ins and outs of a new language/library/framework while trying to get something done is not a great way to do either. My primary languages are Haskell and C++, and I write a lot of language tools. It seems to me that both languages are good choices in this department, but for very different reasons. Haskell is difficult to beat in terms of sheer data-munging expressiveness, and I spend 20% of my time in C++ doing what “deriving” does for me in Haskell, but if you know C++ well, you can use it to write very efficient code that’s still fairly expressive. That ain’t nothing. Maybe next time choose OCaml though. ;)

From the article: "For instance, to actually encode a Cap’n Proto message, I couldn’t just allocate a buffer of zeros and then go through each field and set its value. Instead, I had to compute all the field values first, sort them by position, then concatenate the results."

Sounds reasonable to me, but I think it's just personal preference. Without actually seeing the code (which I'm sure makes a huge difference), the imperative algorithm actually doesn't read as easily as the functional one does to me. We've become accustomed to imperative since it's what we all learned on, but there is a massive amount of book-keeping (although I'm sure the execution speed is much faster). At any rate, here is Scala with imaginary API's detailing how I would envision the functional algorithm...

    def encodeFields(fields: List[Field]): String =
      fields.map { f => f.position -> f.computeValue }.sortBy { _._1 }.map { _._2 }.mkString

In terms of code complexity, I honestly can't decide whether the difference is objective or subjective. The functional version sure feels complex to me, but yeah, it may just be because that's not what I'm used to.

That said, given my knowledge of how the hardware actually works, the purely-functional approach makes my efficiency sense tingle. A lot.

Of course, whether or not it's a good idea to scratch it is something we've been debating for decades...

This is kind of a strawman, but if you were to use a similar pseudo-API, what would the imperative code look like?

Very fair point about efficiency; for all my love of the FP style, I'll never claim it to be faster or leaner w.r.t memory usage. I'd be curious to see if the simple parallelization made possible by the functional approach could close that performance gap, though.

...and I'm almost positive the difference is subjective. =) Reading over your website, it's clear that you are a very talented engineer, especially in areas where C++ shines. Given this plus your experience at Google developing Protobuf, I'd hazard a guess that you have a significant amount of experience writing OO or imperative code, and probably somewhat less writing in the functional style.

Unfortunately, non-strictness is the biggest hindrance to understanding operational semantics of Haskell. To my knowledge, people using Haskell in serious production use strictness annotations like there's no tomorrow.

I did a simple survey of our codebase... as I think we meet your requirements for serious production Haskell. Here's the terribly inaccurate and probably misleading results:

Raw line count:

    destroyer:alphaHeavy$ find . -name "*.hs" | xargs wc -l | tail -1
      132272 total

Things that look like bang patterns or strict fields:

    destroyer:alphaHeavy$ grep "\!" -rI . --include "*.hs" | egrep -v "\\$\!|\.\!|\!\?|\!\!" | wc -l
        1344

Strict returns:

    destroyer:alphaHeavy$ grep "\\$\!" -rI . --include "*.hs" | wc -l
         762

Unboxed fields:

    destroyer:alphaHeavy$ grep UNPACK -rI . --include "*.hs" | wc -l
         298

Strict fields in records are probably a better default than lazy fields. So you indeed see lots of strictness annotations in data structures. It also helps with unpacking/unboxing.

However, strictness annotations in functions is a relatively rare thing.

To do it the way he described (buffer of zeros + fill):

  import qualified Data.Vector.Unboxed.Mutable as V

  encode len fields = do
    buffer <- V.replicate len 0
    forM_ fields $ \(fieldPos, fieldData) ->
      V.copy (V.slice fieldPos (length fieldData) buffer) fieldData
    return buffer

I attended a talk at CUFP (Commercial Users of Functional Programming) by a compiler team at Intel on why they were using SML (which -- like caml -- not lazy by default and allows I/O and mutability without having to isolate them ala IO and St Monads) and the comments were quite interesting: many graph algorithms are best expressed in a mutable fashion and he saw no fundamental advantage of simulating mutable state via recursion/CPS (for algorithms that primarily used mutable state) and actual mutability; it wasn't a performance based argument -- the compiler still outputs extremely efficient (obviously) imperative assembly code, but the additional complexity.

Obviously the functional parts of the language still applied with primarily functional algorithms, like parse-tree traversal and transformation, which is an excellent example of monads being useful and handy outside of pure and lazy language.

Note that the author also notes two significant problems that have nothing to do with functional programming or purity per-se:

1) Calling language-x from Python/Ruby/whatever is difficult unless language-x is C/C++. I fully agree here. At one employer we've built custom bindings from Perl to OCaml (for a DSL we've built) and it was troublesome (e.g., it was broken during 64-bit conversion and our patch fixing it was not initially accepted, although the Nria team later came up with the same approach -- which involved "burning" a register -- later anyway).

This is less of a problem for large scale distributed applications that talk via RPC, but this create a problem of building and re-building first-class RPC libraries in each language -- which (as in this very example!) is again best done by building the core RPC protocol implementation in C/C++ and linking it into the applications (with perhaps a native JVM implementation as JNI is a pile of manure? [Personal curiosity: with Google having a huge Java presence, how does Google handle maintaining up-to-date Java clients for BigTable/Spanner et al?]).

2) Lack of OO.

OCaml has OO but it's never used. OCaml has a marvelous module system that is far better than Haskell's. Unfortunately it lacks type classes (hence -- very annoyingly -- no generic "print"/"show" function), but first class modules and campl4 (equivalent of template Haskell) can help there. I am guessing that it doesn't solve the author's problem (which I honestly can't claim I have, but that is like my opinion, man) -- lack of dynamic dispatch.

Problem is inheritance based dynamic-dispatch polymorphism and generic polymorphism are hard to reconcile. I am very impressed by the work Odersky has done with Scala as well as C++11 (and boost/tr1 before it), but these are by no means simple languages (by simple I don't mean simple like Visual Basic, I mean simple as in "implementing a compiler for it is feasible in an advance undergraduate or beginner graduate class").

When I write golang, Haskell, Erlang, or OCaml I honestly don't miss OOP as modules, interfaces/signatures, type classes, and the like provide what I want out of OOP. However, I've never maintained (as opposed to wrote) commercial code in these languages.

tl;dr That's all folks, I'm now switching to an emacs window to write more C++ code -- while (as a big FP enthusiast) hoping practices for programming-in-the-large would emerge for non-OO statically typed functional languages (from places like Basho, Galois, and Jane Street who have built impressive multi-year projects in those languages), OCaml gets multi-core support, and Scala succeeds in its mission.

Based solely on hearsay from a current Googler, they're using JNI for code sharing with the JVM, which remains a second class citizen for systems programming at Google.

[edit]: English.

I should elaborate a bit on RPC issues: RPC is somewhat of a misnomer, it's a fallacy ("fallacy of distributed computing") to think that a remote method call is the exact same thing as a local method call (anyone who has built a serious system using Java RMI or Spring RPC -- which hacked InvocationContext/used AOP to intercept local method calls and turned them into remote calls -- can confirm this).

Instead successful RPC wrappers tend to follow two patterns:

1) Thin client, with heavy lifting done on a server side proxy written in the same language as the original client. This is the pattern we followed with Voldemort when I was at LinkedIn -- there was a heavy Java RPC client (which had a lot of client logic) and thin clients that (like parts of the Java client) used protobuf over the wire, but contained much less logic.

Problem with this is that it adds an extra hop (latency issue) and at times interface mis-match viz. local clients.

2) Only expose the protocol via the RPC, write a first-class implementation (given the full blown protocol) in major languages. Practically this means native "fat" client (whether in Java or C++) uses the full RPC wire protocol (but may use a higher performance server implementation) and works in the case where major languages are Java (or JVM-based) and C/C++: Python/Ruby/PHP/etc... use Swig or custom extensions to use the C++ client, Java has its own native client built in parallel. If you add another language without FFI to either Java or C/C++ to the mix (or there's significant velocity mismatch between team working on the Java-based vs. C++ based clients/server) maintenance becomes an issue.

This is an approach I was following on my last project at FB with HBase (I've since left FB and am elsewhere, but the work is continuing and will likely be open sourced) for another distributed system -- where the proxy Thrift service always lagged behind the native client and where most heavy C/C++ based clients built their own thrift proxies to talk to HBase. Upstream HBase (and HDFS) -- FB has its own (open sourced) branch -- has also followed a similar approach with converting the native protocol to use protocol buffers for SerDe.

I agree that RPC is not equivalent to a local call. However, it's still worthwhile to create an API where making an RPC is as easy as possible, probably by making it look very much like a local call, as Cap'n Proto aims to do.

Note that Cap'n Proto's RPC will support promise pipelining. This means that if one RPC returns a pointer to another interface, you can start making RPCs to the returned interface before the first RPC has actually returned. Basically you're saying to the server "When you finish this RPC, invoke this method on its result.". The hope is that this will make it possible to avoid a lot of round trips even when using a call-return-style interface, thus making it reasonably possible for clients to use the Cap'n Proto interface definition directly without the help of a fat client library. And that, in turn, gives you freedom to use any language that has Cap'n Proto bindings, rather than the specific languages the server chose to support.

> For instance, to actually encode a Cap’n Proto message, I couldn’t just allocate a buffer of zeros and then go through each field and set its value.

Hah, dealing with native-encoded binary data in Haskell is rather cumbersome. I asked on r/haskell about decoding a native representation of float/double to corresponding Float/Double Haskell value, and this is the thread it generated:

http://www.reddit.com/r/haskell/comments/1k56i1/how_to_read_...

People have generally come with helpful suggestions, and rwbarton's excellent answer [check out the whole thread] has fully explained to me how to essentially reinterpret_cast a byte buffer.

I have been successfully playing with Haskell to implement some nontrivial _algorithms_ and liked. Like the OP, I'm now rethinking whether I want to invest more time into Haskell after seeing how cumbersome it can be to coerce the compiler into "DO THIS" where THIS is not a pure computation.

Now I'll take a pause from Haskell and start reading about Scala as it seems to provide a mix of FP and imperative (OO) that is more palatable to me.

I still don't understand why you even raised a reddit thread -- "Go with Data.Binary.IEEE754 and see if there's any reason not to like it -- it just works"

Is "genuine intellectual curiosity" a good enough answer?

I tried to figure out by myself how to reinterpret_cast a ByteString to something else (Float/Double in my case). I used ByteString because it was recommended by #haskell for binary IO.

I failed in my endeavor because the key function, which returns the pointer underlying ByteString, is in the hidden Internal subpackage. So I asked on reddit.

The internal module isn't actually hidden.

toForeignPtr should get you there: http://hackage.haskell.org/packages/archive/bytestring/0.9.1...

This is a chicken-and-egg problem.

Had I known about the existence of toForeignPtr [the link to Internal module doesn't even appear in the locally installed library docs], I would not have had started the reddit thread.

Again, how was I supposed to know about the existence of Internal submodule and toForeignPtr function?

I suppose it should have gone like this:

* You need to unmarshal hardware floats

* You visit Hackage, and use the IEEE754 package. http://hackage.haskell.org/package/data-binary-ieee754

If that is fast enough, you stop. You are done.

* IEEE754 is too slow for some reason, so you decide to do your own unsafeCoerce of bytestring

* You look at the source for IEE754 and decide to marshal memory yourself: http://hackage.haskell.org/packages/archive/data-binary-ieee...

* You read the bytestring package docs: http://hackage.haskell.org/packages/archive/bytestring/0.9.1... and pay attention to the "unsafe" functions that cast raw pointers.

* That lets you re-implement the IEEE754 package your own way

The mistake here was not using the highly-optimized existing library - http://hackage.haskell.org/packages/archive/data-binary-ieee... - which already does the correct thing. You jumped straight to "have to roll my own low level binary parsing" and then started a reddit thread instead. None of that was necessary.

> "have to roll my own low level binary parsing"

But that was the whole point from the beginning! Find out how can I do it myself.

> You read the bytestring package docs:

I repeat: the Internal module isn't listed in the locally installed documentation, and the link on Hackage is broken. Do I really need to produce for you the two top-level links where I was looking for the documentation of Internal?

The name Cap'n Proto is bit strange. The name makes me thing of CAP'N CRUNCH CEREAL and prototyping, but then I read about the connection to protocol buffers. Might want to think of a different name, e.g. Zero Data X "zero cost data interchange" or something.

I am using JSON to save structured data for an application, and this is interesting, although my app doesn't spend alot of time encoding/deconding the JSON since the data structures are fairly simple.

If I wanted to use this for Java, wouldn't there still be decode step to convert the fields into java objects?

The name makes me thing of CAP'N CRUNCH CEREAL... Might want to think of a different name

But... It's a cerealization protocol. :P

If I wanted to use this for Java, wouldn't there still be decode step to convert the fields into java objects?

Not necessarily. Your generated Java object could just contain a (ByteBuffer, int offset) pair. All the getter/setter methods then just write through to the underlying ByteBuffer.

http://docs.oracle.com/javase/1.4.2/docs/api/java/nio/ByteBu... is solid enough reading for the interested in encoding/decoding. It compares Direct v.s. non-direct buffers. The doc does remain somewhat circumspect about whether any work is done converting from raw memory to primitive values, for example in the use of getLong or putLong to read or write.

JSON makes me think of the Argonauts. They should probably change the name to something like "Language-agnostic hash-based data interchange format" or something.

In all seriousness, if you're familiar with protobuf the name seems reasonable enough. If you aren't, I guess you're not entirely the target audience.

If you do decide to use Haskell for another project come by one of our monthly meetups at the Hacker Dojo: http://www.meetup.com/haskellhackersathackerdojo/. Having more experienced Haskellers around to bounce ideas off of or pair program with can be rather enlightening.

I'm kind of shocked there hasn't been a horrified response from HN Haskell fans.

Fortunately, HN isn't reddit.

To be fair, r/haskell doesn't really see much in the way of fanboyism or name-calling. Not all subreddits are r/worldnews.

Yeah, aside from when /r/haskell gets relatively flooded by people who do not normally frequent the subreddit it is of exceptional quality and an example of a well-run community with one of the highest signal to noise ratios on the Internet.

Haskell having a high barrier to entry likely helps that along a great deal though.

Compare the quality in commentary on nontrivial subjects between /r/programming and /r/haskell for instance.

There will be an enormous amount of disinformation in the former, a state that is incredibly confusing for someone that lacks familiarity in the specific domain as discerning noise will not be easy.

On the other hand, /r/haskell largely in part does not comment as though they were an authority when they are not sufficiently competent to comment on a subject, so the signal remains high.

The subbreddit is fairly active given the niche current user base, and it is big enough that there are a decent amount of domain experts that comment.

The subreddit is also very polite.

I do not recall ever seeing a flame war break out there, which is notable compared to how often any discussion on the topic will break down into inanity, something which even occasionally happens here (such as https://news.ycombinator.com/item?id=6190005 from a couple of days ago).

> Haskell having a high barrier to entry likely helps that along a great deal though.

> The subreddit is also very polite.

Yes, it is very refreshing: it is a complex language, but the community has not become elitist, and is instead polite, considerate and mature.

Haskell devs need to be polite and considerate, otherwise GHC slaps them during the next 'cabal build' run with some hairy type errors. You really don't want that to happen twice.

(Just kidding, I love GHC and its precise & helpful error messages. No sarcasm implied.)

Why? I write haskell code every day, and his choice seems reasonable to me.

>> I'm kind of shocked there hasn't been a horrified response from HN Haskell fans.

"What an ignorant fool?! How could he abandon the holy grail of Haskell?!" -- like that? :)

For someone who wrote a lot of compiler and program analysis code in Haskell I can hardly imagine myself writing the same in C++. That said, I can totally understand the author's perspective. As the author writes, "I really wanted to like Haskell. [...] But when it comes down to it, I am an object-oriented programmer, and Haskell is not an object-oriented language." And I think that's the core of his troubles. I can imagine it's hard to write Haskell with an OOP mindset and expect it to be easy. I'm not saying pure functional programming is superior to imperative object-oriented programming -- they are just different and require different mindsets. Before I learned Haskell in the university the only language I had done any substantial amount of programming in was C++. And I had to make quite a switch in how I think of algorithms. I remember a lot of my classmates struggled with writing even the simplest programs in Haskell. But after some time I've really started understanding the Haskell way of thinking and, to me, it's easier to program in this language than in C++ which I regard as unnecessarily verbose and baroque.

Personally, I wouldn't even think about writing a compiler in C++ unless I was feeling masochistic. That said, I have never written a compiler in C++. So, should my experience in writing compilers in C++ have been greater and my experience with Haskell lower, it would have made sense for me to use the tool I knew how to use best (C++). Since I don't know how to write a correct compiler in C++ as fast as in Haskell, the only feeling I can express towards the author is pure and unadulterated awe.

PS: On that note, I've been shocked to discover that a horrified response from Haskell fans is expected. Haskell community is one of the friendliest and non-opinionated I've known, so I wonder why Haskellers are perceived as being akin to closet trolls.

FWIW, C++11 has massively improved the verbosity problem in C++, by introducing much more powerful metaprogramming features that make it possible to build more concise tools. As an example, I talk a bit in the article about how I've implemented parser combinators. They're not quite as concise as Haskell's, but they're a whole lot better than what you could do in C++03.

The down side is that taking full advantage of metaprogramming in C++11 requires learning a very large and complicated language. But once you've done that, it's really not so bad.

I agree, that the Haskell community is generally awesome. There are just a number of vocal trolls that tend to frequent HN.

There are?

Reply on news.ycombinator.com