8 ms·

Measuring GC latencies in Haskell, OCaml, Racket

137 points by edwintorok 10y ago

nvartolomei 10y ago
Follow up: https://blog.pusher.com/golangs-real-time-gc-in-theory-and-practice/ https://blog.pusher.com/golangs-real-time-gc-in-theory-and-p... and HN: https://news.ycombinator.com/item?id=13086059 https://news.ycombinator.com/item?id=13086059
coldcode 10y ago
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?
- marcosdumay 10y ago
  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.
  - moomin 10y ago
    Gotta say, I'm Team Qualified Import. Use it all the time in my Clojure code. I want to know where things come from.
    - hood_syntax 10y ago
      Totally reasonable, but most people would use BS instead of ByteString as the qualified name.
    - marcosdumay 10y ago
      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.
  - deleted 10y ago
    [deleted]
- evincarofautumn 10y ago
  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 …
  - buckie 10y ago
    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
- uryga 10y ago
  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.
  - deleted 10y ago
    [deleted]
OskarS 10y ago
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.
- cordite 10y ago
  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.
- deleted 10y ago
  [deleted]
- openasocket 10y ago
  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.
  - OskarS 10y ago
    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.
    - hood_syntax 10y ago
vegabook 10y ago
so can we reasonably surmise that Ocaml outperforms Haskell massively on GC pauses? What's the catch, if any?
- marcosdumay 10y ago
  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.
  - dom0 10y ago
    > ... 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.
    - agentgt 10y ago
      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 :)
- moomin 10y ago
  Catches with OCaml? Mutable strings, unchecked integer arithmetic. It's got its fair share of ugly corners.
  - Tobu 10y ago
    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.
  - vegabook 10y ago
    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.
ronjouch 10y ago
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.)
- dom0 10y ago
  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.
- agentgt 10y ago
  > 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).
  - ronjouch 10y ago
amelius 10y ago
This reminds me of the Great Programming Language Shootout. Anyone here who knows what happened to that great site?
- lionsdan 10y ago
  It evolved into The Computer Language Benchmarks Game. https://benchmarksgame.alioth.debian.org https://benchmarksgame.alioth.debian.org
  - igouy 10y ago
    Roll the credits :-) http://benchmarksgame.alioth.debian.org/sometimes-people-just-make-up-stuff.html#history http://benchmarksgame.alioth.debian.org/sometimes-people-jus...
- deleted 10y ago
  [deleted]
- igouy 10y ago
  Just Google "Great Programming Language Shootout"
saosebastiao 10y ago
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?
- waterhouse 10y ago
  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.)

137 points by edwintorok 10y ago

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

coldcode 10y ago

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?

marcosdumay 10y ago
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.
- moomin 10y ago
  Gotta say, I'm Team Qualified Import. Use it all the time in my Clojure code. I want to know where things come from.
  - hood_syntax 10y ago
    Totally reasonable, but most people would use BS instead of ByteString as the qualified name.
  - marcosdumay 10y ago
    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.
- deleted 10y ago
  [deleted]
evincarofautumn 10y ago
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 …
- buckie 10y ago
  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
uryga 10y ago
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.
- deleted 10y ago
  [deleted]

OskarS 10y ago

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.

cordite 10y ago
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.
deleted 10y ago
[deleted]
openasocket 10y ago
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.
- OskarS 10y ago
  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.
  - hood_syntax 10y ago

vegabook 10y ago

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

marcosdumay 10y ago
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.
- dom0 10y ago
  > ... 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.
  - agentgt 10y ago
    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 :)
moomin 10y ago
Catches with OCaml? Mutable strings, unchecked integer arithmetic. It's got its fair share of ugly corners.
- Tobu 10y ago
  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.
- vegabook 10y ago
  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.

ronjouch 10y ago

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

dom0 10y ago
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.
agentgt 10y ago
> 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).
- ronjouch 10y ago

amelius 10y ago

This reminds me of the Great Programming Language Shootout. Anyone here who knows what happened to that great site?

lionsdan 10y ago
It evolved into The Computer Language Benchmarks Game. https://benchmarksgame.alioth.debian.org https://benchmarksgame.alioth.debian.org
- igouy 10y ago
  Roll the credits :-) http://benchmarksgame.alioth.debian.org/sometimes-people-just-make-up-stuff.html#history http://benchmarksgame.alioth.debian.org/sometimes-people-jus...
deleted 10y ago
[deleted]
igouy 10y ago
Just Google "Great Programming Language Shootout"

saosebastiao 10y ago

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?

waterhouse 10y ago
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.)