Lua GC算法中是否存在“循环引用”问题

前几周到北京参见Openresty 2017大会,在会上分享了Lua 5.1 GC原理相关的内容。

其中提到,Lua采用的扫描标记算法,较之Python等使用的引用计数算法,不会出现循环引用问题。会后,有人问我其中的原因,一时之间想不太清楚,最近终于有了空闲的时间,可以来整理一下思路了。

还是以代码来说明问题:

--启动gc回收并打印回收结果函数
function memColl()
    print("now collect")
    collectgarbage("collect")
    local c1 = collectgarbage("count")
    print("after collect , mem used is %d", c1)
end

--开始分配前
collectgarbage("collect")
local c1 = collectgarbage("count")
print("before new, mem used is %d", c1)

--分配一个足够大的表t
function test()
  local t = {}
  for i = 1, 1000000, 1 do
      t[i] = i
  generique cialis end

  --分配一个足够大的表g
  local g = {}
  for i = 1, 1000000, 1 do
      g[i] = i
  end

  --t和g互相引用
  t["g"] = g
  g["t"] = t
end

test()

local c2 = collectgarbage("count")
print("after new, mem used is %d", c2)

--多次回收
memColl()

如上代码中,在函数test中分别分配了两个大表g和t,在函数的最后,将两者相互引用。分别在调用函数之前以及之后,还有做完GC操作之后打印了当前的内存使用量,结果如下:

before new, mem used is %d  28.1064453125
after new, mem used is %d   32796.346679688
now collect
after collect , mem used is %d  28.1455078125

可以看到,在函数结束之后,系统完成了对g、t两个对象的回收,尽管它们之间存在相互引用的关系。

究其原因,“扫描回收”算法的本质,是根据对象的可达性(reachable)来判断对象是否可以回收的,以前面的例子为例,在离开函数test之后,g、t两个对象就都不可达了,于是尽管它们之间存在相互引用关系,也会被系统回收。有的人会问了,g被t引用了,怎么就不可达呢?因为是引用它的t同样也是不可达的,所以这个引用关系并不足以让这个对象继续留在系统里。

从这里也可以看到,基于引用计数的GC算法和基于扫描的算法的最大不同:前者只需要局部的信息(即对象的引用计数),而后者需要的是全局的信息。

Leave a Reply