Measuring GC latencies in Haskell, OCaml, Racket | Hacker News Reader

Measuring GC latencies in Haskell, OCaml, Racket

prl.ccs.neu.edu

137 pointsedwintorok57 comments

Well, Today I Learned that Racket is GCed; I assumed the contrary due to John Carmack being enthusiast about it in the context of video games.

I understand the fact that not everything in a game belongs to the critical 16ms budget (and know about e.g. Unity, which lets you talk C# to it), but I'm still puzzled; can someone expand on:

- Which are these non critical parts? Rendering / physics / animation are certainly in the critical path. That leaves only simple "client" game logic out of it, right? What else?

- For these non critical parts, what are the typical acceptable time boundaries? For example, the article mentions "maximal latencies of around 22ms" for Racket. How is it acceptable for non-critical-path parts? How much would still be acceptable? 50ms? 100ms? "That depends"?

- And regarding Haskell and OCaml, which I only vaguely know about, I had never asked myself how they handle memory. Which makes me ask: are there non-GCed functional programming languages? Does it make sense? (Especially given the kinds of deep complex data structures produced by the immutability that often comes with these languages.)

The cogent language by nicta (an easy google away) has functional semantics but uses linear logic / linear types to make sure that no gc is needed. The code is on github and they have a very cool approach to generating proofs that any code generation maps the cogent code to equivalent c code. https://github.com/NICTA/cogent/tree/master/cogent

I've also been looking into how to add resource logic / linear logic to ghc Haskell / languages with a similar internal rep as ghc core. Still need to write that stuff up mind you.

There's a long history of no gc free functional language research. Mlkit and clean are probably two of the older but accessible implementations in the wild

As a datapoint, bone-lisp [0] is a Lisp-1 without a GC. There is prescheme [1] as well. Mlkit supposedly uses region-based management as well but I'm pretty sure it also has a GC too.

[0] https://github.com/wolfgangj/bone-lisp

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.40...

How much client code kinda depends a lot on genre, doesn't it? A shooter doesn't have a lot of that. Something like CSGO or BF1 might have things like the announcer, some LoD perhaps, streaming of skins and tags going on. Something like a TESV has all that content streaming, NPC pathfinding, quest tracking and those 10 million lines of scripts the user installed through mods going on.

There are at least functional programming languages that try to let you get by without or at least less GC:

ATS: https://bluishcoder.co.nz/2011/02/27/linear-datatypes-in-ats...

Stalin does global static life time analysis and MLKit uses GC only to augment it's region based scheme, but you can turn it off (at the cost of guaranteed space safety).

Of course Rust is a bastard child of ML as well.

PreScheme was a C replacement. It had manual de-allocation. Carp LISP is a new one with code being updated. MLkit supports reference-based GC, region-based management, and disabling GC for real-time use.

https://github.com/carp-lang/Carp

http://www.elsman.com/mlkit/

And in Unity3d, the GC is actually very problematic. For complex games, you need to focus on zero-allocation or there will be noticeable pauses. (See Kerbal Space Program) Object pooling is the way to go here.

I don't know if "problematic" is the right word seeing as even with manual memory management you have to do the same techniques. The problem is with allocation/destruction in general within the core loop.

It's more problematic in languages that encourage allocation since you have to work more to avoid it.

I've done game development in C++, C#, and JS, and I had to worry about memory management far more in JS than in C# or C++, simply because even something as innocent as adding two vec3s requires you come up with a space for the result first, if you want to avoid gc hitches.

C#'s struct types help here, but it still has plenty of its features increase GC pressure.

A consequence of a pre-historic Mono implementation.

It is challenging to deal with functional languages, especially non-strict functional languages, without GC. You can do it to some degree, but it requires some clever and inconvenient limitations on the language. Lifetimes and linear types are two approaches that can help. Clash and lambda-ccc can convert non-monomorphically-recursive Haskell code to a fixed-memory implementation (not even a stack, let alone a heap). Closures, unbounded recursion, and all those other things that make functional programming so convenient often require GC.

Exactly what I was hoping. Thanks for naming these things, names are what those of us without the academic baggage need to be able to investigate/study what we are talking about.

Just to be clear, in the Oculus scripting with Racket that Carmack has done, I don't think Racket is being used in the real-time way that you're suggesting. Instead, Racket is used to control and send commands to the Android device running the VR simulation.

> Well, Today I Learned that Racket is GCed

I'm curious how did you expect Racket to work without a GC or any Lisp like language for that matter or did you just assume because of video game usage?

> - And regarding Haskell and OCaml, which I only vaguely know about, I had never asked myself how they handle memory. Which makes me ask: are there non-GCed functional programming languages? Does it make sense? (Especially given the kinds of deep complex data structures produced by immutability.)

Rust and C++ depending on your definition of FP. I believe there are some old ML languages as well (and even some old lisps).

Am I misreading something? The first half of your comment seems to suggest that no lisp language could work without a CG, while the second half suggest there're some lisp languages that do.

Because I don't know how modern Lisps can do it (I believe there was hardware like lisp machines made specifically for Lisp that would deal or help with memory allocation/reuse as well as some code generation).

I honestly was curious if the OP had some insight that I did not. I realize re-reading the comment it sounds snide but I didn't want to assume the OP's knowledge.

For all I knew Racket could have some ability to avoid GC.

https://github.com/carp-lang/Carp

> "I'm curious how did you expect Racket to work without a GC or any Lisp like language for that matter or did you just assume because of video game usage?"

Just because of video game usage and my perception of Carmack as a performance freak who wouldn't compromise on performance. (Sloppy reasoning, I know! Thus, my questions on where GC makes sense in games)

I actually was curious and not trying to be snide. For example I wasn't sure if Carmack or whoever might be using Racket for code generation (ie multi-stage programming) which in theory would avoid GC. I wasn't sure how he was using Racket.

No problem, your comment was clear and I didn't perceive it as snide, at all. Thanks for your carefulness in the discussion.

It should be noted that he used Racket to teach his son game programming. He mentioned in his QuakeCon 2013 talk that he was enthusiastic about FP concepts, but is too entrenched with C++ to make a change.

https://news.ycombinator.com/item?id=13107075

> are there non-GCed functional programming languages?

Yes, C++. For the last 18 years the C++ standard has been busy adding functional features to the language. With mixed success, but still the result is quite impressive.

I have a really dumb question about the Haskell GC, which I've never been brave enough to ask, but here goes:

I thought everything in Haskell was immutable? If so, wouldn't that imply that it's impossible to create cyclic references (i.e. A and B can't both reference each other, because one of them has to be created first, and once created, it's immutable)?

Couldn't you then just use reference counting to decide when to recycle objects instead of having full-blown GC pauses? Or is it too expensive to keep a reference count on all those objects and keep it updated? Whatever cost it has, it seems much more preferable to me compared to 50 ms GC pauses for relatively simple code.

Not a dumb question at all! You can create cycles in Haskell thanks to lazy evaluation. I can make a circular list in Haskell with the following:

x :: [Int]

x = 0 : y

y :: [Int]

y = 1 : x

And thus we have a circular list with the elements 0 and 1. It's technically an infinite-length list with 0 and 1 repeating forever, but Haskell will represent this in memory as a circular list.

Ah, I see, I figured that there might be some case like that. I would have expected that to be a compile-time error because `y` is an unrecognized identifier by the time `x` is defined, but I guess it makes sense with lazy evaluation to not make that kind of ordering matter.

Lazy evaluation is not important item here. It is merely the semantics is defined in a way that the order of declarations does not matter.

Other languages have this property too - say, C# (not entirely true, but pretty close - at least if you think about top level methods etc.).

Also an example where the order of declarations does not matter at all, because there is just one declaration:

   x :: [Integer]
   x = 0 : 1 : x

Yeah, all definitions are module level unless they are scoped in let or where blocks (someone correct me if I'm mistaken)

It ought to, yes. More specifically, immutability means that you cannot observe sharing. What this means is that it's easy to break sharing and if you rely on it for performance you might face difficulties.

But you can create it. Names are shared:

    let x = [1, 2, 3] in [x, x, x]

There are more exotic ways, too.

The key thing missing from the responses so far is that laziness is a (particularly constrained) kind of mutability.

Yes you are correct, for statically typed (and not lazy) functional languages. In this case Ref counting will work fine since you can't create cycles. See http://www.forwardscattering.org/post/47

Usually copying is only to compact everything alive back together for cache friendliness. However, it shouldn't need a stop the world for that due to immutability.

Why is it that GC technology is so hard to transfer from one language to another? I'd kill for a FLOSS implementation of Azul's GC, or a good small-heap-specialized GC for .NET.

It seems far too often we run into popular languages whose growth has stalled due to their GC, or features that have been held back by GC, or whatever. And then other languages have several different GCs with different characteristics that can be swapped out with a simple CLI flag.

Is it something that is deeply and strongly coupled to the language structure? Is the parameter space for tuning just too large to practically swap one GC for another? Incompatible algorithms? Maybe one of those situations where you get 80% of the way with an ounce of effort, but to get to 81% takes years?

Some answers that come to mind:

  - Azul's GC requires cooperation from the kernel; I believe it
    specifically uses the virtual memory mechanism to implement a read
    barrier.  Basically you need a patched Linux kernel.
  - Real-time GC will assuredly lower overall throughput, and increase
    complexity.  At the very least you need either a read barrier or a
    write barrier.  I don't think anyone uses read barriers normally;
    write barriers are often used for generational GC, but I *think*
    the write barriers used for real-time GC involve more work than
    those for generational GC.
  - Adding a read or write barrier to a language implementation that
    doesn't already have them means you need to guard every single
    place where someone reads or writes what might be a pointer.  This
    is easy to screw up.
  - Several real-time GC algorithms punt on moving objects, and are
    thus vulnerable to memory fragmentation.  This obviously reduces
    the robustness of the runtime system.  (Others use stop-the-world
    to do compaction, and thus are not real-time.)

Follow up: https://blog.pusher.com/golangs-real-time-gc-in-theory-and-p... and HN: https://news.ycombinator.com/item?id=13086059

I don't know Haskell but it sure has some odd syntax:

    type Chan = Map.Map Int ByteString.ByteString

is odd looking. Why the duplication?

Haskell namespaces are a bit annoying.

let's look at the stdlib `replicate` function. `replicate 5 'x'` gets you `['x', 'x', 'x', 'x', 'x']`. But that's a standard haskell linked list, and there's other list-y things, like ByteString. So there's bytestring module has it's own replicate function which returns a ByteString (like an array afaik) instead of a list.

Now, a bare `import bytestring` just dumps all of the module - its datatypes, its functions - into the global namespace, like a Python `from bytestring import *`, so the two replicate functions are gonna clash. There's a solution - we do `import qualified bytestring`. it behaves like a normal Python `import bytestring`, which means that we have to type `bytestring.replicate` to get that function from earlier. all of the stuff inside the bytestring module is hidden away inside this namespace.

Now, the trouble is, EVERYTHING is hidden away. So, say I want to refer to the actual ByteString datatype, say to write a type signature like: ``` length :: Bytestring a -> Int ``` Now, because of the namespace qualification I did, I actually have to write the verbose ``` length :: bytestring.ByteString a -> Int ``` So that's like saying "bytestring-module.ByteString-datatype" every time you want use a ByteString. that's what the author does, hence the weird duplication you noticed comes from.

The usual solution is: ``` import qualified Data.ByteString as B -- the functions import Data.ByteString (ByteString) -- the datatype ```

which roughly translates to Python as: ``` import bytestring as B from bytestring import ByteString # the ByteString class ```

so now, I can use `B.replicate`, and `ByteString`, which is what I want! Great! But the importing is verbose and, as I said, kinda annoying.

They used qualified imports:

    import qualified Data.ByteString as ByteString
    import qualified Data.Map.Strict as Map

So everything from “Data.ByteString” has to be prefixed with “ByteString.”

In real-world code, depending on conventions, you’d probably add unqualified imports for the type names to avoid the needless duplication:

    import Data.ByteString (ByteString)
    import Data.Map.Strict (Map)
    import qualified Data.ByteString as ByteString
    import qualified Data.Map.Strict as Map

    type Chan = Map Int ByteString

    pushMsg =
      …
        let inserted = Map.insert …

Also, `ByteString` as the qualified name is a bit unusual but it probably is helpful for clarifying what's going on for people unfamiliar with Haskell. I'm more used to seeing:

    import Data.ByteString (ByteString)
    import qualified Data.ByteString as BS
    import qualified Data.ByesString.Lazy as BSL
    import qualified Data.ByteString.Char8 as BSC

That's what you get by importing qualified and being too verbose.

This same can be written as:

  type Chan = Map Int ByteString

People do prefer importing Map and ByteString qualified, so their functions will have a prefix of their choice. But very few people import ByteString as "ByteString", most use something shorter.

Gotta say, I'm Team Qualified Import. Use it all the time in my Clojure code. I want to know where things come from.

On Haskell you don't even get much choice. The community is so biased towards qualified importing that most modules clash, and you'd need some incredible stretching to use them unqualified.

As most things in Haskell, it tends to work greatly. The usual problems go away due to some combination of Haskell's features and the main problems are things you wouldn't think about.

Totally reasonable, but most people would use BS instead of ByteString as the qualified name.

so can we reasonably surmise that Ocaml outperforms Haskell massively on GC pauses? What's the catch, if any?

Hum... No.

We can conclude that Ocaml outperforms GHC on this edge case for the GC.

There's nothing to conclude here about a general case, and it may not even be possible to make general conclusions about GC.

> ... and it may not even be possible to make general conclusions about GC.

Exactly my experience of the Java JIT and GC where I worked on uh "optimizations" of related metrics in two or three projects.

I too find with Java (most of my career I worked with it) if you change hardware just slightly you can also get wildly different results making other users benchmark conclusions on GC and JIT not very helpful. Like your armpits the only benchmarks that don't stink are your own :)

OCaml is not yet multicore ready. Also, overloaded operators aren't available, which can be a bit of a pain if you're writing numerical code. Otherwise it's a great language.

...and a terrible ecosystem. I recently mucked around with getting set up in Ubuntu Linux with F#, Haskell, Ocaml, and others. Ocaml to me was the worst in terms of user friendliness. I never got it working, so I'm working in Haskell. I hope some day somebody spits out a truly good docker image of Ocaml Batteries Included.

Catches with OCaml? Mutable strings, unchecked integer arithmetic. It's got its fair share of ugly corners.

it seems to me that ocaml/(ocaml zealotry) > haskell/(haskell zealotry). This of course does not suggest that Ocaml>Haskell, only that one must probably apply some coefficients in favour of Ocaml given that it is extra-anglo-saxon domain and therefore probably suffers some marketing disadvantage.

Just a casual observation of the commento-sphere after a lay imperative programmer's cursory research of functional programming. This post, sample-of-one hugely notwithstanding, seems in the absence of counterpoints to suggest that, as potentially narrow as the benchmark may be, Ocaml has some very strong arguments against Haskell on the compiler implemenation front.

I can't help but wonder if this GC outperformance is the flipside of the coin of Ocaml's much maligned lack of multi-core capability.

Well said, and I feel exactly the same way (as an interested observer)

Mutable strings are on the way out though. 4.02 introduced -safe-string and 4.04 lets you build compilers and OPAM switches that mandate it.

This reminds me of the Great Programming Language Shootout.

Anyone here who knows what happened to that great site?

It evolved into The Computer Language Benchmarks Game.

https://benchmarksgame.alioth.debian.org

Roll the credits :-)

http://benchmarksgame.alioth.debian.org/sometimes-people-jus...

Just Google "Great Programming Language Shootout"

Reply on news.ycombinator.com