Concurrent and Parallel GC in Chromium's Orinoco

This article provides a technical breakdown of how the Orinoco garbage collector within Chromium's V8 JavaScript engine performs concurrent and parallel memory reclamation. By shifting workloads off the main execution thread, Orinoco significantly reduces "stop-the-world" pause times that cause web applications to stutter. The following sections detail the difference between parallel and concurrent operations in V8, followed by the exact mechanisms Orinoco uses to clean up both the young and old memory generations.

Parallel vs. Concurrent Garbage Collection

To understand Orinoco, it is necessary to distinguish between parallel and concurrent tasks within the V8 engine:

  • Parallel Garbage Collection: The main thread stops executing JavaScript and works alongside multiple background helper threads to perform garbage collection. While this is still a "stop-the-world" pause, the total pause time is drastically reduced because the workload is divided among several CPU cores.
  • Concurrent Garbage Collection: The main thread continues executing JavaScript without interruption while background helper threads perform garbage collection tasks simultaneously. This is the most complex method because the JavaScript application is actively changing the memory graph while the collector is trying to read it.

The Generational Heap Architecture

Orinoco divides the memory heap into two areas based on the generational hypothesis, which states that most objects die young:

  1. The Young Generation: Where new objects are allocated. It is small and collected frequently.
  2. The Old Generation: Where objects that survive the young generation are promoted. It is large and collected less frequently.

Orinoco uses two different collectors optimized for these generations, utilizing parallel and concurrent techniques differently in each.

Parallel Scavenging in the Young Generation

Memory reclamation in the young generation is handled by a collector called the Scavenger. The Scavenger uses a semi-space strategy, dividing the young generation into two halves: "From-Space" and "To-Space".

Orinoco performs scavenging in parallel. When the From-Space is full, JavaScript execution pauses. The main thread and several worker threads immediately begin scanning the root pointers to find live objects.

The threads copy surviving objects into the contiguous To-Space (or promote them to the Old Generation if they have survived a previous scavenge) and update the pointers to these objects. Because memory allocation during this copying phase could cause threads to clash, each worker thread is given its own local allocation buffer. If one thread finishes its assigned objects early, Orinoco utilizes a work-stealing algorithm, allowing idle threads to take tasks from busy threads. Once all live objects are moved, the From-Space is wiped clean instantly, and JavaScript resumes.

Concurrent and Parallel Reclamation in the Old Generation

The Old Generation is managed by the Major GC, which uses a Mark-Sweep-Compact algorithm. Because the Old Generation can hold hundreds of megabytes of data, pausing the main thread to clean it would freeze the browser. Orinoco solves this by mixing concurrent and parallel phases.

1. Concurrent Marking

Marking is the process of finding all reachable (live) objects. Orinoco does the vast majority of this work concurrently. While the main thread runs JavaScript, background threads traverse the object graph and mark live objects using a tri-color marking system (white for unvisited, grey for discovered, black for visited).

Because JavaScript is actively running, it might create a new reference from a "black" object to a "white" object, which the background threads would miss, leading to the accidental deletion of a live object. Orinoco prevents this using a Write Barrier. Every time JavaScript mutates an object reference, a tiny piece of code (the write barrier) intercepts the change and records the modified object into a shared buffer. The background threads periodically empty this buffer to ensure no live objects are missed.

2. Parallel Compaction

Once the concurrent marking phase is nearly complete, the main thread briefly pauses JavaScript to finalize the scan of the root pointers. Immediately during this pause, Orinoco transitions into parallel compaction.

Over time, deleting dead objects leaves memory pages fragmented, like Swiss cheese. To fix this, the main thread and worker threads work in parallel to evacuate live objects from highly fragmented pages into free spaces on other pages. Moving objects means their memory addresses change, so the threads also work in parallel to update every pointer in the application to reflect the new addresses.

3. Concurrent Sweeping

For memory pages that are not heavily fragmented, moving objects is inefficient. Instead, Orinoco uses concurrent sweeping.

Once parallel compaction is finished, the main thread resumes executing JavaScript immediately. In the background, helper threads sweep through the remaining pages, identifying the memory addresses of dead objects (those not marked during the marking phase). The threads add these dead memory ranges back to "free-lists." When the application needs to allocate new memory in the future, it simply checks the free-list for an appropriately sized gap.