8 ms·

High-performance garbage collection for C++ V8 (2020)

97 points by signa11 5y ago

dragontamer 5y ago
It makes sense for a Javascript engine to optimize for main-thread latency. But the code I write for fun is usually throughput bound: meaning a 2nd thread should try to minimize the additional work to be done. I do wonder what the appropriate metrics for a garbage collector should be. This post focuses entirely on the main-thread times, but maybe "total CPU-time used" would be better? Especially if it was split up using hardware performance counters (ex: how much time waiting on L1, L2, L3 cache, and DDR4 RAM). I'd imagine that having multiple cores work on application + garbage collection in parallel would cause more main-memory hits (the garbage collector would have to keep its state in cache, probably L3 cache, meaning the application has less L3 cache to work with). So overall throughput would be lower than the single-threaded solution. -------------- But yes, latency is king for UI programs. I guess I'm just musing about the "what to measure" problem.
- slaymaker1907 5y ago
  On a related note, if you are building a UI, an even better solution for computationally intensive work is to offload it onto a separate process instead of just a separate thread. This ensures that the UI thread is not blocked as often due to GC. Obviously this isn't really possible in JS (outside of Electron), but this can be a good idea in languages like Java.
  - croshan 5y ago
    I think this is possible to do with JS + WASM/Service workers? And even with many background threads, in WASM: https://developers.google.com/web/updates/2018/10/wasm-threads https://developers.google.com/web/updates/2018/10/wasm-threa...
  - esprehn 5y ago
    There's overhead to a process that doesn't exist with threads. You can definitely split your work across threads in JS using Workers, ServiceWorkers and the main thread. Most apps don't take advantage of this very well though. Using a separate thread gets you the same GC benefits. There have been some attempts to make it easier to use threads on the web like the excellent Comlink library: https://github.com/GoogleChromeLabs/comlink https://github.com/GoogleChromeLabs/comlink
  - pjmlp 5y ago
    It has been possible for quite a while with background workers.
mirekrusin 5y ago
Looking from the distance it feels like making gc a library is... important. There seems to be a lot of gcs, many extremely sophisticated. Wouldn't it be great if they consolidate with time on common api and could be exchanged with minimal effort? Without knowing too much about intricacies, wouldn't it be beneficial to have system (kernel) provided gc? Surely there are no cost ways of sharing userspace usage of pointers with the kernel?
- dragontamer 5y ago
  Kernel-code is secure code. That means you need to defend against a variety of speculative and/or side-channel attacks. This is because the superuser has the passwords (and other "secure" data) to the entire system in the superuser's memory space. Lesser users must never gain access to superuser memory. The kernel is the keys to your kingdom, since its responsible for protecting superuser (and other users). As such: you must never allow a side-channel attack against other users through the kernel. This means that a significant amount of inefficiency must be introduced (ie: flushing TLB caches, among other things) whenever the kernel executes. ----------- The current plan of action for most OSes is to therefore never have the kernel run. Linux's "futex" for example, are purely userspace in the "hot" case. (In the "cold" case, such as a task-switch becomes necessary... the kernel would run. But these cases are minimized as little as possible). Similarly: I'm not sure what moving the garbage collector into the kernel would accomplish at all. It'd frankly be faster as a library, since you wouldn't need to do a secure task-switch.
  - mirekrusin 5y ago
    You wouldn't have to preallocate memory. Kernel should know better when it's good time to mark and sweep. Unpinning memory doesn't have to have immediate effects. I don't think sidechannel attacks would be possible, the only task for kernel is to deallocate at some unknown point in time dereferenced memory, which by definition should not be visible from the user space? Maybe a bit far fetched but parts of the kernel (will never happen) or kernel modules (possible) could use it as well?
    - 5y ago
choeger 5y ago
Unfortunately, they didn't follow up on the scanning part. How does that work? Ok, the allocator is obviously cooperating, but how do you get from scanning piece of C++ memory to the class of the object?
- sanxiyn 5y ago
  All GC objects have GC headers prepended, from which you can lookup the class and how to scan it. https://github.com/v8/v8/blob/master/src/heap/cppgc/heap-object-header.h https://github.com/v8/v8/blob/master/src/heap/cppgc/heap-obj...
- Leszek 5y ago
  When scanning the stack, you interpret every word as a potential pointer. Then, you ask your GCs allocator "is this pointer's address in one of your pages?". If it isn't, you're done. If it is, then you check if it's the pointer to the start of an object (there's a bitmap of "is object start" for each word on the page). If this passes too, then you effectively reinterpret cast it to a "GC object" base class which is shared for all GC objects, and call the virtual "trace" function from there.
  - flohofwoe 5y ago
    Maybe a stupid question, but how would this detect random data byte sequences that accidentally form a valid GC object pointer?
    - sanxiyn 5y ago
      It doesn't. That is what it means for GC to be conservative.
- _old_dude_ 5y ago
  Here is the related research paper https://duckduckgo.com/?q=Cross-Component+Garbage+Collection https://duckduckgo.com/?q=Cross-Component+Garbage+Collection

97 points by signa11 5y ago

It makes sense for a Javascript engine to optimize for main-thread latency. But the code I write for fun is usually throughput bound: meaning a 2nd thread should try to minimize the additional work to be done. I do wonder what the appropriate metrics for a garbage collector should be. This post focuses entirely on the main-thread times, but maybe "total CPU-time used" would be better? Especially if it was split up using hardware performance counters (ex: how much time waiting on L1, L2, L3 cache, and DDR4 RAM). I'd imagine that having multiple cores work on application + garbage collection in parallel would cause more main-memory hits (the garbage collector would have to keep its state in cache, probably L3 cache, meaning the application has less L3 cache to work with). So overall throughput would be lower than the single-threaded solution. -------------- But yes, latency is king for UI programs. I guess I'm just musing about the "what to measure" problem.

slaymaker1907 5y ago
On a related note, if you are building a UI, an even better solution for computationally intensive work is to offload it onto a separate process instead of just a separate thread. This ensures that the UI thread is not blocked as often due to GC. Obviously this isn't really possible in JS (outside of Electron), but this can be a good idea in languages like Java.
- croshan 5y ago
  I think this is possible to do with JS + WASM/Service workers? And even with many background threads, in WASM: https://developers.google.com/web/updates/2018/10/wasm-threads https://developers.google.com/web/updates/2018/10/wasm-threa...
- esprehn 5y ago
  There's overhead to a process that doesn't exist with threads. You can definitely split your work across threads in JS using Workers, ServiceWorkers and the main thread. Most apps don't take advantage of this very well though. Using a separate thread gets you the same GC benefits. There have been some attempts to make it easier to use threads on the web like the excellent Comlink library: https://github.com/GoogleChromeLabs/comlink https://github.com/GoogleChromeLabs/comlink
- pjmlp 5y ago
  It has been possible for quite a while with background workers.

mirekrusin 5y ago

Looking from the distance it feels like making gc a library is... important. There seems to be a lot of gcs, many extremely sophisticated. Wouldn't it be great if they consolidate with time on common api and could be exchanged with minimal effort? Without knowing too much about intricacies, wouldn't it be beneficial to have system (kernel) provided gc? Surely there are no cost ways of sharing userspace usage of pointers with the kernel?

dragontamer 5y ago
Kernel-code is secure code. That means you need to defend against a variety of speculative and/or side-channel attacks. This is because the superuser has the passwords (and other "secure" data) to the entire system in the superuser's memory space. Lesser users must never gain access to superuser memory. The kernel is the keys to your kingdom, since its responsible for protecting superuser (and other users). As such: you must never allow a side-channel attack against other users through the kernel. This means that a significant amount of inefficiency must be introduced (ie: flushing TLB caches, among other things) whenever the kernel executes. ----------- The current plan of action for most OSes is to therefore never have the kernel run. Linux's "futex" for example, are purely userspace in the "hot" case. (In the "cold" case, such as a task-switch becomes necessary... the kernel would run. But these cases are minimized as little as possible). Similarly: I'm not sure what moving the garbage collector into the kernel would accomplish at all. It'd frankly be faster as a library, since you wouldn't need to do a secure task-switch.
- mirekrusin 5y ago
  You wouldn't have to preallocate memory. Kernel should know better when it's good time to mark and sweep. Unpinning memory doesn't have to have immediate effects. I don't think sidechannel attacks would be possible, the only task for kernel is to deallocate at some unknown point in time dereferenced memory, which by definition should not be visible from the user space? Maybe a bit far fetched but parts of the kernel (will never happen) or kernel modules (possible) could use it as well?
  - 5y ago

choeger 5y ago

Unfortunately, they didn't follow up on the scanning part. How does that work? Ok, the allocator is obviously cooperating, but how do you get from scanning piece of C++ memory to the class of the object?

sanxiyn 5y ago
All GC objects have GC headers prepended, from which you can lookup the class and how to scan it. https://github.com/v8/v8/blob/master/src/heap/cppgc/heap-object-header.h https://github.com/v8/v8/blob/master/src/heap/cppgc/heap-obj...
Leszek 5y ago
When scanning the stack, you interpret every word as a potential pointer. Then, you ask your GCs allocator "is this pointer's address in one of your pages?". If it isn't, you're done. If it is, then you check if it's the pointer to the start of an object (there's a bitmap of "is object start" for each word on the page). If this passes too, then you effectively reinterpret cast it to a "GC object" base class which is shared for all GC objects, and call the virtual "trace" function from there.
- flohofwoe 5y ago
  Maybe a stupid question, but how would this detect random data byte sequences that accidentally form a valid GC object pointer?
  - sanxiyn 5y ago
    It doesn't. That is what it means for GC to be conservative.
_old_dude_ 5y ago
Here is the related research paper https://duckduckgo.com/?q=Cross-Component+Garbage+Collection https://duckduckgo.com/?q=Cross-Component+Garbage+Collection