A flash to the second half of 2020, the blog opened before now has long grass. In spite of my frustration, I still remember the pain, and write a good blog and column.

Today we’ll talk about JavaScript garbage collection

To be clear, unlike languages like C and C++ that require manual memory management, memory management in JavaScript is automatic. This is where the Garbage Collection (GC) algorithm is introduced today. The garbage collection mechanism means that the space in memory that is no longer useful is freed and reused. In order to implement this logic, there must be a standard within the engine to determine whether the memory space is “no longer useful”, and this different standard is a different GC algorithm. There are a variety of GC algorithms in JavaScript implementations, and the most common ones are listed below.

1. Reference counting algorithm

The core idea: set up a reference counter internally, and change the value of the counter when the reference relationship of each object space changes. When the number of references to an object space becomes zero, the garbage collection mechanism is immediately triggered to reclaim the object space.Copy the code

Reference counting algorithms appeared in early implementations and are now rarely used. But we can still learn the idea of this algorithm by studying it. Here’s an example:

	let obj = {name:'zhangsan'} // Zhangsan is referenced once by obj
    let obj2 = obj1 // Zhangsan is referenced for the second time with a counter of 2
    
    obj = null // Remove the reference from obj to Zhangsan, and the reference counter for Zhangsan becomes 1
    obj2 = null // The reference to the zhangsan object becomes 0, and the space in the heap where the zhangsan is stored will be garbage collected
Copy the code

This section describes the advantages and disadvantages of the reference counting algorithm

Advantages:

  1. Since the reference counting algorithm monitors the number of references in the memory space in real time, when the number of references is zero, the memory space can be reclaimed immediately
  2. The reference counting algorithm minimizes program pauses

Disadvantages:

  1. Because the reference counting algorithm maintains a counter, it constantly monitors whether the value needs to be modified, so it is time consuming.
  2. Does not solve the circular reference problem

The so-called circular reference can be illustrated with an example:

	let obj1={value:obj2}
    let obj2={value:obj1}
    // This creates a pair of circular references. Even though obj1 and obj2 represent object Spaces that are not referenced anywhere else,
    // Since they reference each other, the two memory Spaces will not be destroyed either.
Copy the code

2. Mark clearing algorithm

Core idea: The garbage collection process is divided into two phases: marking and cleaning. In the marking phase, all objects are traversed starting from the root object (global object) and all reachable objects are marked. In the cleanup phase, all objects are also iterated, and unmarked objects are cleared.Copy the code

There are two key concepts in this definition: root objects and reachable objects, which are explained in the following order:

  • Root object: Can be considered a global object in JavaScript
  • Reachable objects: Objects that can be accessed through layers of references starting from the root object.

For example, if a variable obj1 is defined on a global object, its internal property value points to another object, obj2, which in turn refers to obj3. All objects on this chain of references, obj1,obj2, and obj3, are reachable objects, whereas if an object cannot be found by reference to the root object, it is unreachable and its memory space is garbage collected.

The advantages and disadvantages of the tag clearing algorithm are described

Advantages:

Objects referenced by a loop can be recycled

Disadvantages:

  1. It is easy to generate fragmented space and waste space
  2. Garbage objects are not collected immediately

3. Mark sorting algorithm

Tag cleaning algorithm is a GC algorithm used in V8 engine. It can be regarded as an upgraded version of tag cleaning algorithm.

The algorithm can be divided into two stages: marking and sorting. The marking stage is the same as the mark clearing algorithm, which marks all reachable objects. In the collation stage, all marked reachable objects are moved in the memory space so that they occupy continuous memory space.

Application: Garbage collection policy in V8

The V8 engine is the javascript execution engine for Chrome and Node. It features high efficiency, instant compilation, and a memory ceiling

  • On 64-bit operating systems: the upper limit is about 1.5 GIGABytes
  • For 32-bit operating systems: the upper limit is about 800 MB

The garbage collection strategy of V8 engine is generational collection

In V8, the memory space is divided into new generation and old generation regions, and different GC algorithms are used for different generations

Among them, the Cenozoic area has a smaller space, 32M on 64-bit operating system and 16M on 32-bit operating system, where objects with short survival time are stored.

V8 divides the new-generation space into two equally large Spaces. The in-use space is called from, and the idle space is called to. When the FROM space usage reaches a certain limit, the garbage collection mechanism is triggered. The V8 generation of recycling is the Scavenge strategy.

New generation object recovery implementation

  1. Mark the phase. Mark active objects (in-use objects) in the FROM space to identify objects waiting to be reclaimed

  1. Sorting stage.

    • Copies an active object from the FROM space to the TO space

    • Free from space completely

  2. Exchange phase. Swap from space and to space to complete the garbage collection operation.

Unlike the new generation regions, the old generation regions store objects that are active for a long time, such as global objects, closures, and so on.

Like the new generation area, the old generation memory area also has size limits and special garbage collection strategies

On 64-bit operating systems, the upper limit for old-generation memory is 1.4 GIGABytes

In 32-bit operating systems, the upper limit of memory generation is 700 MB

The new generation of objects is promoted to the old generation

When an object appears in the to space more than once in the new generation, or when the to space memory exceeds 25%, the object is moved to the old generation space. This practice is called promotion.

By default, programmatically generated objects are first placed in the FROM space. When garbage collection moves objects from from to to, it verifies whether the object has been scinsane by examining its memory location, and if so, moves the object to older space. Next, determine if the to space exceeds 25%, and if so, move the object to the old space.

Old generation object recycling implementation

The Scavenge avenge is the application of the Scavenge avenge, an algorithm that uses space to exchange time, because the Scavenge avenge has relatively small storage space and can lose only a limited amount of storage space even if it is split in half. Compared with this strategy of the new generation, the storage space of the old generation object is larger. Using generational recycling will lose a lot of storage space, which is not worth the loss. In addition, because the old generation memory stores a large number of objects, using this algorithm to copy objects, will greatly reduce the efficiency.

Therefore, garbage collection of old generation memory adopts a different strategy from that of the new generation. Specifically, there are two algorithms: Mark-sweep and Mark-compact. Yes, the two basic algorithms mentioned earlier in the article. Here, we further illustrate the two algorithms with diagrams:

  • Application of mark clearing algorithm in old generation space:

    1. At the beginning, where ABCDEF is used memory

    2. Mark the stage, in which ACE is the active object and the remaining objects are to be cleared3. In the clear phase, space of the object to be cleared is released

    It is easy to see from the above diagram that the memory of the mark clearing algorithm will appear discontinuous state after each clearing. If a large memory needs to be allocated in the old generation space, garbage collection will be triggered in advance because the remaining fragment space is not enough to complete the allocation, and this collection is unnecessary.

    Therefore, on the basis of the tag clearing algorithm, a tag sorting algorithm is developed. The markup algorithm is the same as the clearing algorithm in the marking stage. The difference is that after the active object is marked, it is moved to the other end of heap memory, and then all memory outside the boundary is cleared.

  • Application of mark collation algorithm in old generation space:

    1. Tag phase, consistent with the tag clearing algorithm.

    2. In the declutter phase, the active objects are copied to the other end of the straight heap memory3. In the clearing phase, the memory outside the boundary of the copied object is cleared

  • The combination of tag clearing algorithm and tag sorting algorithm

    In terms of trade-offs, the algorithm is not fast because it needs to move objects. Therefore, the old generation algorithm mainly adopts mark clearing. When the size of objects promoted by the new generation is larger than the available space of the old generation, the mark sorting algorithm is started.

conclusion

That’s all about the JS garbage collection mechanism. In general, there are a variety of GC algorithms in JavaScript. The V8 engine uses the tag scavenging, tag collation, and scavenge algorithm to recycle the new-generation and old-generation memory, respectively.

  • The Cenozoic exploit the scavenge avenge the loss of space to gain advantage in time.

  • The old generation hybrid adopts the algorithm of mark clearing and mark collation to recycle the objects saved in the old generation space.

  • Objects in the new generation space can be promoted to the old generation space if they meet certain conditions.

  • In addition, in the old version of JS engine, also used reference counting algorithm, is no longer used.

Thank you for your help:

Find out the garbage collection of V8 engine by V FE

Let’s talk about V8 garbage collection by Leocoder