自己的思維提綱和讀書筆記，不詳細，推薦自己讀GC相關(guān)的書

標記階段

• 標記根直接引用的對象（遞歸），避免重復(fù)標記
• 思想：遍歷對象并標記
• DFS，容易壓低內(nèi)存使用

清除階段

• 遍歷對象并回收
• 取消活動對象標記，回收非活動對象
• 所費時間和堆大小成正比

分配

• first fit（比較好用）
• best fit
• worst fit

合并

優(yōu)缺點

• 優(yōu)點
  • 實現(xiàn)簡單
  • 與保守式GC算法兼容（對象不能被移動）
• 缺點
  • 碎片化
  • 分配速度（分塊不連續(xù)，最壞遍歷整個free_list）【BiBOP技術(shù)】
  • 不兼容COW技術(shù)（算法機制導(dǎo)致的頻繁設(shè)置標志位，以致不必要的復(fù)制） 【bitmap】

注：COW技術(shù)重寫時復(fù)制私有空間數(shù)據(jù)，復(fù)制后不再訪問共享空間

多個空閑鏈表

• 改進分配速度
• 思路：創(chuàng)建只鏈接大分塊和只鏈接小分塊的空閑鏈表
• 實現(xiàn)注意：設(shè)定上限，大分塊需求極為罕見，不必太在意大分塊分配效率，著重考慮小分塊
• 算法部分：添加尋找鏈表序號的部分

BiBOP(Big Bag of Page)

• 把堆分成固定大小的塊，讓每塊只能配置同樣大小的對象（比如某一空閑鏈表均配置2個字大小的塊）
• 作用：提高內(nèi)存使用效率
• 這種方法不能完全消除碎片化，可能會有多個分塊中都會有相同大小的碎片（比如兩個字大小的內(nèi)存塊中）

位圖標記(Bitmap)

• 只收集標志位并利用位圖管理管理（不涉及對象，修改時只修改位圖中的標志位）
• bitmap可用數(shù)組、散列、樹等實現(xiàn)，一般一個字分配一個位
• 一般需要obj_num(序號)，index(行號)，offset(列號)
• 優(yōu)點
  1. 與COW技術(shù)兼容
  2. 清除操作更高效
     同樣遍歷堆，同時遍歷bitmap，將所有非活動對象回收至free_list之后，將bitmap每位均置0，以達到清除活動對象標志位的效果（沒有立即消除標志位）
• Note
  此方法利用位運算計算對象對應(yīng)的標志位，對象地址不連續(xù)時，單純的位運算無法計算對象標志位的位置。因此有多個堆時，一般為每個堆準備一個bitmap。

延遲清除

• 縮減因清除操作而導(dǎo)致的mutator最大暫停時間
• 分配
  利用清除(lazy_sweep)操作分配，成功即返回，否則執(zhí)行一次mark_phase()做標記，繼續(xù)調(diào)用lazy_sweep()分配
• lazy_sweep()
  1. 遍歷的開始位置位于上一次清除操作中發(fā)現(xiàn)分塊的右側(cè)（$sweeping是全局變量）
  2. 延遲清除不遍歷整個堆，只在分配時執(zhí)行必要的遍歷，壓縮因清除導(dǎo)致的mutator暫停時間
• Note：如果垃圾變成垃圾堆，活動對象變成活動對象堆，會導(dǎo)致延遲清除效果不均衡。遍歷至垃圾堆部分獲得分塊速度較快，遍歷至活動對象堆分配變慢。

（這部分后續(xù)還會有更詳細的相關(guān)知識）