JavaScript标记清除算法详解

发布时间: 2025-03-22 11:32

↑

# JavaScript标记清除算法详解

标记清除(Mark-Sweep)是JavaScript中最常用的垃圾回收算法。本文将深入讲解标记清除算法的工作原理、实现机制和优化策略。

## 算法基本原理

标记清除算法分为两个阶段:

1. 标记阶段: 从根对象开始,递归遍历所有可访问的对象并标记
2. 清除阶段: 遍历整个堆,回收未被标记的对象

## 标记阶段详解

### 1. 根对象识别

在JavaScript中,根对象包括:

- 全局对象(window/global)
- DOM树
- 正在执行的函数的局部变量和参数
- 闭包中的变量

```javascript
// 全局变量作为根对象
window.globalData = {
  value: 'some data'
};

// 函数参数和局部变量作为根对象
function process(data) {
  let temp = { /* ... */ };
  // data和temp都是根对象
}
```

### 2. 可达性分析

```javascript
let user = {
  name: 'John',
  friend: null
};

let admin = {
  name: 'Admin'
};

// user可以从根访问到,被标记
user.friend = admin; // admin也可以通过user访问到,被标记

// 切断引用
user.friend = null; // admin不再可达,将在清除阶段被回收
```

### 3. 标记过程

```javascript
class GarbageCollector {
  constructor() {
    this.marked = new Set();
  }

mark(obj) {
    if (this.marked.has(obj)) return;
    
    this.marked.add(obj);
    
    // 递归标记所有引用
    for (let value of Object.values(obj)) {
      if (typeof value === 'object' && value !== null) {
        this.mark(value);
      }
    }
  }
}
```

## 清除阶段详解

### 1. 内存遍历

```javascript
class GarbageCollector {
  sweep() {
    for (let obj of this.heap) {
      if (!this.marked.has(obj)) {
        this.freeMemory(obj);
      }
    }
    this.marked.clear(); // 重置标记集合
  }

freeMemory(obj) {
    // 释放对象占用的内存
    // 实际由JavaScript引擎实现
  }
}
```

### 2. 内存碎片处理

```javascript
// 内存碎片示例
let arr = new Array(1000000);
for (let i = 0; i < 1000000; i += 2) {
  arr[i] = null; // 产生大量内存碎片
}

// 压缩方案
function compactArray(arr) {
  return arr.filter(item => item !== null);
}
```

## 算法优化策略

### 1. 分代回收

```javascript
// 新生代对象
class YoungGeneration {
  constructor() {
    this.objects = new Set();
    this.age = 0;
  }

promote(obj) {
    if (this.age > 2) {
      // 将对象移动到老年代
      return true;
    }
    return false;
  }
}

// 老年代对象使用标记清除
class OldGeneration {
  collectGarbage() {
    // 标准的标记清除流程
  }
}
```

### 2. 增量标记

```javascript
class IncrementalGC {
  constructor() {
    this.markingQueue = [];
    this.markingInProgress = false;
  }

markIncremental() {
    const MAX_MARKING_TIME = 5; // 毫秒
    const startTime = Date.now();

while (this.markingQueue.length > 0) {
      if (Date.now() - startTime > MAX_MARKING_TIME) {
        // 暂停标记,让出控制权
        setTimeout(() => this.markIncremental(), 0);
        return;
      }

const obj = this.markingQueue.pop();
      this.mark(obj);
    }

// 标记完成,进行清除
    this.sweep();
  }
}
```

### 3. 并发回收

```javascript
class ConcurrentGC {
  constructor() {
    this.worker = new Worker('gc-worker.js');
  }

startCollection() {
    // 在后台线程中执行垃圾回收
    this.worker.postMessage({
      type: 'startGC',
      heap: this.getHeapSnapshot()
    });
  }

handleWorkerMessage(event) {
    if (event.data.type === 'gcComplete') {
      this.applyGCResults(event.data.freedMemory);
    }
  }
}
```

## 性能优化建议

### 1. 对象池复用

```javascript
class ObjectPool {
  constructor() {
    this.pool = [];
  }

acquire() {
    return this.pool.pop() || this.createObject();
  }

release(obj) {
    if (this.pool.length < 100) { // 限制池大小
      this.pool.push(obj);
    }
  }
}
```

### 2. 手动内存管理

```javascript
class ResourceManager {
  constructor() {
    this.resources = new Map();
  }

allocate(key, value) {
    this.resources.set(key, value);
  }

release(key) {
    this.resources.delete(key);
  }

clear() {
    this.resources.clear();
  }
}
```

### 3. 避免内存泄漏

```javascript
class Component {
  constructor() {
    this.data = new Array(1000000);
    this.setupEventListeners();
  }

setupEventListeners() {
    this.handler = () => {
      // 处理事件
    };
    document.addEventListener('click', this.handler);
  }

destroy() {
    // 清理事件监听
    document.removeEventListener('click', this.handler);
    // 清理大数据
    this.data = null;
  }
}
```

## 最佳实践

### 1. 及时释放引用

```javascript
function processData(data) {
  const result = heavyComputation(data);
  
  // 使用完后释放
  data = null;
  
  return result;
}
```

### 2. 使用WeakMap/WeakSet

```javascript
// 使用WeakMap存储元数据
const metadata = new WeakMap();

function addMetadata(obj, data) {
  metadata.set(obj, data);
}

// 当obj不再被引用时,相关的元数据会自动被回收
```

### 3. 控制对象生命周期

```javascript
class Cache {
  constructor() {
    this.cache = new Map();
    this.maxSize = 1000;
  }

set(key, value) {
    if (this.cache.size >= this.maxSize) {
      // 删除最老的项
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    this.cache.set(key, value);
  }
}
```

## 总结

标记清除算法是JavaScript中最基础和重要的垃圾回收算法。通过理解其工作原理,我们可以:

1. 编写更加内存高效的代码
2. 避免常见的内存泄漏问题
3. 优化应用程序的性能
4. 实现更好的内存管理策略

在实际开发中,我们应该结合使用对象池、WeakMap等技术,并遵循最佳实践,以实现最优的内存使用效果。

元素码农