preface

This article is the seventh chapter of the V8 engine detailed explanation series, focusing on the V8 garbage collection mechanism, and V8 optimization strategy for garbage collection, this article first needs to have a preliminary understanding of the memory structure, do not understand can first look at the V8 engine detailed explanation (six) – memory structure. There will be links to the finished series at the end of this article, which is still being updated.

The garbage collection

We first introduce the simple concept of garbage collection, such as the V8 engine encountered in the process of executing code a function, then we will create a function performs the context and added to the top of the call stack, inside the scope of the function contains all variables in the function of information, we allocate memory to create these variables in the process of execution, The function scope is destroyed when the function is finished executing, so the variables in the scope are no longer useful, and the process of destroying them to reclaim memory is called garbage collection.

The garbage collection process is done automatically by the V8 engine, and v8 does it pretty well in most cases, but as a program, there are only so many cases where it can help us cover, so if we don’t code carefully enough, it can cause a memory leak.

One feature of the javascript language is known to all is a single-threaded, single thread means that the execution of the code is executed in sequence and at the same time also can only handle one task, so V8 in recycling mission, other tasks will be in a wait state, until the end of the garbage collection task to perform other tasks, There are a number of optimizations V8 has made to reduce the impact that garbage collection can inevitably have on the user experience if it takes too long. Let’s take a look at how V8 does garbage collection and how it is optimized.

Garbage collector

The Generational Hypothesis is an important term in garbage collection, and V8’s garbage collection strategies are based on it. The intergenerational hypothesis is also very simple and has two main characteristics:

  • Most objects live in memory for a short period of time. Simply put, many objects become inaccessible quickly once memory is allocated.
  • The undead live longer.

Based on this hypothesis, V8 divides the heap into new generation and old generation regions and designs two garbage collectors:

  • The sub-garbage collector is responsible for garbage collection in the new generation area
  • The main garbage collector is responsible for garbage collection in the old generation area

(Cenozoic and old generation have been introduced in the author’s previous article, if you do not know, you can read the previous article)

Abcs (Freets)

The subgarbage collector is used to collect garbage from the new generation. Usually, newly created objects are allocated to the memory of the new generation first. The new generation of memory area will be divided into two parts (space), from space and to space. These two areas are the same in nature, both have two working states and idle states, and when one is working, the other must be idle state.

Let’s say we create a new object:

  • Allocations are made to the new generation in the heap, and if from SPCAE in the new generation is working, objects are allocated to from space.
  • After the program runs for some time, the memory of from space is about to reach the maximum storage limit.
  • The V8 engine performs a garbage cleanup operation at this point, marking objects that are no longer used in from Space (objects that the root node cannot traverse).
  • The unmarked objects will be copied to the idle state of to space and rearranged in an orderly manner. Then the from space will be emptied and marked as idle state and to space as working state.

The above is the so-called displacement process, which can also be said to be the flipping process. Because this kind of replication operation requires time cost, the space of the new generation is often not large, so it is carried out more frequently.

In order to solve this problem, V8 uses the promotion mechanism to store objects that meet the requirements in the old generation memory area, freeing up space in the new generation memory area.

Conditions of promotion mechanism:

  • An object that has been subjected to an INVERSION, and has not been marked clean, is an object that has been subjected to an inversion.
  • When a rollover is performed, the objects copied are greater than 25% of the to space space. (From space must be the same size as to space)

Promoted objects are allocated to the old generation memory area and are managed by the old generation memory area.

Main Garbage Collector (Mark-Sweep & Mark-Compact)

The main garbage collector is mainly used to collect old generation garbage. Usually, objects promoted in the new generation and those that occupy a large initial space are stored in the old generation memory area.

The main garbage collector takes a completely different approach from the secondary garbage collector, which first collects garbage using a Mark-sweep algorithm.

To quote teacher Li Bing’s description:

The first is to mark the process phase. The marking phase is to start from a set of root elements and recursively traverse this set of root elements. In this traversal process, the elements that can be reached are called active objects, and the elements that cannot be reached can be judged as junk data.

Next comes the garbage removal process. It is completely different from the garbage removal process of the secondary garbage collector, where the main garbage collector directly cleans up the data marked as garbage.

Time.geekbang.org/column/arti…


However, when we clean up memory in this way, a large number of discrete memory fragments will be generated. When we want to store a large object, we may not have enough space. Therefore, in addition to implementing mark-sweep algorithm, Garbage collection is also done through a mark-compact algorithm.

The Mark-compact algorithm is also divided into two steps:

  • The first is also the marking process.
  • Move unmarked objects (live objects) to the left, cleaning up memory outside the boundary when the move is complete.

V8 uses mark-sweep and mark-compact algorithms to collect old memory areas, and this is where the main garbage collector does its job.

Garbage Collection Optimization Strategy (Orinoco)

The approach taken by V8’s two garbage collectors described above is actually quite common in programming languages with garbage collection mechanisms. An important measure of how good a garbage collection mechanism is is the amount of time that the main thread hangs when performing garbage collection, and V8 has optimised this part of the experience by launching a garbage collector project codename Orinoco to optimise the garbage collection strategy.

Orinoco has achieved three optimizations

  • Parallel garbage Collection
  • Incremental garbage collection
  • Concurrent garbage collection

Parallel garbage collection

The first one is optimized for parallel garbage collection. We talked about the new generation and the old generation and based on the garbage collection mechanism we talked about, we can determine that the objects in the new generation are completely different from the objects in the old generation, There is no dependency between the new generation performing mark -> copy -> clean operations and the old generation performing mark -> clean -> compact operations. Orinoco then decided to optimise the non-dependent garbage collection logic (more than one of the above) by executing it in parallel to reduce the time it takes to perform garbage collection in the main process. So Orinoco only needs to start a few helper processes to clean up the garbage at the same time:

(Photo credit: v8.dev/blog/trash-…)

Incremental garbage collection

The second optimization is incremental garbage collection. Although the parallel mechanism of parallel garbage collection can effectively reduce the footprint of the main process, it takes a long time for a large object to be marked at a time. Since 2011, V8 has introduced incremental tagging, also known as incremental garbage collection.

V8. Dev/blog/trash -…

Breaking up a large task into smaller chunks allows applications to run between the chunks. This optimization brings great challenges to the implementation of the tag. How to save the scan results at that time? How to deal with marked data if it is modified by the main thread?

V8 then uses tag bits and tag worksheets to implement tags. The marker bit is used to mark three colors: white (00), gray (10), black (11),

  • In the initial state all objects are white that is, objects that are not referenced by the root node.
  • When the garbage collector finds that an object is referenced, it grays the object and pushes it into the tag worksheet.
  • The tag worksheet accesses all gray objects that have themselves, accesses all children of that object, and marks the object black when it is done.
  • The mark worksheet is continuously injected with grey objects (every new object to mark is injected into the mark worksheet)
  • If there are no gray objects in the mark sheet, then all objects are black or white, and you can safely clean up the white objects later.

The whole process is shown as follows:

Start the tag at the root node

Traverse processing

The final form after completion

If this process is a little convoluted, let me give you an example.

Like a gang of thieves

  • The police caught A of the gang of thieves (marked gray), but the police could not convict him but handed him over to the court (marked worksheet).
  • In the court, A gave up the gang member B, and the police captured the criminal gang member B (marked in gray) and handed him over to the court (marked worksheet).
  • B says the gang also has a C, but C is guilty of no crime (the default mark is white).
  • At this point, the case is closed, and then B is convicted (marked black) and then A is convicted (marked black) and then A is sentenced.

So back to the previous question, if the marked data is modified by the main thread, what is the correct processing? V8 uses a fairly straightforward write-barrier mechanism to enforce that black objects cannot point directly to white objects. Let’s say we perform a write operation:

// after calling 'object.field = value' write_barrier(object, field_offset, value) {if(color(object) == black && color(value) == white) { set_color(value, grey); marking_worklist.push(value); }}Copy the code

By changing the newly written object from its original white to gray, the markup worksheet is not empty, and the markup process continues, ensuring the correct markup data.

Concurrent garbage collection

Concurrent garbage collection and parallel garbage collection are completely different as illustrated by a graph

Parallel garbage collection occurs on the main thread and the worker thread. The application pauses for the entire parallel marking phase. Concurrent garbage collection occurs primarily on worker threads. The application can continue to run while concurrent garbage collection is in progress.

Generally, the above three methods do not exist alone, but are used together as shown in the following figure:

Garbage collection when idle

Idle garbage collection is not part of the Orinoco project and is an optimization strategy implemented by V8. In general, the scheduler uses its knowledge of task queue occupancy, as well as signals received from other components of V8, to estimate when V8 is idle and for how long it is likely to remain idle. Using this information, V8 can assign low-priority garbage collection tasks to do during this idle time.

V8, for example, uses Chrome’s Task Scheduler to dynamically reprioritize tasks based on signals received from various other Chrome components and various heuristics designed to estimate user intentions. For example, if the user touches the screen, the scheduler prioritizes screen rendering and input tasks for a 100-millisecond period to ensure that the user interface remains responsive when the user interacts with the Web page.

For example, if you render at 60 FPS, the interval between frames is 16.6 ms. If there are no valid updates on the screen, the Task Scheduler starts a longer idle period that lasts until the next pending task is started, capped at 50 milliseconds, to ensure Chrome remains responsive to unexpected user input.

A more detailed description of idle tasks can be found at queue.acm.org/detail.cfm?… There is not much more to be said about this article.

conclusion

In this paper, we know the V8 garbage collection mechanism and some optimization methods, the garbage collection mechanism is relatively simple, but the Orinoco optimization method is relatively difficult to understand, the author has not fully understand how concurrent garbage collection do so without further written, understand clearly behind will update), if there are any errors, Please discuss it with the author in the comments and give a thumbs up if you found this article helpful. Thank you very much.

Refer to the article

Queue.acm.org/detail.cfm?… Time.geekbang.org/column/arti… V8. Dev/blog/concur… V8. Js. Cn/blog/orinoc…

series

V8 Engine Details (1) — Overview V8 engine details (2) — AST V8 engine details (3) — Bytecode evolution V8 engine details (4) — Bytecode execution V8 engine details (5) — Inline caching V8 engine details (6) — Memory structure V8 engine details (7) – Garbage collection mechanism V8 engine details (8) – message queue V8 engine details (9) – coroutines & generator functions