The Manchester Garbage Collector and purple-garden's runtime

Summary

Recently, while in Manchester, I designed and implemented the mgc - manchester garbage collector #10 for purple-garden. This article is a deep dive into its inner workings and why it is designed in the way it is.IntroWhile garbage collection in general is a widely researched subject, the combination of multiple garbage collection techniques can yield improved results compared to relying on a single strategy. The manchester garbage collector (mgc) is such a composite of several paradigms: allocation into preallocated memory regions, reachability analysis via recursive root set tracing and compacting semi-space copying. At the same time this is not novel, but specifically engineered for this runtime.Combining these approaches enables fast allocation, low allocation latency and reduced fragmentation.Purple-gardenmgc is specifically engineered for the purple-garden runtime. Purple-garden is a minimalist scripting language, designed and implemented with a focus on performance and a low memory profile, see: xnacly/purple-garden.NIX1fn greeting :: greetee { std::println("hello world to:" greetee) } 2greeting(std::env::get("USER")) # hello world to: $USER 3 4var v = "Hello World" 5std::println(std::runtime::type(v) std::len(v)) # str 11Purple-garden is focussed on embeddablity and ease of use as a scripting language. For this, it has a small memory footprint, a high performance runtime and a minimalist, yet useful standard library. It is implemented in C as a register-based bytecode compiler and virtual machine.While the above example doesn’t allocate memory (in the runtime itself) and therefore isn’t a great example for this article, it is still a great example what purple garden is about.A better example for some runtime heap pressure is the following recursive string concatenation:NIX 1fn f :: n { 2 match { 3 n < 100000 { 4 f(n+1) 5 var s1 = std::str::append("a" "b") 6 var s2 = std::str::append("c" "d") 7 var pair = std::str::append(s1 s2) 8 } 9 { std::println(n) } 10 } ...