指针碰撞与空闲列表

1. 指针碰撞（Bump-the-Pointer）

1. 原理

假设堆内存是规整的——所有已使用的对象紧密排列在一端，空闲内存连续在另一端，中间只有一个分界指针（top pointer）作为边界。

分配新对象时：

检查空闲空间是否足够（top + size <= end）。
如果够，直接将 top指针向后移动 size字节。
返回原来的 top地址给新对象。

整个过程就像推土机向前推进，一步到位，没有复杂计算。

初始：
|  已使用对象  |              空闲内存               |
              ↑ top                            ↑ end

分配对象 A 后：
|  已使用对象  |  A  |         空闲内存          |
                   ↑ top                       ↑ end

2. 适用条件

堆内存必须规整（无碎片）。
通常用于复制算法（年轻代）或标记-整理算法（老年代）。

3. 优点

极快：仅一次指针加法，无复杂数据结构操作。
无碎片：分配天然连续，有利于缓存局部性。

4. 缺点

依赖内存规整性，如果堆碎片化则无法使用。
多线程并发分配时需要同步（CAS 或 TLAB）。

5. 哪些收集器用指针碰撞？

收集器	区域	原因
Serial / ParNew	年轻代（Eden + Survivor）	复制算法，内存连续
Parallel Scavenge	年轻代	同上
Parallel Old	老年代	标记-整理，压缩后连续
G1	每个 Region 内部	Region 内部连续，使用 TLAB 分配
ZGC / Shenandoah	每个 Region 内部	类似 G1，Region 内连续

2. 空闲列表（Free List）

1. 原理

当堆内存不规整（存在碎片）时，无法用简单的指针移动来分配。JVM 维护一个空闲块链表，记录所有未被占用的内存块（每个块有起始地址和大小）。

分配新对象时：

遍历空闲列表，找到一个足够大的空闲块。
从该块中切出一段给新对象（如果剩余空间较大，可以分裂成两个小块）。
更新空闲列表（删除原块，添加剩余块）。
回收对象时，将释放的内存块合并回空闲列表（可能需要与相邻空闲块合并，减少碎片）。

空闲列表结构示例：
free_list → [addr=0x100, size=64] → [addr=0x200, size=128] → [addr=0x400, size=32] → NULL

分配一个 40 字节的对象：
找到 [addr=0x200, size=128] 足够大，切出 40 字节给对象，
剩余 [addr=0x228, size=88] 放回列表。

2. 适用条件

堆内存不规整（碎片化）。
通常用于标记-清除算法（如 CMS 的老年代）。

3. 优点

适用于碎片化堆，不需要压缩。
灵活管理任意大小的空闲块。

4. 缺点

慢：需要遍历链表寻找合适块（最坏情况 O(n)）。
碎片化加剧：频繁分配和释放可能导致更多小碎片，最终需要压缩。
额外内存开销：维护链表需要额外空间（指针、大小等）。
缓存不友好：分配的对象可能分散在堆各处，访问性能下降。

5. 哪些收集器用空闲列表？

收集器	区域	原因
CMS	老年代	标记-清除，不压缩，必然碎片化
Serial Old（作为 CMS 后备）	老年代	标记-整理，但整理前也用空闲列表分配
G1	老年代（Humongous 对象）	巨型对象（超过 Region 一半）有时用空闲列表管理

3. 两者对比总结

特性	指针碰撞	空闲列表
前提	内存规整（无碎片）	内存不规整（有碎片）
分配速度	O(1)，极快	O(n)，较慢（尤其碎片多时）
内存碎片	无碎片	产生碎片，需合并或压缩
实现复杂度	简单	复杂（需维护链表、合并分裂）
多线程并发	CAS 或 TLAB 解决	通常加锁（全局链表）
典型收集器	Serial, ParNew, Parallel, G1（年轻代）	CMS, Serial Old（老年代）

4. 结合 JVM 的实际运作

1. TLAB（Thread Local Allocation Buffer）

无论是指针碰撞还是空闲列表，在多线程下都需要同步。为了提升效率，JVM 引入了 TLAB：每个线程在堆中预分配一小块私有空间（在年轻代或 G1 的 Region 内），线程在自己 TLAB 内使用指针碰撞分配对象，无需同步。只有当 TLAB 用尽时，才需要加锁申请新的 TLAB。

年轻代（复制算法）→ TLAB 内指针碰撞。
老年代（CMS 空闲列表）→ TLAB 内也可以用空闲列表？不，TLAB 通常只用于年轻代，老年代分配较少且对象较大，一般不设 TLAB。但 G1 的老年代 Region 内也有 TLAB 机制。

2. G1 的特殊性

G1 虽然是分区式，但每个 Region 内部是连续的，所以在 Region 内分配对象时仍然使用指针碰撞（配合 TLAB）。但对于巨型对象（humongous objects，大小超过 Region 的一半），G1 会直接用一串连续的 Region 来存放，分配时也近似指针碰撞（跨越多个 Region）。