内存管理-堆栈和GC

前言

所有的程序都必须和计算机内存打交道，从计算机申请内存，在不需要的时候释放内存，这是各个编程语言的设计难点。

目前有三种流派的内存管理：

垃圾回收机制（GC）：在运行时不断的寻找需要释放的内存。JavaScript、Java 等等各大主流语言都用的 GC
手动管理内存的分配和释放：所有堆对象的创建和销毁都要由程序员负责。C++
通过所有权进行管理内存：在编译时根据一系列规则进行检查。Rust

为什么要学内存管理？

帮助开发同学更好的理解各种变量创建的过程，应用的性能情况有哪些优化空间，帮助我们开发高性能的应用，尤其是 Node 应用。

内存管理的知识是通用的，你在开发 JS、JAVA、C++、GO 等等各种语言都绕不开它。

栈（Stack）和堆（Heap）

数据结构中的栈和堆

一般我们看到栈和堆就会以为是两个数据结构：

栈是一个后进先出的数据结构，比如 JS 中的函数调用栈、浏览器的网页历史记录

堆是一种特别的完全二叉树的数据结构，还分为最大堆、最小堆，一般适用于优先级队列，比如 React 的 Scheduler

内存中的栈和堆

我们主要是讲 C/C++ 的内存分配。（ V8 引擎是 C++ 实现的，Java 中的 JVM 是汇编、C、C++ 实现的，比较有代表性）

我们这里所说的堆栈是两种内存管理的形式，所以也会叫栈内存（栈区）和堆内存（堆区）。

在 C/C++ 中内存分为 栈区、堆区、全局/静态存储区、常量存储区、代码区。

**静态内存分配：**编译时分配。包括：全局、静态全局、静态局部三种变量。

**动态内存分配：**运行时分配。包括：栈、堆。

栈内存

是由编译器管理的
是线程私有的。
栈中的数据占有大小是已知的。
每个方法在执行时都会创建一个栈帧用于存储局部变量、操作数栈、方法出口等等信息。

哪些是存到栈内存的？：

字符（char）、数值（int）、布尔值、引用指针等等，可以看出来，这些值一旦声明了，它的大小是确定的，编译期就能知道的。

堆内存

是由程序员管理的
所有线程共享的
可动态分配和释放的内存
堆中的数据都是大小不可知，也可能会发生变化。

由此可以看出，我们一般说的内存溢出、GC 等都是指的是堆内存。

哪些是存到堆内存的？：

容器：动态数组（C++ 种的 Vector，JS 中的 Array）、哈希表、JS 中的对象。

从这些可以看出来，这些变量声明后，大小是不确定的，编译器是不可知的。运行时会动态的变大变小。

垃圾回收机制

垃圾回收机制的实现有两种：

引用计数收集器：最早的也是最简单的垃圾回收实现方法。会将存到堆空间的对象

当引用一个对象，计数器就加一，不引用计数器就减一，为 0 时释放空间
- 优点：可以尽快的回收不适用的对象
- 缺点：频繁更新计数会降低效率、循环引用问题等等
跟踪收集器

可达性

内存管理概念是 可达性。“可达”值是那些以某种方式可访问或可用的值。它们一定是存储在内存中的。

这里有个很简单的例子：

// user 具有对这个对象的引用
let user = {
  name: 'John',
};

user 引用了对象 { name: "John" }。随后 user 的值被重写了

user = null;

此时 { name: "John" } “断开了连接”，没有了引用，不可达了，那么就会被当作垃圾数据回收掉。

还有更加复杂的例子，下面这种情况，即使这个对象还引用了别的对象，也会被回收掉。

还有一个是无法到达的岛屿，尽管他们内部有各自的引用，但是始终无法到达，也会被回收。

垃圾回收算法：标记-清除（mark-and-sweep）& 标记-紧缩（mark-and-compact）

V8 将标记-清除和标记-紧缩（标记-整理）两种算法结合使用。

这两个回收算法分为两个阶段，第一阶段的算法都是一样的：

标记（marking） 在托管堆（managed heap）中扫描后的活动对象（live objects）的位置

清除（sweeping） 在托管堆中被回收死亡对象（dead objects）的位置。

但是清除会带来一个问题就是空间不连续，所以需要优化，*紧缩（compacting）*就是用于优化不连续的空间整合到一片连续的空间。

可能有点抽象，我们直接看图说话：

比如现在有这样一个结构的引用关系：

当开始准备垃圾回收时，会暂停整个程序的全部运行的线程（Stop The World, STW）
找到所有的引用的根，并标记，并继续遍历，有点像有向图的广度优先遍历
全部标记完成后，开始清除没有被标记的（不可达的）
然后所有线程恢复运行

这种算法有一个必然的结果，就是每次运行 GC，都会导致整个应用卡顿，那体验也太差了。浏览器引擎对此做了很多优化，使得 GC 速度非常快，感受不到延迟：

分代收集（Generational collection）—— 对象被分成两组：“新的”和“旧的”。在典型的代码中，许多对象的生命周期都很短：它们出现、完成它们的工作并很快死去，因此在这种情况下跟踪新对象并将其从内存中清除是有意义的。那些长期存活的对象会变得“老旧”，并且被检查的频次也会降低。
增量收集（Incremental collection）—— 如果有许多对象，并且我们试图一次遍历并标记整个对象集，则可能需要一些时间，并在执行过程中带来明显的延迟。因此，引擎将现有的整个对象集拆分为多个部分，然后将这些部分逐一清除。这样就会有很多小型的垃圾收集，而不是一个大型的。这需要它们之间有额外的标记来追踪变化，但是这样会带来许多微小的延迟而不是一个大的延迟。
闲时收集（Idle-time collection）—— 垃圾收集器只会在 CPU 空闲时尝试运行，以减少可能对代码执行的影响。

分代收集

V8 将堆分了很多个片区：

新生代：大多数对象被分配在这里，这是一个很小的片区。垃圾回收非常频繁。
老生代：大多数在新生区存活一段时间之后的对象都会被挪到这里。会有一个大周期进行垃圾回收。
大对象区：
... 等等

我们主要理解新老分代。

新生代

这里需要再引出一个算法：Scavenge 算法。

大概是将新生代区分为出区、入区，内存分配发生在出区，出区将要耗尽时（小周期），交换出区入区，将入区的活跃对象复制到出区或者老生代区。

这个算法的速度是比标记-清除和标记-紧缩快的，但是占用的空间比较大（直接需要一半的空间）。所以只适用于区域小的新生代区。

def scavenge():
  swap(fromSpace, toSpace)
  allocationPtr = toSpace.bottom
  scanPtr = toSpace.bottom

  for i = 0..len(roots):
    root = roots[i]
    if inFromSpace(root):
      rootCopy = copyObject(&allocationPtr, root)
      setForwardingAddress(root, rootCopy)
      roots[i] = rootCopy

  while scanPtr < allocationPtr:
    obj = object at scanPtr
    scanPtr += size(obj)
    n = sizeInWords(obj)
    for i = 0..n:
      if isPointer(obj[i]) and not inOldSpace(obj[i]):
        fromNeighbor = obj[i]
        if hasForwardingAddress(fromNeighbor):
          toNeighbor = getForwardingAddress(fromNeighbor)
        else:
          toNeighbor = copyObject(&allocationPtr, fromNeighbor)
          setForwardingAddress(fromNeighbor, toNeighbor)
        obj[i] = toNeighbor

def copyObject(*allocationPtr, object):
  copy = *allocationPtr
  *allocationPtr += size(object)
  memcpy(copy, object, size(object))
  return copy