How does HLVM's GC work?

HLVM injects code into managed user-code functions that keep two data structures up to date:

  • The shadow stack lists all references held on the stack or in registers and acts as the set of global roots into the heap. If a function accepts an argument of a reference type or allocates then the value is pushed onto the shadow stack. On function exit, the shadow stack is reset back to the way it was when the function was entered.
  • The allocated list gives all of the references that have been allocated by the program. When a function allocates, the value is appended onto the allocated list.

When the allocation quota is exceeeded a garbage collection occurs. This is composed of two phases:

  1. Mark. Starting from the global roots on the shadow stack, all reachable data in the heap are marked as reachable (and the rest left marked as unreachable).
  2. Sweep. The allocated list is traversed, unreachable values are freed and all values have their mark state set back to unreachable.

This functionality requires only one non-trivial feature: given a value of a reference type it must be possible to find out what it references. In OCaml, the uniform representation makes it possible to traverse any value using the same code. HLVM uses a different approach: all values contain a pointer to a function that knows how to traverse values of that type. I called this the "visit function".

A block of OCaml code defines the def_visit, visit and def_visit_array functions. The def_visit function takes an HLVM description of a type and creates an HLVM function that finds all references contained within a value of that type. There are two kinds of reference type in HLVM: unions and arrays. The visit function does this for a non-array type and the def_visit_array function does this for an array type by creating an auxiliary function to traverse the elements of the array.

A block of HLVM code defines gc_mark_all, gc_mark, gc_sweep and gc functions. The gc_mark function traverses the shadow stack and then calls the gc_mark_all function to recursively traverse the entire heap marking values as reachable. The gc_sweep function traverses the allocated list freeing unreachable values and resetting all mark states back to unreachable. Finally, the gc function simply calls gc_mark and then gc_sweep to perform a complete garbage collection.

This simple algorithm, implemented in only a few dozen lines of OCaml code, is all that is required for HLVM to reliably recycle unreachable values. The next stage in the evolution of HLVM's garbage collector will be support for parallel threads by stopping all mutator threads when performing a collection. Once this is complete, HLVM will finally be a competitive platform for high performance parallel numerics. A further improvement will be the implementation of a variant of the Very Concurrent Garbage Collector (VCGC) that allows mutator threads and garbage collection threads to run concurrently, offering both better pause times and overall performance.

The HLVM project is described in detail in the OCaml Journal.

Comments

Post a Comment

Popular posts from this blog

Bjarne Stroustrup is catching up

Bjarne Stroustrup, creator of the C++ programming language, once famously said "There are only two kinds of languages: the ones people complain about and the ones nobody uses". Interestingly, Bjarne has gone on the defensive in his recent lectures, completely changed his tune and is catching up with the conclusions that most former-C++ developers have arrived at. In a recent lecture Bjarne made many eyebrow-raising assertions. He is happy that people are no longer talking about C++ because that means it has succeeded. In reality, C++ demand in the job market has been in freefall for years and few new software projects are choosing it. He attacked computer scientists for copying data and said that "even babies don't do that", a very strange statement to make in a technical presentation. He also implied that other languages deep copy 10,000x10,000 matrices and claimed that a shared_ptr is "like an old fashioned garbage collector except it gets resource relea...
Read more

Does reference counting really use less memory than tracing garbage collection? Mathematica vs Swift vs OCaml vs F# on .NET and Mono

Image
Our previous post caused some controversy by questioning the validity of some commonly-held beliefs. Specifically, the beliefs that reference counting (RC) always requires less memory than tracing garbage collection (GC) and that tracing GCs require 3-4x more memory in order to perform adequately. We presented a benchmark written in Swift and OCaml and noted that the RC'd Swift implementation ran over 5x slower and required over 3x more memory than the tracing GC'd OCaml implementation. This observation disproves these beliefs in their strong form and even brings into question whether there is even any validity in the weak forms of those beliefs. After all, we have never seen any empirical evidence to support these beliefs in any form. We received a lot of criticism for that post. The vast majority of the criticism was not constructive but two valid points did arise. Firstly, although our result was anomalous it would be more compelling to see the benchmark repeated across a w...
Read more

Benchmarking in the web age

The TechEmpower website contains some fascinating benchmarks of servers. The results on this benchmark of multiple requests to servers provide some insight into the performance characteristics of .NET on a modern problem. Specifically, the C# on ASP.NET Core solutions range from 2.5-80× slower than fastest solution which is written in Rust. In fact, C# is beaten by the following programming languages in order: Rust Java Kotlin Go C Perl Clojure PHP C++ Furthermore, .NET Core is Microsoft's new improved and faster version of .NET aimed specifically at these kinds of tasks. So why is it beaten by all those languages? I suspect that a large part of this is the change in workload from the kind of number crunching .NET was designed for to a modern string-heavy workload and I suspect .NET's GC isn't as optimised for this as the JVM is. As we have found, .NET has really poor support for JSON compared to other languages and frameworks, with support fragmented across many non-stand...
Read more