V8 implements a generational garbage collector - meaning it has a memory segment called new space for the young generation, and has an old space for the old generation. New objects are allocated in the new space, and if they survive two garbage collections in the new space, they are moved to the old space.
The problem with the two spaces is that moving objects between them is expensive: the objects need to be copied over, and the pointers must be updated. Moving out from the young generation is called evacuation, while adding it to the old generation is called compaction.
Since there are no dependencies between young generation evacuation and old generation compaction, the garbage collector can perform these in parallel, resulting in a reduction of compaction time of 75% from ~7ms to under 2ms on average.
When an object is moved on the heap, the garbage collector has to update all the pointers - but first, it has to find all the pointers to the old location. For this V8 uses a data structure called remembered set to keep track of interesting pointers in the heap. A pointer is classified interesting if the next garbage collector run may move it:
- moving objects from the young generation to the old generation,
- pointers to objects in fragmented pages, as objects may be moved to other pages during compaction
In older versions of V8, remembered sets are implemented using store buffers. This contains addresses of all incoming pointers. The problem is that it may result in duplicated entries, because a store buffer may end up including a pointer multiple times and two store buffers may have the same pointer. This would make parallelization of the pointer update really complex.
Instead of dealing with the extra complexity, Orinoco removes it by reorganizing the remembered set. Instead of the previous approach, now each page stores the offsets of the interesting pointers originating from the given page. With this technique the parallel updates of the pointers become feasible.
It has a huge performance impact - it can reduce the maximum pause time of compacting garbage collection by 40%.
The Black Allocation introduced by Orinoco is involved in the marking phase of the garbage collector. With this, once an object is allocated in the old generation, they are marked black instantly, meaning that they are “live” objects. The goal of this allocation is that objects allocated in the old space are likely to live longer, so they should survive the next garbage collector. Objects colored black are not visited by the garbage collector - they are put on black pages of the old space.
It speeds up the garbage collection due the faster-marking progress as well as less garbage collection work in general.