Compile a language to C with OCaml GC support

Learning
#1

This is related to my previous post about support of stack allocation inside OCaml. I was wondering if it would be possible to compile a toy language to C, and include support for the OCaml garbage collector, as an opt-in for certain variables?

Example code:

struct Point {
  x: int;
  y: int;
}

function do_something(): int {
  local p1: point = {10, 20};  // Stack allocated
  let p2: point = {30, 40};  // Heap allocated, traced by the OCaml GC
  return p1.x + p2.y;  // p1 and p2 can interact
}

Possible? I don’t care so much about the potential slowdown compared to doing a “real” GC.

#2

I think you may be able to use the OCaml backend for that, maybe a new primitive on lambda will be required, essentially you can compile your code to the OCaml Lambda IR

#3

Will this work with stack allocation? :thinking:

#4

You can do pointer arithmetic, quite nicely, so you can just allocate your stack and encode the operations on top of it.

The trick is to allocate an array and add it’s pointer to the GC code section so the GC will not scan it, you just need to remember to keep a reference for the elements that are inside of the stack manually.

Essentially the problem is heap pointers inside of your stack.

#5

Since your project is to compile to C, it is probably possible to use the OCaml GC as a library via its C interface. You need to declare local and/or global roots, see https://caml.inria.fr/pub/docs/manual-ocaml/intfc.html#s:c-gc-harmony. Local roots (via CAMLparam, CAMLlocal) will let you scan variables on the stack, but this is implemented as a linked list and therefore less efficient than native OCaml compilation that uses frame descriptors.

1 Like
#6

… for more flexibility in your context, you can implement your own scanning function and register it with caml_scan_roots_hook from caml/roots.h.

By “stack allocation”, do you mean (for whatever experiment you have in mind) being able to refer to a value allocated on the stack from a value allocated on the heap?

#7

Thanks for the tip!

The interaction between the two memory layouts is not clear to me, honestly. Same issues apply as in Rust, when you include a pointer to an Rc value inside a stack allocated struct, where the Copy trait is required at dereference. A lot of copying can happen there. Same story as in C, where value types are copied automatically.

The example they use in Rust docs is Point {x, y} and Rectangle {top_right : Point, bottom_left : Point}.

The easiest solution is to completely separate the memory layouts, requiring a manual copy at interaction:

local p1 = Point {10, 20}
local p2 = Point {20, 30}
let rectangle = Rectangle {copy p1, copy p2};

Phrased differently, stack allocated variables are non-aliasing. Or maybe they can be aliased but in a restrained way, to avoid excessive copying, but also avoid the cognitive overhead of lifetime and ownership annotations.

#8

So I assume that if p1 or p2 contained pointers, they would point to the heap.

What you describe makes me think of Go. Go is a garbage-collected language whose memory representation is “value-oriented” which means that you can manipulate unboxed values like in C. This means passing/building values by shallow copy (memcpy) as in your example, but also be able to manipulate pointers taken inside of your values (interior pointers). It is an interesting point on the design space (at least from a memory management perspective :slight_smile: ). Being value-oriented means they can allocate less for value representation (than OCaml, say) and so they skip having a minor heap (while still benefiting from cache locality). As a consequence, the GC is non-moving, which combined with the rest means they have a good value interoperability story with C. See Getting to Go: The Journey of Go's Garbage Collector - The Go Blog.

With the OCaml GC, you will probably miss the ability to manipulate and store interior pointers, which is a big part of this approach. It makes unboxed values more modular. You can try to simulate interior pointers as pairs (base_ptr, 2 * offset + 1) and see if you can manage to avoid allocating memory cells for that pair by unboxing. So you would be manipulating values totally untypable in OCaml, but this is fine.

#9

That lecture note makes me confused about the Go target domain. If they care so much about speed, why use GC at all? GC is there to increase development speed, not runtime speed. Strange.

I wrote a little bit about my reasoning here: https://www.reddit.com/r/ProgrammingLanguages/comments/kxuv5l/programming_language_with_exactly_two_memory/

The problem with optimizing with Go is that it boils down to guess-work together with the debugger (which reports which variables escape and which do not). I see no reason why a programming language couldn’t help you with this on code-level instead of runtime-level.

I’m not interested at all in finding the fastest GC (that’s ridiculously comlicated) just to make the GC opt-in (or opt-out).

My current process right now is to manually translate the n-body and binary tree benchmarks from language benchmark games into what I think the language could look like. Next step is to write the AST, and then the C it should generate. :slight_smile:

#10

I’m not sure I understand the benefits of interior pointers, sorry?

#11

Interior pointers become a necessity when you mix heap allocated values and pointers, and when you allow the user to take pointers to array items or individual fields of a record. Go (and D) has explicit pointers so its GC has to deal with this problem. OCaml doesn’t have explicit pointers, and all the values are passed around by copy (some are copies of pointers to blocks, but you never access a record field by reference), so it’s not a problem.

#12

Got it, thank you. :slight_smile: