自己的思维提纲和读书笔记,不详细,推荐自己读GC相关的书
标记阶段
- 标记根直接引用的对象(递归),避免重复标记
- 思想:遍历对象并标记
- DFS,容易压低内存使用
清除阶段
- 遍历对象并回收
- 取消活动对象标记,回收非活动对象
- 所费时间和堆大小成正比
分配
- first fit(比较好用)
- best fit
- worst fit
合并
优缺点
- 优点
- 实现简单
- 与保守式GC算法兼容(对象不能被移动)
- 缺点
- 碎片化
- 分配速度(分块不连续,最坏遍历整个free_list)【BiBOP技术】
- 不兼容COW技术(算法机制导致的频繁设置标志位,以致不必要的复制) 【bitmap】
注:COW技术重写时复制私有空间数据,复制后不再访问共享空间
多个空闲链表
- 改进分配速度
- 思路:创建只链接大分块和只链接小分块的空闲链表
- 实现注意:设定上限,大分块需求极为罕见,不必太在意大分块分配效率,着重考虑小分块
- 算法部分:添加寻找链表序号的部分
BiBOP(Big Bag of Page)
- 把堆分成固定大小的块,让每块只能配置同样大小的对象(比如某一空闲链表均配置2个字大小的块)
- 作用:提高内存使用效率
- 这种方法不能完全消除碎片化,可能会有多个分块中都会有相同大小的碎片(比如两个字大小的内存块中)
位图标记(Bitmap)
- 只收集标志位并利用位图管理管理(不涉及对象,修改时只修改位图中的标志位)
- bitmap可用数组、散列、树等实现,一般一个字分配一个位
- 一般需要obj_num(序号),index(行号),offset(列号)
- 优点
- 与COW技术兼容
- 清除操作更高效
同样遍历堆,同时遍历bitmap,将所有非活动对象回收至free_list之后,将bitmap每位均置0,以达到清除活动对象标志位的效果(没有立即消除标志位)
- Note
此方法利用位运算计算对象对应的标志位,对象地址不连续时,单纯的位运算无法计算对象标志位的位置。因此有多个堆时,一般为每个堆准备一个bitmap。
延迟清除
- 缩减因清除操作而导致的mutator最大暂停时间
- 分配
利用清除(lazy_sweep)操作分配,成功即返回,否则执行一次mark_phase()做标记,继续调用lazy_sweep()分配 - lazy_sweep()
1. 遍历的开始位置位于上一次清除操作中发现分块的右侧($sweeping是全局变量)
2. 延迟清除不遍历整个堆,只在分配时执行必要的遍历,压缩因清除导致的mutator暂停时间 - Note:如果垃圾变成垃圾堆,活动对象变成活动对象堆,会导致延迟清除效果不均衡。遍历至垃圾堆部分获得分块速度较快,遍历至活动对象堆分配变慢。
(这部分后续还会有更详细的相关知识)
网友评论