4

Unfortunately, due to .NET's lack of an incremental GC (either in the MS or Mono implementation), building soft real-time software such as games with F# is problematic. I've written a language in F# that, if -

a) it doesn't perform adequately in the face of the generational GC (arbitrary pauses during the interactive simulation, and b) OCaml gets a good complete port to the LLVM backend -

I will port it from F# to OCaml. I have avoided as much .NET-specific libraries as I could, and since F#'s syntax is based on OCaml's, I'm assuming there should be some automated tools to assist in converting the code.

Anyone know of such things, either finished or in progress?

Thanks deeply!

Bryan Edds
  • 1,696
  • 12
  • 28
  • 3
    Are you sure it will work better in OCaml? What reasons make you believe on that? – pad Jul 09 '12 at 15:57
  • 2
    There are no such tools. Although F# is based on OCaml, it has evolved a lot and is different in a number of ways, so automatic conversion (to readable OCaml) is not trivial. – Tomas Petricek Jul 09 '12 at 15:59
  • pad - without an incremental GC, the amount of time required for any given GC phase is unbounded. In practice, I presume this means that there will be arbitrary drops of frames during my game, say, every few seconds or so with .NET. This would be considered a severe bug. For many reasons, I program in functional style by default, so avoiding allocation with imperative style is not an option. I hope that through some magic that .NET's GC won't end up giving me this problem, but I doubt it. Also, F# seems generally slow compared to OCaml - another problem for games. – Bryan Edds Jul 09 '12 at 16:11
  • OCaml's stock GC is not fancy or incremental (as I understand the term). It's a generational GC with two generations. (Not a criticism--it's really good in my experience.) Last I heard, LLVM itself doesn't have GC, it instead offers support for GC at higher levels. If there are some interesting garbage collectors out there built on LLVM, it would be cool to try them out if OCaml gets an LLVM backend. But that seems like a big "if"--do you know of any progress on this front? – Jeffrey Scofield Jul 09 '12 at 16:13
  • As I currently understand, OCaml's GC is both incremental and generational (best of both words, presumably). From http://caml.inria.fr/pub/docs/oreilly-book/html/book-ora087.html - "Objective CAML's garbage collector combines the various techniques described above. It works on two generations, the old and the new. It mainly uses a Stop&Copy on the new generation (a minor garbage collection) and an incremental Mark&Sweep on the old generation (major garbage collection)." More context here - http://caml.inria.fr/pub/docs/oreilly-book/html/book-ora086.html#sec-GC-gen – Bryan Edds Jul 09 '12 at 16:15
  • The only thing I've found with OCaml on the LLVM is here - https://github.com/colinbenner/ocamlllvm . Last update was four months ago and I've not yet looked at how complete it is. – Bryan Edds Jul 09 '12 at 16:21
  • I am no expert on GC (hope Harrop will write here!) but I have seen people prefer F# over OCaml precisely because of a better GC. .NET GC can run in concurrent mode: http://msdn.microsoft.com/en-us/library/at1stbec.aspx – t0yv0 Jul 09 '12 at 16:32
  • *Attempts to summon Jon Harrop* – Bryan Edds Jul 09 '12 at 16:37
  • 1
    "I program in functional style by default, so avoiding allocation with imperative style is not an option" sounds capricious. Both OCaml and F# encourage dropping to imperative style (or even C!) in the 10% of your code that is performance critical. With this attitude, it sounds like your best bet is Haskell/GHC. – t0yv0 Jul 09 '12 at 16:37
  • I think you misunderstood me. You can (and should) drop to imperative style %10 while being functional the other %90 of the time. This is exactly what I mean by being 'functional by default' - being functional by default means write in a functional style until you get problems, then alternating to another approach. No problem. What most F# game devs do AFAIK is they program F# 'imperative by default', and only use functional techniques in %10 of the code. The latter totally defeats what I'm trying to do. The former does fully support it :) – Bryan Edds Jul 09 '12 at 16:39
  • 3
    Note that some of the avoidance of functional idioms is from F# developers targeting Xbox, where the CLR behaves significantly differently from the PC version. I'd recommend profiling your code to see what your bottlenecks really are rather than making assumptions. – kvb Jul 09 '12 at 18:46
  • 1
    @BryanEdds "most F# game devs": Is there anyone beside myself (Asteroid SharpShooter on the XBLIG channel) and the MS team that worked on "The Path of Go"? In any case, I definitely used the "functional by default" approach. I can't speak for the other team, but from presentations I saw, they did the same. Don't presume GC performance will be bad on the PC and take big decisions based on that. Also, don't expect GC in Ocaml to be a lot better. At least .NET gives you some control thanks to value types. – Joh Jul 10 '12 at 12:18
  • Joh - that would be good news. I have never hoped to be wrong about something as much as I hope to be wrong about this :) If F# and .NET can handle a 'functional-by-default' approach for game development, I will be ecstatic :) – Bryan Edds Jul 10 '12 at 14:32
  • @BryanEdds: "Attempts to summon Jon Harrop". LOL. Allow me to sort this out. The term incremental GC means it traverses the heap incrementally rather than stopping the world for the entire heap traversal so it dramatically reduces pause times. OCaml has an incremental GC because (although it does the minor heap or "nursery" in batch) the old generation is traversed incrementally using Dijkstra's tricolor marking scheme. – J D Mar 22 '15 at 22:20
  • As for practical pause times I typically get 10ms from OCaml and 100ms from .NET. In OCaml you must avoid large arrays of references (e.g. big hash tables) and deep stacks. In .NET the only way I have found to reduce pause times (which actually eliminates them) is to use pool allocators implemented as arrays of value types to avoid allocation entirely in the steady state. I have used this in commercial code (Infiniband drivers) to completely eliminate pauses. However, it is a major PITA. F# supports multicore whereas OCaml does not, of course. – J D Mar 22 '15 at 22:23
  • For a description of tricolor marking and incremental GC see http://www.memorymanagement.org/glossary/t.html#term-tri-color-marking – J D Mar 22 '15 at 22:25

2 Answers2

6

To answer your question in an answer - as far as I know, there are no such tools and I do not think it is likely somebody will create them.

Although F# is inspired by OCaml, it has evolved a lot and is different in a number of ways (see this SO discussion), so automatic conversion is not trivial. Even if somebody did that, it would be more like compilation to hard to read OCaml than conversion to idiomatic code that you can later continue working on.

To add a few general comments, when you speak about "real-time" I imagine controlling some robot in a factory dealing with dangerous stuff or an airplane control. In these areas, concerns about GC are certainly valid. However, I do not think games are necessarily "real-time". You need good performance, that's for sure, but people have been writing games with .NET and F# quite happily. For some F# examples, see:

These are probably simpler than what you're aiming for, but it may be good enough to show that writing games using GC is doable.

Community
  • 1
  • 1
Tomas Petricek
  • 240,744
  • 19
  • 378
  • 553
  • 2
    Games are in the category of 'soft real-time' software. Apologies for the use of the more blanket term. I have been reading Johann's blog from time to time. Much of it is about how you must fall back on imperative techniques to make games work in F#. Not only do you have to program F# as if it were C#, you can't even use C#'s functional idioms. I am unwilling to fall back on these techniques, I'm afraid. Cont'd... – Bryan Edds Jul 09 '12 at 16:33
  • ...My goal in life is to make practical use of functional programming _style_ for game development. I presume imperative techniques are either being used by default in the F# games you mentioned, or the embarrassing frame drops are being ignored. I hope this is wrong, but I need objective proof. We can program imperatively in F#, sure, but that's not at all my goal :) – Bryan Edds Jul 09 '12 at 16:34
  • @BryanEdds That makes good sense. I would definitely like to see how purely functional game works in F# compared to dirty imperative style. I suppose most of the people above use F# not as a purely functional language, but as a functional-first language with other nice features. That is, use functional where it makes the most sense (but maybe not for low-level aspects) and benefit from other nice features (i.e. use computation expressions to represent state, which might actually be the most important benefit compared with C#). – Tomas Petricek Jul 09 '12 at 16:44
  • Thanks! One more nuance however, it's not my goal to write pure functional code everywhere. I just want to write code that by default is purely functional (say, %80+ of the time). I am ecstatic to use other techniques (data-orientation, objects, imperative) when one happens to be the right tool for a particular job. From what I've seen, however, people _aren't_ using F# for games as 'functional-first', as you put it, but as 'imperative-first'... sort of like how many old school game dev's use C++ as C with templates. Total purity is not my goal, but functional-programming-by-default is. – Bryan Edds Jul 09 '12 at 17:00
  • 1
    (I have written some games in OCaml for iOS, for what it's worth. They are not *at all* graphics-heavy, but GC has never caused us any trouble. See my profile for a link to some free example code, etc.) – Jeffrey Scofield Jul 09 '12 at 22:48
6

Unfortunately, due to .NET's lack of an incremental GC (either in the MS or Mono implementation), building soft real-time software such as games with F# is problematic.

A few points here:

  • Incremental GCs are not the only way to get low pause times. Concurrent GCs like VCGC do the work in bulk but do it concurrently with mutators running, e.g. the VCGC implementation I described in the non-free article here was running with sub-millisecond pause times.

  • Incremental GC does not necessarily mean low pause times. For example, OCaml's GC typically incurs 10ms pauses and can incur arbitrarily-long pauses when it encounters a deep thread stack or long array in the heap.

I have measured typical pause times of 10ms with OCaml and 30ms with F# on .NET 3. With a simple implementation I was able to build a fault tolerant server in F# from scratch that handled 20k msgs/s with 50% of latencies under 114us and 95% under 500us.

I've written a language in F# that, if -

a) it doesn't perform adequately in the face of the generational GC (arbitrary pauses during the interactive simulation, and

I wouldn't give up on the platform is your first working version has unacceptable latency. There are lots of things you can do to bring the max latency down.

b) OCaml gets a good complete port to the LLVM backend -

I seriously doubt OCaml will ever get what I'd consider to be a "good complete port to the LLVM backend". They'll just retarget LLVM with the current typeless IR and it won't do much better than the current ocamlopt compiler because LLVM isn't designed to optimize that kind of workload.

I will port it from F# to OCaml. I have avoided as much .NET-specific libraries as I could, and since F#'s syntax is based on OCaml's, I'm assuming there should be some automated tools to assist in converting the code.

No automated tools but I've ported hundreds of thousands of lines of code between OCaml and F# now and it is generally very easy because most code is written in the core ML subset of both languages.

Community
  • 1
  • 1
J D
  • 48,105
  • 13
  • 171
  • 274
  • Hi Jon! I read your article on VCGC - very compelling! According to your data, I now suppose if I need to write (or pay someone to write) a GC for mono, it would be a VCGC. BTW, I sent you an e-mail about an article / possible consulting opportunity to 'consultant@ffconsultancy.com' that I hope you can get around to. Cheers! – Bryan Edds Aug 10 '12 at 12:24
  • @BryanEdds Oh, I forgot to mention that Mono's support for garbage collection is absolutely awful. You'll have to write Mono's first accurate GC which will require you to fix Mono's entire VM. You're probably looking at a £1m project. – J D Aug 10 '12 at 19:21
  • @BryanEdds: Mono has improved with SGen since I wrote that and now supports (I believe) "mostly accurate" collection which should be a lot better than Boehm's horrific GC. – J D Mar 23 '15 at 12:29