directory

  • GC related concepts
  • Common GC Algorithms

  • Reference counting algorithm

    • core idea
    • Realize the principle of
    • The instance
    • The advantages and disadvantages

  • Tag scavenging algorithm

    • core idea
    • Realize the principle of
    • graphic
    • The advantages and disadvantages

  • Tag collation algorithm

    • core idea
    • Realize the principle of
    • graphic
    • The advantages and disadvantages

GC related concepts

  • [X] GC: Short for Garbage Collection Mechanism, Garbage Collection Period to complete specific work. You can find garbage in memory, free and reclaim space
  • [x] GC garbage: Objects in a program that are no longer needed and that can no longer be accessed by the program
  • [X] GC algorithm: The rules that GC looks up and collects as it works

Common GC Algorithms

  • Reference counting
  • Mark clear
  • Tag to sort out
  • Divided to be recycled (used for V8)

Reference counting algorithm

core idea

Set the number of references to determine whether the current number of references is 0 to determine whether it is garbage object, if 0, GC will work, for recycling.

Realize the principle of

  • Reference counter
  • Modify the reference number when the reference relationship changes
  • The quoted number is0Recall immediately when

The instance

const user1 = { age: 11 }
const user2 = { age: 12 }
const user3 = { age: 13 }
const nameList = [user1.age, user2.age, user3.age]

function fn() {
  const num1 = 1
  const num2 = 2
  num3 = 3
}

fn()

When the function is called,
num1and
num2Cannot be used externally. Number of references is
0, will be recycled;


num3Is mounted on
windowOn, so it won’t be recycled;


The above
user1,
user2,
user3be
nameListReference, so the number of references is not
0It won’t be recycled;

The advantages and disadvantages

Reference counting algorithm content
advantages <br/> <br/> <br/> <br/> <br/> <br/>
disadvantages <br/> > <br/> > <br/> > <br/> > <br/> > <br/> > <br/> > <br/> > <br/> > <br/> >

An example of the above shortcoming is the inability to recycle application objects:

function fn() { const obj1 = {} const obj2 = {} obj1.name = obj2 obj2.name = obj1 return 'hello world' } fn() // Obj1 and obj2, because they have references to each other, so the counter is not zero, and the fn call will not be able to reclaim the two objects

Tag scavenging algorithm

Compared to the principle of implementation is more simple, but also to solve the corresponding problems, V8 will be used a lot.

core idea

The two stages are marked and cleared

Realize the principle of

  • Stage 1: Iterate through all objects to find live objects (reachable objects)tag(Hierarchies are operated recursively)
  • Stage 2: iterate through more objectsremoveNo mark object and erase the mark of the first stage mark
  • Recycle the corresponding space and add the reclaimed space toFree listIn, convenient application behind the program space use

graphic

The advantages and disadvantages

Tag scavenging algorithm content
advantages In contrast to the reference-counting algorithm, which solves the problem of object circular references, the contents of the local scope cannot be marked, so even if there is a reference, it will be cleared
disadvantages <br/> <br/> <br/> <br/> <br/> Garbage objects are not collected immediately. The program stops working when it is cleared.

The following is the spatial linked list address discontinuous diagram, can better help us understand:

The left side is released
2The space of the word, which is later released
1A word of space, though, seems to be released
3The space of a word, but the address is discontinuous. If you want to apply for one
1.5Word space, using left space is wasted
0.5, when the right side is not enough, will cause the maximum use.

Tag collation algorithm

This algorithm is also widely used in V8 in conjunction with the tag removal algorithm.

core idea

Between mark and clear, a collation of memory space is added

Realize the principle of

  • Tag cleansing can be considered an enhancement of tag cleansing
  • Marking phase: Consistent with tag cleanup
  • Cleanup phase: Clear money first performs the cleanup, moves the object position, and produces a continuum on the address
  • Cleanup phase: Consistent with tag cleanup

graphic

There will be a lot of live objects and inactive objects to start with, and some free space to start tidying up before recycling

Inactive objects should be cleared after collation

And you end up with the whole free space

The advantages and disadvantages

Tag collation algorithm content
advantages Compared with the tag purging algorithm, the fragmentation space is reduced
disadvantages Garbage objects are not collected immediately. The program stops working when it is cleared.