顺德网络营销网站,腾冲网站建设,信誉好的南昌网站建设,网站开发项目概述什么是GC#xff08;Garbage Collection#xff09;#xff1f;
内存管理方式通常分为两种#xff1a;
手动内存管理#xff08;Manual Memory Management#xff09;自动内存管理#xff08;Garbage Collection, GC#xff09;
手动内存管理
手动内存管理是指开发…
什么是GCGarbage Collection
内存管理方式通常分为两种
手动内存管理Manual Memory Management自动内存管理Garbage Collection, GC
手动内存管理
手动内存管理是指开发者直接管理内存的分配和释放。典型的语言如C、C使用malloc/free、new/delete等来手动分配和释放内存。
优点
精确控制内存的分配和释放。可预测的性能没有GC带来的额外开销。不需要的内存可以立即释放从而节省资源。
缺点
存在**内存泄漏Memory Leak**问题。存在**悬挂指针Dangling Pointer**问题。开发复杂度增加。
内存泄漏 分配的内存未被释放导致程序运行期间内存占用持续增加可能导致系统内存耗尽而崩溃。 悬挂指针 已释放的内存被引用时可能会引发不可预测的行为。
近年来Rust通过所有权系统Ownership System提供了一种安全的内存管理方式这并不是完全的手动内存管理而是手动内存管理的一种新替代方案。
GC垃圾回收
GC是编程语言中自动回收不再使用的内存的功能。接下来我们将详细解释这一机制。 自由存储列表Free-Storage List 在任何时刻只有一部分为列表结构预留的内存实际上用于存储S表达式S-expressions。其余的寄存器在我们的系统中大约有15,000个组成了一个称为**自由存储列表free-storage list**的单一列表。程序中的某个特定寄存器FREE包含该列表的第一个寄存器位置。 当需要额外的列表结构时自由存储列表的第一个单词将被使用并且寄存器FREE的值会更新为自由存储列表的第二个单词位置。用户不需要编程将寄存器返回到自由存储列表中。 ——《Recursive Functions of Symbolic Expressions Their Computation by Machine, Part I》John McCarthy GC的概念始于1960年约翰·麦卡锡John McCarthy在其论文《Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I》中介绍了自由存储列表Free-Storage List的概念这是后来GC垃圾回收的基础思想。 为什么需要这个概念
LISPLISt Processor是一种高级语言支持符号处理Symbolic Processing和递归调用Recursion。然而当时的计算机技术难以应对LISP复杂的内存管理问题。LISP在运行过程中不断生成对象未使用的对象垃圾堆积会导致严重的内存泄漏问题。由于程序员很难完全追踪所有的内存分配和释放因此引入了自动内存管理技术。
自由存储列表Free-Storage List是早期LISP系统中实现自动内存管理的基础概念。当时LISP采用动态生成列表结构的方式程序员显式释放内存非常困难。为了解决这个问题引入了跟踪未使用内存块的Free-Storage List概念这最终发展为自动内存管理的思想。其基本原理是使用特定寄存器FREE存储可用内存列表的起始位置按需获取内存并在不再使用时将其返回。这种思想成为了后来Mark-and-Sweep方式GC的基础。 Newell-Shaw-Simon 的列表存储方式的一个重要特点是即使相同的数据多次出现也可以只在计算机内存中存储一次。也就是说列表可以“重叠(overlapped)”。 然而这种重叠会在删除(erasure)过程中引发问题。当不再需要某个列表时必须选择性地删除那些没有与其他列表重叠的部分。在LISP中麦卡锡(McCarthy)提出了一个优雅但低效的解决方案。 本文则描述了一种能够实现高效删除的通用方法。 ——《A Method for Overlapping and Erasure of Lists》 (1963)George E. Collins 尽管约翰·麦卡锡的论文奠定了Mark-and-Sweep方法的基础但在执行GC时会导致程序暂停Stop-the-World现象。这使得实现实时GC变得困难。因此Collins提出了引用计数(Reference Counting)的概念作为GC方法。 该方法通过为每个对象保存一个引用计数(Reference Count)并在引用计数变为0时立即回收内存。
Collins1960年提出的引用计数GC虽然实现了即时内存回收但由于循环引用问题并不是一个完美的解决方案。 尽管如此现代语言如Python和Swift仍然使用这种方法但加入了一些补充技术来解决其缺陷。
顺便提一句“优雅但低效”这样的评价让我觉得有趣。程序员这个职业似乎总有一种特点他们喜欢用“优雅”的方式讽刺对方。也许是因为讨论的是抽象概念缺乏实体暴力的存在感在韩国如果有人这样说话可能会被拳头教训吧。 《A LISP Garbage Collector for Virtual-Memory Computer Systems》论文摘要 本文提出了一种适用于非常大的虚拟内存环境的列表处理系统的垃圾回收算法。 该算法的主要目的不是“释放空闲内存”而是压缩活动内存(compaction) 。 在虚拟内存系统中由于空闲内存实际上并不会耗尽因此很难决定何时触发垃圾回收。因此本文讨论了触发垃圾回收的各种条件。 ——《A LISP Garbage Collector for Virtual-Memory Computer Systems》 (Fenichel Yochelson, 1969) 虚拟内存(Virtual Memory)一种逻辑上管理超出物理内存大小的大容量内存的技术。
这篇论文改进了Minsky的复制式GC(Copying GC)使其能够在虚拟内存环境中高效运行。 本文实际实现了Minsky的垃圾回收器它利用深度优先搜索(DFS, Depth-First Search)将可达数据复制到辅助存储器中分配到新的连续地址后重新加载回内存。尽管有评论认为其实现完成度较低因为稍后会详细解释所以这里不需要完全理解这篇论文是首次将Minsky的方法应用于现代虚拟内存环境中的“Copying GC”如果没有这篇论文Java和C#中的分代GC(Generational GC)概念可能就不会出现。 “提出了一种简单的非递归nonrecursive列表结构压缩方法或垃圾收集器。该算法适用于紧凑compact结构和LISP风格的列表结构。通过逐步利用部分结构来追踪复制的列表从而消除了对递归的依赖。” — C. J. Cheney, 1970 随后使用广度优先搜索BFS, Breadth-First Search而非深度优先搜索DFS设计了一种“非递归Nonrecursive”的GC使其能够在没有栈的情况下运行。 这项研究对Java、C#、Python的Copying GC方式产生了重要影响基于BFS的设计避免了栈溢出问题并具有缓存友好的结构。 为什么BFS可以以非递归的方式实现而DFS不能
首先大多数读者应该知道栈是一种**后进先出LIFO, Last In, First Out的数据结构。最后添加的元素会最先被移除。 队列则是一种 先进先出FIFO, First In, First Out**的数据结构。也就是说最先添加的元素会最先被移除。
DFS的工作原理
DFS采用一种沿着某条路径深入探索到底然后回溯backtracking的方式。为了实现这一点DFS需要使用栈Stack或递归函数Recursive Call。 DFS基于栈的原理如下
将当前节点存储在栈中或通过递归调用。如果有下一个要访问的节点则继续通过栈调用或递归调用进行处理。当没有更多可前进的地方时执行回溯返回上一步。
BFS的工作原理
BFS则是基于队列的原理
将起始节点添加到队列中Enqueue。从队列中取出一个节点Dequeue访问它并将其相邻节点重新添加到队列中。重复上述过程直到访问完所有节点。
由于BFS使用队列因此不需要额外的递归调用。 以洞穴探险为例
DFS
在洞穴探险时DFS会选择一条路一直走到尽头如果路被堵住就会回溯并尝试新的路径。 当路被堵住时必须记住存储返回的路径否则无法回到原点。
BFS
BFS会在洞口布置一支队伍同时探索所有的岔路。先确认第一层的所有路径然后再进入下一层。 为了合理分配队伍必须优先安排最早到达的岔路。 GC的发展历程 年代 研究者 GC算法 改进点 问题 1960 John McCarthy Mark-and-Sweep 首次引入GC概念 Stop-the-World碎片化问题 1963 Marvin L. Minsky Copying GC基于DFS 解决内存碎片化优化缓存 循环引用问题磁盘使用 1969 Fenichel Yochelson Copying GC虚拟内存应用 使用两个半空间Semispaces 内存不足时程序变慢 1970 C. J. Cheney 非递归Copying GC基于BFS 无需栈即可进行GC BFS基础内存重定位优化较少
GC算法发展的意义是什么
通过减少“Stop-the-World”问题并逐步向实时ConcurrentGC发展我们可以看到GC的进步过程。
那么现在让我们总结一下垃圾回收器有哪些算法以及这些算法的概述。
在进入主题之前先简单介绍一些基础知识
我们通常将内存管理分为两个池堆内存和栈内存。栈内存主要用于存储小型短生命周期的数据主要是值类型。堆内存则用于存储更大、更持久的数据主要是引用类型。
GC算法大致可以分为两类 1. Tracing GC追踪型GC
这是最常见的GC类型。 垃圾回收通过可达性Reachability来判断某个对象是否为垃圾。 从根Root如全局变量、栈变量等开始查找可达对象Reachable然后销毁不可达对象Unreachable。 如果没有有效的引用对象会被标记为unreachable并被回收。 常用的算法主要有以下三种附带代码仅为作者学习核心概念实现的伪代码不保证实际运行效果。
1-1. Mark-and-Sweep标记-清除 (ref: Demystifying memory management in modern programming languages | Technorage)
#include iostream
#include vector
#include algorithm// Mark-and-Sweep GC 实现使用原始指针
class Object {
public:bool marked; // GC 标记状态std::vectorObject* children; // 子对象列表Object() : marked(false) {}// 添加子对象的方法void addChild(Object* child) {children.push_back(child);}// 析构函数对象被删除时打印日志用于调试~Object() {std::cout Deleting Object at this std::endl;}
};// 全局堆和根对象容器
std::vectorObject* heap;
std::vectorObject* roots;// 递归标记对象及其子对象
void mark(Object* obj) {if (obj nullptr || obj-marked) {return;}obj-marked true;for (Object* child : obj-children) {mark(child);}
}// 清除阶段删除未标记的对象并从堆中移除
void sweep() {auto it heap.begin();while (it ! heap.end()) {Object* obj *it;if (!obj-marked) {// 释放无法到达的对象delete obj;it heap.erase(it);} else {// 复位标记以便下次 GC 运行obj-marked false;it;}}// 更新根对象列表仅保留仍在堆中的对象std::vectorObject* newRoots;for (Object* root : roots) {if (std::find(heap.begin(), heap.end(), root) ! heap.end()) {newRoots.push_back(root);}}roots newRoots;
}// 执行完整的 GC 过程标记并清除
void gc() {for (Object* root : roots) {mark(root);}sweep();
}int main() {// 创建对象并加入堆中Object* a new Object();Object* b new Object();Object* c new Object();// 设定对象间的引用关系a-addChild(b);b-addChild(c);// 将所有对象加入堆heap.push_back(a);heap.push_back(b);heap.push_back(c);// 设定根对象此处 a 作为根对象roots.push_back(a);std::cout Heap size before GC: heap.size() std::endl;// 执行垃圾回收gc();std::cout Heap size after GC: heap.size() std::endl;// 释放剩余的对象实际系统中最终 GC 运行时会处理for (Object* obj : heap) {delete obj;}heap.clear();roots.clear();return 0;
}如果在代码中使用C的RAII特性并通过shared_ptr管理内存则很难观察到GC的实际操作因此需要使用原始指针。
Mark阶段 识别正在使用的对象。Sweep阶段 删除不可达对象。出现内存碎片化Fragmentation问题。
简而言之从Root Space找到连接的对象并删除未连接的对象。 优点是实现相对简单且能有效保留必要的对象避免浪费内存。 缺点是会出现“Stop-the-World”现象并产生内存碎片化问题。
内存碎片化 当内存单元在堆中分配时其大小取决于存储变量的大小。回收内存时堆内存会分裂成碎片。
内部碎片化 已分配内存块中未使用的空间例如分配4KB但只使用1KB。外部碎片化 可用内存分散无法分配大块内存。 (img ref: Visualizing memory management in V8 Engine (JavaScript, NodeJS, Deno, WebAssembly) | Technorage )
1-2. Mark-Compact标记-整理
在Mark阶段之后将存活对象移动到内存的一侧以进行整理Compaction从而解决碎片化问题。 缺点是整理过程中会产生额外的开销GC时间较长。 #include iostream
#include vector
#include algorithm
#include cstringconstexpr std::size_t HEAP_SIZE 1024;// 对象类 (简单链表结构)
class Object {
public:int value;Object* next;explicit Object(int val) : value(val), next(nullptr) {}// 析构函数 (调试用途)~Object() {std::cout Deleting Object with value value at this std::endl;}
};// 使用两个半空间 (Semispace) 进行内存管理
std::vectorchar fromSpace(HEAP_SIZE);
std::vectorchar toSpace(HEAP_SIZE);std::size_t fromIndex 0;
std::size_t toIndex 0;// 在给定的空间中分配对象 (使用 placement new)
Object* allocate(int val, std::vectorchar space, std::size_t idx) {if (idx sizeof(Object) space.size()) {return nullptr; // 空间不足}Object* obj new (space[idx]) Object(val);idx sizeof(Object);return obj;
}// 递归复制对象及其链接
Object* copy(Object* obj, std::vectorchar targetSpace, std::size_t targetIdx) {if (obj nullptr) {return nullptr;}Object* newObj allocate(obj-value, targetSpace, targetIdx);if (newObj nullptr) {return nullptr;}newObj-next copy(obj-next, targetSpace, targetIdx);return newObj;
}// 复制垃圾回收 (Copying GC) - 复制所有可达对象到新的空间
void gc(Object* root) {toIndex 0;Object* newRoot copy(root, toSpace, toIndex);// 交换空间使新分配的空间成为新的堆std::swap(fromSpace, toSpace);fromIndex toIndex;root newRoot;
}int main() {// 在 fromSpace 中分配对象Object* a allocate(10, fromSpace, fromIndex);if (a nullptr) {std::cerr Allocation failed for object a. std::endl;return 1;}Object* b allocate(20, fromSpace, fromIndex);if (b nullptr) {std::cerr Allocation failed for object b. std::endl;return 1;}a-next b;std::cout Before GC, root object value: a-value std::endl;// 运行 GCgc(a);std::cout After GC, copied root object value: a-value std::endl;return 0;
}1-3. Copying GC复制型GC
将内存分为两个半空间Semi-Space分别称为From-Space和To-Space。 仅将可达对象复制到新空间To-Space然后销毁旧空间。 优点是没有内存碎片化分配速度快缺点是内存使用效率低仅使用一半的内存。
2. Reference Counting引用计数
#include iostream
#include unordered_map// 对象类存储简单整数值
class Object {
public:int value;explicit Object(int val) : value(val) {}// 析构函数: 当对象被释放时打印日志~Object() {std::cout Deleting Object with value value at this std::endl;}
};// 全局引用计数表
std::unordered_mapObject*, int refTable;// 创建对象并初始化其引用计数
Object* createObject(int val) {Object* obj new Object(val);refTable[obj] 1;return obj;
}// 增加对象的引用计数
void addRef(Object* obj) {if (obj ! nullptr) {auto it refTable.find(obj);if (it ! refTable.end()) {(it-second);}}
}// 释放对象的引用当引用计数为0时删除对象
void releaseRef(Object* obj) {if (obj ! nullptr) {auto it refTable.find(obj);if (it ! refTable.end()) {if (--(it-second) 0) {refTable.erase(it);delete obj;}}}
}int main() {// 创建对象Object* a createObject(10);Object* b createObject(20);// 增加 b 的引用计数 (模拟多个地方使用)addRef(b);// 释放 b 的引用两次调用后计数变为0对象被释放releaseRef(b);releaseRef(b);// 释放 areleaseRef(a);std::cout Remaining objects in refTable: refTable.size() std::endl;return 0;
}使用全局引用表unordered_map在创建对象时将引用计数初始化为1并通过addRef和releaseRef调整引用计数。当引用计数为0时调用delete。
每个对象存储一个引用计数Reference Count当引用计数为0时立即释放内存。 由于可以立即释放内存因此没有“Stop-the-World”现象且对象的使用量清晰可见。 缺点是存在循环引用问题并且在处理大型对象时性能下降。 Swift中使用了改进版的ARCAutomatic Reference Counting。
核心总结 分类 Tracing GC (Mark Sweep) Reference Counting GC 基本概念 从根开始追踪并清理对象 根据对象的引用计数释放内存 内存泄漏可能性 可能存在循环引用GC自动解决 循环引用导致内存泄漏 GC执行成本 与对象数量和引用图大小成正比 对象越多计算负担越大 性能 对象越多性能越可能下降 引用计数立即归零时快速释放 Stop-the-World(STW) GC执行时暂停 立即释放无需暂停 典型应用场景 C#, Java, Python Objective-C (ARC), Swift 此外除了基本的GC算法外还有一些优化策略。 GC优化策略有哪些
最常见的是Generational GC分代GC 。
1. Generational GC分代GC
根据对象的生存周期将其分为Young Generation和Old Generation并对新生代Young快速GC对老年代Old缓慢GC。 接下来我们看看Young和Old是如何划分的。
1-1. Young GenerationEden Survivor Space
Eden伊甸园区域 新创建的对象首先分配到这里。大多数对象在这里生成后很快就会被销毁因此GC频繁发生。Survivor幸存者区域 Eden区域中经过GC后存活的对象会移动到这里。通常有两个Survivor区域。对象多次经历GC后最终晋升到Old Generation。 Survivor区域通常分为两个Survivor0From Space和Survivor1To Space。 在这里新创建的对象存储在此大部分对象会快速销毁。此区域使用Copying GC快速移除对象。 当该区域中的对象被移除时称为Minor GC。
1-2. Old Generation老年代
Tenured老年区域 多次在Young Generation中经历GC后存活的对象会移动到这里。 此区域GC较少发生但一旦发生涉及的对象较多处理成本较高。 老年代对象存储在这里使用Mark-Sweep或Mark-Compact方式进行清理。 利用对象生命周期模式进行性能优化。当此区域中的对象被移除时称为Major GC或Full GC。 Young GC快速执行Old GC较慢执行但在Old Generation中发生GC时可能会出现“Stop-the-World”。
通常Old区域分配较大因此GC发生的频率低于Young区域。
可以用人类一生的例子来说明
在Eden伊甸园中以灵魂状态存在接受世界的召唤出生经历世间的风雨洗礼Survivor无事故地幸存下来成为老人获得社会尊重Promotion受人尊敬的老人去世后社会上更多的人哀悼比年轻人更大的哀悼成本。 2. Parallel GC并行GC
使用多个线程Thread并行执行GC提升GC速度。适用于大型应用程序但可能存在线程同步开销。Java HotSpot JVM实现了Parallel GC。 需要注意的是分代GC和并行GC并不互斥因此可以同时使用实际上JVM HotSpot和.NET中也确实如此。 (Time Freeze!!!)
那么GC是如何执行的呢
1. Stop-the-WorldSTW
GC执行时程序完全停止。 这是传统的GC方式实现相对简单能够准确回收内存。 但会导致响应时间增加用户体验下降。 (img ref:An attempt at visualizing the Go GC)
2. Incremental GC增量GC
将GC分成多个小步骤Small Steps执行基于Dijkstra的三色标记算法Tri-Color Marking Algorithm。
这个算法的核心是高效地标记三种颜色
白色 未处理Unprocessed灰色 处理中Processing黑色 已处理Processed
节点着色的规则如下
所有节点初始为白色。访问对象时标记为灰色。访问完成后标记为黑色。
这样就形成了三个集合对象从白色→灰色→黑色移动。重要的是白色和黑色之间不会直接连接。
3. Concurrent GC并发GC
GC与应用程序同时运行尽量减少“Stop-the-World”时间。 GC线程独立运行并与其他应用程序线程同时进行内存标记mark或复制等操作。 这使得GC执行期间应用程序仍能运行并利用多核优势但内存管理变得更加复杂。 “过早优化是万恶之源。”——Donald Knuth 本文介绍了GC的历史、当前使用的GC算法、优化策略及执行方法。后续还提到了避免GC的ZoCZero Allocation等内容但由于本文面向初学者部分内容如某些优化策略被省略了。
喜欢手动管理内存的人可能会将GC视为罪恶认为它增加了编程的不确定性。 但正如Donald Knuth所说与其沉迷于内存管理这样的“过早优化”不如让GC帮助开发者专注于解决问题。 程序员的角色不仅是掌握技术更是解决眼前的问题。 GC为许多程序员减轻了“内存管理”的负担是一项重要的工具。
重要的是不是“GC好还是不好”而是思考“哪种工具最适合解决我的问题”。
