V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zhigewuwang
V2EX  ›  算法

确定性唯一强引用链 gc 算法。 这算法成立吗?

  •  
  •   zhigewuwang · 89 天前 · 325 次点击
    这是一个创建于 89 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有可能成立的新 GC 算法,欢迎大家讨论

    每个值,记录引用与被引用关系。 被引用关系中,只有一个是强引用,其他全是弱引用。 由值的引用关系图中,对于一个值,有且只有一种强引用链直通到根。

    值引用图

    其中直线是强引用,虚线是弱引用

    当弱引用断掉后,不需要做处理。 当强引用断掉后, 将该引用链后段的所有强引用全部置为弱引用,并将涉及到的值都记录起来, 记为 tmp_values

    此时 tmp_values 中的所有值都只存在弱引用关系。 如下图所示( A->C 的引用断掉):

    A->C 的引用断掉,该引用链后段所有的强引用全部置为弱引用

    遍历 tmp_values,寻找被引用关系的上级,该上级带有强引用, 如果没有找到,就跳过。 如果有找到,就更新该被引用关系为强引用。

    再次遍历 tmp_values 如果当前 tmp_value 带有强引用, 则从它出发的所有只有弱引用的值,都将引用更新为强引用。如下图所示,绿色的强引用是重新寻找到的强引用:

    image.png

    再次遍历 tmp_values 删除所有未带有强引用的值,如下图所示:

    唯一强引用链重建,只有弱引用的 C 、G 、D 都将被删除

    gc 完成。

    比喻

    每个人在一家公司里都要站队,如果上司倒了,就重新站队(要被使用),重新站队后,你下属的链就保全了。
    没能重新站队的人,就被 fire 了

    优势

    • 引用关系掉后,垃圾数据立刻被清掉,没有 mark-and-sweap gc 算法的延迟。
    • 因为是立即清掉垃圾数据,所以内存也不会被无效数据占掉
    • 因为是立即清掉垃圾数据,所以也不需要 stop-the-world
    • 因为是立即清掉垃圾数据,所以也可以做 RAII
    • 相比引用计数,没有循环引用的问题,因为同时最多一个强引用

    不足

    • 相比 mark-and-sweap gc 要多记录 被引用关系来重建强引用
    • 清理时,需要遍历强引用链后段数据三次
    zhigewuwang
        1
    zhigewuwang   89 天前
    有没有讨论的呀
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2334 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 07:58 · PVG 15:58 · LAX 23:58 · JFK 02:58
    ♥ Do have faith in what you're doing.