GC algorithm

GC algorithm is short for garbage collection mechanism, GC can find the garbage in memory, and free, reclaim space

What is considered garbage in GC

  1. Objects that are no longer needed in the program. When the function finishes executing,nameIt is no longer in use and is therefore considered garbage

Such as:

function func(){
name = 'silan'
return `${name} is a coder`
}
func()
Copy the code

2. An object that can no longer be accessed by the program. After executing func(), the name cannot be accessed outside the function and is therefore considered garbage

function func(){
const name = 'silan'
return `${name} is a coder`
}
func()
Copy the code

Common GC algorithm

  1. Reference counting
  2. Mark clear
  3. Tag to sort out
  4. Generational recycling

Reference counting algorithm implementation principle

The core idea is to set the number of references, determine whether the current number of references is zero, through a reference counter, when the reference relationship changes, will change the number of reference counter

A reference change means that you have an object, and when a variable points to it, the reference count increases by one, and so on. Make the reference number zero immediately recycled

Each element in the nameList array is a property of the user1,user2, and user3 objects, so user1,user2, and user3 are all referenced by 1

Num1 and num2 in the fn function body are referenced by 0 because they are not used in the fn function body, but num3 and num4 are mounted on global objects and can be accessed by global objects, so they are referenced by 1

const user1={age:12}
const user2 = {age:13}
const user3={age:14}
const nameList=[user1.age,user2.age,user3.age] // The number of references is 1
function fn(){
 const num1= 1 // Reference number 0  const num2 =2 // Reference number 0  num3=3 // Number of references 1  num4=4 // Number of references 1 } fn() Copy the code

There is an even simpler way. The editor already tells us that NUM1 has been defined but not used, so the reference count is zero

The advantages and disadvantages:

Advantages:

  1. Collect garbage as soon as it is found
  2. Minimize program pauses, and start clearing reference counts when it is found that memory is about to reach a critical point.

Disadvantages:

  1. The time complexity is relatively high
  2. Objects with circular references, such as A.test =b, B.test =a, cannot be reclaimed
  3. High resource consumption

Tag clearing implementation principle

The implementation principle has two phases,

  1. We go through all the active objects and mark them
  2. Iterates through all objects to clear unmarked objects

Finally, recycle the corresponding space

Advantages and disadvantages of tag clearing

Advantages:

  1. You can solve the circular reference problem

Disadvantages:

  1. Garbage objects are not collected immediately. Even if garbage objects are found, they are not cleared until the end of the traversal, resulting in a program stutter

  2. Resulting in space fragmentation, space cannot be used with maximum efficiency

If you look at this graph, assume that neither object A nor object C has A variable reference, so the marker clearing algorithm considers them to be reclaimable space. After reclaiming, there are exactly three domain Spaces, which are allocated the next time the program requests space, but the b object space and the C object space are separated by object A. So when the program requests three Spaces, it finds that both domain Spaces are insufficient and discontinuous.

This is the problem of space fragmentation

Tag sorting algorithm

The tag sorting algorithm can be regarded as the enhancement of the tag clearing algorithm. The process of the tag sorting algorithm is similar to that of the tag clearing algorithm

  1. Walk through all the objects and mark the live objects
  2. Iterate through all the objects, tidy up the space, and move the object according to the mark, so that the address is continuous
  3. Move unless live object, reclaim space

The advantages and disadvantages

Advantages:

  1. Reduce space fragmentation

Disadvantages:

1. Garbage objects are not immediately collected, which is the same problem as flag clearing

V8 Engine Recycling Strategy (generational recycling)

V8 is a mainstream JavaScript execution engine. V8 builds just in time, but with memory limits of 1.5G for 64-bit operating systems and 800MB for 32-bit systems. It is also because of memory limitations that generational recycling is used in the reclamation strategy

In generational collection, the memory is divided into the new generation and the old generation. The small space is used to store the new generation objects. The size varies on different systems (32-bit 32M and 32-bit 16M), and different GC algorithms are used for different objects

Cenozoic objects: Objects that are short-lived, such as local variables

Old generation objects: Objects that are longer lived, such as global-scope variables, and closures

V8 commonly used GC algorithm

  1. Generational recycling
  2. Space to copy
  3. Mark clear
  4. Tag to sort out
  5. Incremental tag

How does V8 recycle next-generation objects

From space is active space, to is free space, and live objects are stored in from space. The two Spaces are equal in size.

Once garbage collection is triggered, the From space is marked up, the live object is copied to the TO space, the From space is freed, and then the space is swapped between From and to, so the original From becomes to, the original TO becomes From, This is the spatial replication algorithm.

It is worth noting that there may be object promotion during the replication algorithm, that is, moving the new generation of objects to the old generation of object storage space. There are two triggering conditions for promotion:

  1. A new generation of objects that survive a round of GC

  2. When the to space usage exceeds 25%, because the copy algorithm is to use the space in the live objects to copy to the space, when the space usage exceeds 25%, to space also exceeds 25%, then there is no room.

How does V8 recycle old generation objects

Old-generation objects are stored in the old-generation object storage area, as shown in the preceding figure. The size varies from system to system, from 1.4g for 62 bits to 700M for 32 bits

When the new generation object is promoted to the old generation storage area, if the space is insufficient, the mark sorting operation will be carried out to optimize the space. Finally, incremental marking is adopted to improve the efficiency

Since garbage collection will block program running, garbage collection and program running are carried out alternately. Instead of marking at one time, incremental marking is carried out during the program running gap, and garbage collection is carried out after the marking is completed. The purpose is to interrupt program running as little as possible and increase efficiency

This article was typeset using MDNICE