shenandoah并发整理不适用传统大o复杂度，而是多阶段工程系统：标记近似o(h)并行摊薄，疏散靠brooks指针将o(p)引用更新降为每次访问o(1)重定向，roots更新stw仅o(r)，停顿恒定≤10ms。
Shenandoah 实现并发整理的算法复杂度，不能简单套用传统“时间/空间复杂度”的大O表达式，因为它本质上是**多阶段、多线程、带屏障开销与停顿约束的工程化系统设计**，而非单一纯计算过程。其复杂度需从三个维度拆解评估：标记阶段、转发指针驱动的并发疏散（evacuation）、以及引用更新机制。
标记阶段：近似线性，并发摊平开销
Shenandoah 使用基于 Region 的并发标记，采用 SATB（Snapshot-At-The-Beginning）快照算法：
- 初始标记（Initial Mark）为 STW，仅扫描 GC Roots，时间复杂度为 O(R)，R 是根集合大小（栈帧、静态变量等），通常极小且与堆无关
- 并发标记遍历整个存活对象图，由多个 GC 线程并行完成；单线程理论为 O(H)（H 为堆中存活对象数），但实际被线程数 T 摊薄，整体工作量仍为 O(H)，而 wall-clock 时间趋近于 O(H/T)
- 无全局遍历压力，不依赖堆总大小，只与活跃对象数量相关
并发疏散与转发指针：空间换时间，访问延迟恒定化
核心创新在于 Brooks 转发指针，它将“移动对象 + 修正所有引用”这一传统 O(P) 操作（P 为所有指向该对象的引用数）分解为：
Codex Auth Cleaner
下载
一款AI工具，主要用于Monitor and clean up invalid Codex authentication files in CPA. Check quota status, disable files returning 401 errors, and perform dual verification before deletion.，适合需要提升相关任务效率的用户。
- 对象移动本身：GC 线程复制对象并原子更新转发指针，单次操作 O(1)；总移动代价为 O(S)，S 是待疏散存活对象数
- 引用重定向：不再批量扫描修正，而是靠读屏障在每次访问时惰性跳转——每次对象读取增加一次指针解引用（+1 indirection），时间开销恒定 O(1)，与堆大小、对象分布完全无关
- 对象头额外占用 8 字节，空间复杂度增加 O(N)（N 为堆中对象总数），属可接受常数级膨胀
引用更新阶段：分层处理，STW 极短可控
Shenandoah 将引用更新拆为两层：
- Roots 更新：最终标记后一次极短 STW，仅处理线程栈、JNI 引用、静态字段等，复杂度 O(R)，通常 sub-millisecond
- 堆内引用批量更新（可选优化）：按物理地址顺序扫描 Region 中的引用字段，将仍指向旧地址的引用改为新地址；虽为 O(P)，但它是并发执行、非必须路径，且不阻塞用户线程
综合来看，Shenandoah 的关键优势不是降低理论复杂度阶数，而是将原本集中在 STW 中的高阶开销（如全堆引用扫描 O(P) 或对象图遍历 O(H)）分散到并发阶段与运行时访问路径中，使最大暂停时间稳定在 10ms 内，且不随堆增大而恶化。它用少量空间开销（+8B/obj）、每次访问微小间接成本（read barrier）、以及更复杂的并发协调逻辑，换取了延迟的强可预测性。
