The Garbage Collection Handbook (Jones, Hosking, Moss)

The Garbage Collection Handbook (Jones, Hosking, Moss) === ## Session 1 ###### tags: `Reading Group` :::info - **Date:** 2024-05-06 00:00 (UTC) - **Participants:** - Jedel (JDL) - Kevin (KN) ::: V8 Trash Talk blog: https://v8.dev/blog/trash-talk Spidermonkey blog: https://firefox-source-docs.mozilla.org/js/gc.html JDL: The book mentions that collectors are very specific to their use case. I suppose this would mean that we should base our design on V8's or SM's, since they have the same use case as ours. KDN: Yes, it's dense. I can find the links for Spidermonkey and V8. (expanded upon what I remember about them) KDN: What do you think about mark-compact? JDL: It's an interesting algorithm, but not really fit for the engine because we don't have a good way to override the roots without messing with embedding use cases. JDL: The book mentions to focus on Mutator performance over collector performance JDL: Mark/Cons ratio, and other builtin benchmarks. KDN: Agreed. This will probably come with the custom collector implementation. JDL: Java collectors use a custom benchmarking suite to test real uses cases [DaCapo](https://www.dacapobench.org/). JDL: We should probably implement bitmap marking to be able to implement other more advanced algorithms. Goal for next reading group (May18-19): Chapter 7-10 Good potential wins to consider: - Partitioning the Heap to block size and bitmap - Lazy Sweeping - Prefetching ## Session 2 :::info - **Date:** 2024-05-26 18:00 (UTC) - **Participants:** - Jedel (JDL) - Kevin (KN) ::: Chapter 7 - Allocation JDL: A lot of interesting optimizations. We should probably think about rewriting the GC so that allocations and collections have shared data. This could reduce the metadata of each object with a good heap partition. - V8 - Boundary types Kevin - Curious about allocating blocks (pages), and how that may be manageable. Might be possible to update `Gc` from `NonNull<GcBox<T>>` to `NonNull<Address<T>>` ## Partitioning the heap by Kind vs. Size Jedel - We could restrict the GC types for specific types (JsObject, DeclarativeEnvironment) Kevin - Size may be more generic. Boundary tags might also be an option to look into ## Allocation Jedel - We should definitely stop relying on the Global allocator and reimplement allocations to tie it to the collector. Kevin - Immix allocator as a concept is interesting to consider as we implement allocators (freeing a page in bulk vs. single items). ### Notes - How does a non-generic GC affect embedders? - We could probably enable mark-compact (and other features) by having `Gc` be a double pointer or a pointer to an address table. - Reducing Object size (probably independent of garbage collector). - Check MMtk to see if we can reuse their ideas for the allocator. - Rewrite the allocator side for the GC (aka don't abuse Box). - Have a better idea of what `Handle` represents. - https://github.com/v8/v8/blob/main/src/handles/handles.h - https://github.com/WebKit/WebKit/blob/main/Source/JavaScriptCore/heap/Handle.h - https://hg.mozilla.org/mozilla-central/file/942686767e5e/js/public/RootingAPI.h - https://hg.mozilla.org/mozilla-central/file/tip/js/public/HeapAPI.h ## Session 3 :::info - **Date:** 2024-06-10 03:00 (UTC) - **Participants:** - Jedel (JDL) - Kevin (KN) ::: Kevin: Most V8 primordial objects have fixed addresses. I think this causes some problems for Temporal. Jedel: Maybe this won't be a problem for Boa, because Rust is really good at size optimizations, and users who don't want to incur to the size cost can just disable Temporal using the feature. V8 Static Roots Blog - https://v8.dev/blog/static-roots Kevin: Essentially everyone (V8, SM) is doing generational, so it's good to have a better idea about what everyone's doing. Jedel: A dynamic schema may be good for JavaScript. Kevin: Agreed. But definitely need better observability/heuristics to measure Jedel: Definitely more observability. Though, right now we aren't doing interesting things to track, but after we have a generational garbage collector we'll have more interesting stats that we can base our decisions off of. Jedel: Assigning objects to builtins could make them immortal for optimizations. If we want to be more conservative, we could also mark them as old objects directly. General Note: Page 113-114 - between 64% and 95% DeCapo Java objects don't live past ~64 kilobytes V8 Finalizer doc - https://v8.dev/blog/high-performance-cpp-gc Kevin: Do we want to have a repo for doing experiments about the GC? Jedel: Definitely, I want to see if the Handle API is compatible with Rust in general. ### Notes - Check ways to parallellize the GC. - Implement generational garbage collection, which should be easy to adapt to future changes to the GC. - Create repo for experiments about the GC. For next week: chapter 11-12 ## Session 4 :::info - **Date:** 2024-07-07 18:00 (UTC) - **Participants:** - Jase (JW) - Kevin (KN) - Jedel (JDL) ::: ### Chapter 11 #### Kind vs Size Jedel: Some schemas are better if you consider the type of data. Jason: I don't know what the advantages of type are, apart from iterating an array. Kevin: Size makes more sense to me than type, take Nova they have a vec for every single built-in, which feels like a lot of fragmentation by typing. If you go size you have a lot more flexibility. Jason: Do you know what the other engines do? Kevin: V8 was storing the size of the object in its header, but that may have been the old GC. They were putting the object onto a page, then mark the starting bit then they would know that the first 2 bytes were the size, then fetch the whole object based on the bytes (not 100% sure). 11.2 - Finding pointers Jedel: Can we do conservative pointer finding from Rust? Kevin: Maybe we could integrate it with the VM, but I don't know if we could scan pointers from the Rust stack. I'm not sold on it though. Jedel: Yeah, I think doing that from the VM perspective could be good for starters, then implement advanced algorithms later. Kevin: We would have to see how to do that while having the VM and the GC in separate crates though. Jason: Yeah, the benefits of having separate crates is good Jedel: We'll have to see if we can maintain that when implementing finalisers though, because the Global roots Jedel: I guess for us that would be built-ins. Static Global roots could be useful for collection times, and immutable Jason: In this new world we wouldn't need to mark globals as they're static throughout the entire program? Kevin: You won't have to mark them but you would still need to trace through them Jedel: If the code doesn't modify the built-ins at all then the static options would be better. Kevin: We can have a specific page/region that is meant for forever-alive objects and anything that is added to a primordial we shift into that region. It's going to be rare someone is creating a loop and adding a property to a built-in object then removing it again. Kevin: I wonder if its concerning if we never collect object of built-ins, could it pause the heap as it takes up too much memory. Jason: Would we never collect anything attached to the built-ins? I assumed a reduced occurance of collections but still having some collection Jedel: If we have generational collection we could just move them to the old generation straight away. Todo - Check V8/SM for Kind vs Size in terms of heap allocations ## Session 5 :::info - **Date:** 2024-07-28 21:00 (UTC) - **Participants:** - Jase (JW) - Kevin (KN) - Jedel (JDL) ::: 11.5 stack barriers - Anytime you're hijacking or doing any level of indirection it feels like it should be a stable operation, but that could be wrong. 11.6 - Polling (stopping execution when a flag is set), the other is patching (modifying the bytecode when the VM is running) to have a new collect method. JDL - It could be good if in promise code we could have a job to collect, it could be good to use that for collection flags. I think its also used in the finalization registry. Jason - Yeah chapter 12 talks about finalization registry Kevin - We could be putting the state in the return frame itself. We have a completion type with a yield, its more of a completion flag with a yield bit flipped, I don't know how that would affect runtime. Jedel - We should have a clear separation with execution flags from the runtime and the engine itself. certain byte code that needs a flat that sets at compile time vs flags set at runtime. I think there was an issue that you could stop the engine from another thread. Kevin - I think its worth considering, as JS might change towards the future, there seems to be more primitives being added (exposing GC internals), so we should keep in mind and not design ourselves into a corner. 11.7 - Garbage Collecting Code Jedel / Jason - We should optimize the environment to remove variables that are no longer referenced by the inner closure. Jedel - I think we could do it (move from stack machine to register machine) incrementally, we could propose to him to merge it as it is, with all the transitionary op codes. Kevin - Is it possibe to ask for a design doc so we can keep track of what he's planning so we don't end up changing what he's planning. Jason - Yep 11.8 Jason - I found this blog post interesting https://webkit.org/blog/12967/understanding-gc-in-jsc-from-scratch/ Kevin - The further we get into this book the more we get into read/write barriers and how they integrate with the rest of the GC. 11.9 Managing address space Jedel - The stalling allocations thing is interesting. We could use it to squeeze a bit more performance from our current GC. Kevin - What is the overall performance loss from having to track that. Jedel - I'm pretty sure it's just a syscall and most of the time is spent on requesting memory from the OS, so it shouldn't be too expensive overall. Kevin - I agree. Kevin - If we implement our own allocator, it would be less time spent on having to do syscalls to request memory per item being created. Jedel - There was an interesting chapter about keeping track of heap size using virtual memory page protection, but I would prefer to do that after we do all the user code optimizations we can. Kevin - Yeah. That's a lot of work that we would have if we started doing syscall related optimizations. Kevin - Also, we should definitely return to this chapter again after we start the implementation of the concurrent garbage collector, since it has a lot of information that could be useful. Jedel - Yeah, definitely. We should maybe do an abstract of the most important items so that we don't need to read the whole chapter again in the future. Todo - Trying to schedule a reading session for the JSC post about write barriers (https://webkit.org/blog/12967/understanding-gc-in-jsc-from-scratch/) - Draft for the stalling allocations measurements with our current GC. - Try to see if we can start working on integrating the tracing framework (probably incrementally, start with the GC). - Start doing some design documenting work, probably start with the VM (the most complex part of the engine right now).