Mark and Sweep Algorithm ใน JavaScript Garbage Collection

Mark and Sweep Algorithm

อัลกอริทึม GC หลักใน JavaScript สมัยใหม่ ค้นหา Object ที่ Unreachable (เข้าถึงไม่ได้) แทนที่จะหา "ไม่ได้ใช้แล้ว" ปรับปรุงจาก Reference Counting

3 ขั้นตอนหลัก

1. Root: Global Object (Window ใน Browser, Global ใน Node.js) เริ่มต้นจาก Root หา Object ที่ Reachable
2. Mark Phase: Traversal จาก Root ทุกเส้นทาง Object ที่ถึงได้ = Marked (Reachable) Object ที่ถึงไม่ได้ = Unmarked (Unreachable)
3. Sweep Phase: ลบ Object ที่ Unmarked ทั้งหมด (Garbage Collection)

Mark Phase ตัวอย่าง

// Example 1: Reachable
var obj1 = { prop1: 'hello' }; // Marked (Root → obj1 → prop1)

// Example 2: Become Unreachable
obj1 = null; // null Marked, 'hello' Unmarked → จะถูก Sweep

Sweep Phase

Object ที่ Unmarked (Unreachable) จะถูกลบออกจาก Memory

แก้ปัญหา Circular Reference

function f() {
  var obj1 = {};
  var obj2 = {};
  obj1.p = obj2; // obj1 → obj2
  obj2.p = obj1; // obj2 → obj1 (Cycle!)
}
f(); // ทั้งคู่ Unreachable จาก Root → ทั้งคู่ถูก GC ได้!

Reference Counting ไม่ทำได้ เพราะ Ref Count = 1 ทั้งคู่ แต่ Mark-Sweep ทำได้ เพราะไม่ Reachable จาก Root

ข้อจำกัด

• ไม่สามารถ Trigger GC ด้วยตนเองได้ (Non-deterministic)
• Pause Time (Stop-the-world) ในการ Mark/Sweep
• Memory Fragmentation

Generational GC (Modern Engines: V8, SpiderMonkey)

• Young Generation: Object ใหม่ GC บ่อย (Scavenge - Fast)
• Old Generation: Object ที่รอดชีวมาหลายรอบ GC น้อย (Mark-Sweep-Compact - Slow)