fuchencong

The way I am

0%

《lua 程序设计》读书笔记（11）：垃圾收集 & 协程

发表于 分类于

作为一本脚本语言，Lua 提供了自动内存管理机制，简化对内存资源的管理。Lua 还提供了协程机制，用于实现并发程序的编写。这篇文章将介绍 Lua 的垃圾收集以及协程机制。

垃圾收集

Lua 使用自动内存管理，程序可以创建对象（表、闭包等），但是却没有函数来删除对象。Lua 通过垃圾收集器自动地删除成为垃圾的对象。在一个理想的环境中，垃圾收集器对程序员来说是不可见的，但是有时即使是最智能的垃圾收集器也会需要我们的辅助。

弱引用表（weak table）、析构器（finalizer）和函数 collectgarbage 是 Lua 中用来辅助垃圾收集器的主要机制。

弱引用表

垃圾收集器不能帮我们猜测哪些是垃圾，某些情况下，当我们代码的确不会用到某个对象时，需要我们手动将这些对象赋值为 nil，以便将来释放这些对象。

有时候我们将某些对象插入到数组中，由于数组始终在引用该对象，这会阻止垃圾收集器回收该对象。弱引用表就是一种告知 Lua 一个引用不应该阻止一个对象回收的机制。所谓弱引用是一种不在垃圾收集器考虑范围内的对象引用。如果一个对象的引用都是弱引用，那么垃圾收集器将会回收这个对象并删除这些弱引用。

Lua 通过弱引用表来实现弱引用。一个表是否为弱引用表是由其元表中的 _mode 字段来实现的：

  • 如果其值为 k，表示该表的键是弱引用的
  • 如果其值为 v，表示该表的值时弱引用的
  • 如果其值为 kv，表示该表的键和值都是弱引用的

表由键值对组成，其两者都可以容纳任意类型的对象。正常情况下，垃圾收集器不会回收一个在可访问表中作为键或值的对象，这时他们都是强引用。而对于弱引用表，只要 key 或 value 被回收了，那么对应对应的整个键值对都会从表中删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a = {}

mt = {__mode = 'k'}
setmetatable(a, mt)

key = {}
a[key] = 1

key = {}
a[key] = 2

collectgarbage()

for key, value in pairs(a) do
    print(key, value)
end
1
2
# lua weak_key.lua
table: 0x5564f07c4d50   2

注意，只有对象可以从弱引用表中移除，而像数字、布尔值这样的 值 是不可回收的，从程序员的角度，字符串也是值而不是对象。

记忆函数

空间换时间是一种常见的编程技巧，可以通过记忆函数的执行结果，在后续使用相同的参数再次调用该函数时直接返回之前记忆的结果，用来加快函数的执行速度。弱引用表在这些场景中，可以及时释放那些不再使用的缓存结果，从而释放表空间。

记忆技术还可以用来确保某类对象的唯一性，如下是一个示例，相同的颜色复用相同的表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
local results = {}

setmetatable(results, {__mode = "v"})

function createRGB(r, g, b)
    local key = string.format("%d-%d-%d", r, g, b)
    local color = results[key]
    if color == nil then
        color = {red = r, green = g, blue = b}
        results[key] = color
    end

    return color
end

print(createRGB(1,1,1))
print(createRGB(1,1,1))

在该实现中，只要一种颜色正在被使用，它就不会从 results 中移除。

对象属性

弱引用表的另外一种重要应用是将属性与对象关联起来。当对象是一个表时，可以通过适当的唯一键把属性存储在这个表的自身当中（例如创建唯一键一种简单的方式创建一个新表并把它当做键使用）。如果对象不是一个表，那么它就不能保存它自己的属性，或者有时我们不希望把属性保存在原始的对象中。

外部表为对象和属性的映射提供了一种理想的方法，即之前介绍过的 对偶表示。但是需要考虑，一旦一个对象被当做表中的一个键，那么就是引用它。Lua 无法回收一个正在被用作键的对象。可以使用弱引用表来解决这个问题，

具有默认值的表

之前在介绍如何实现具有非 nil 默认值的表时，说到还需要弱引用表的支持。如下使用弱引用表来映射每一个表和它的默认值，它也是对偶表示的一种典型应用，使用 defaults[t] 来标识 t.defaults。如果表 defaults 没有弱引用的键，那么所有具有默认值的表就会永远存在下去。

1
2
3
4
5
6
7
local defaults = {}
setmetatable(defaults, {__mode = 'k'})
local mt = {__index = function(t) return defaults[t] end}
function setDefault(t, d)
    defaults[t] = d
    setmetatable(t, mt)
end

在第二种解决方案中，对不同默认值使用不同的元表，在遇到重复默认值时会使用相同的元表，这是记忆技术的典型应用。如下使用若引用的值使得不再被使用的元表能够被回收。

1
2
3
4
5
6
7
8
9
10
11
local metas = {}
setmetatable(metas, {__mode = 'v'})

function setDefault(t, d)
    local mt = metas[d]
    if mt == nil then
        mt = {__index = function() return d end}
        metas[d] = mt
    end
    setmetatable(t, mt)
end

具体使用哪种解决方案，取决于具体情况。如果应用中由上千个具有少量不同默认值的表，那么解决方案二更好。如果只有少量共享默认值的表，那么就应该选择解决方案一。

瞬表（Ephemeron Table）

一种情况是：一个具有弱引用键的表中的值有引用了对应的键。如下函数是一个常量函数工厂：

1
2
3
function factory(o)
    return (function() return o end)
end

在工厂中使用记忆是一种好的手段，可以避免在闭包已经存在时又创建新的闭包：

1
2
3
4
5
6
7
8
9
10
11
12
do
    local mem = {}
    setmetatable(mem, {__mode = "k"})
    function factory(o)
        local res = mem[o]
        if not res then
            res = (function () return o end)
            mem[o] = res
        end
        return res
    end
end

但是这里表 mem 中的值（常量函数）回指了它自己的键（对象本身）。虽然表的键是弱应用，但是值是强引用。所以对于每一个函数都存在一个强引用，每一个函数都指向其对应的对象，因此对于每个键都存在一个强引用。

Lua 通过瞬表来解决该问题，在 Lua 中一个具有弱引用键和强引用值的表是一个瞬表。在一个瞬表中，一个键的可访问性控制着对应值的可访问性。考虑瞬表中的一个元素 (k, v)，只有当存在某些指向 k 的其他外部应用存在时，指向 v 的引用才是强引用，否则即使 v 引用了 k，垃圾收集器最终会收集 k 并将元素从表中删除。

析构器

虽然垃圾收集器的目标是回收对象，但是它也可以帮助程序员来释放外部资源。析构器是一个与对象关联的函数，当该对象即将被回收时该函数会被调用。Lua 通过元方法 __gc 实现析构器。

1
2
3
4
5
> o = {x = "hi"}
> setmetatable(o, {__gc = function(o) print(o.x) end})
table: 0x557e4de5a4a0
> o = nil
> collectgarbage()

有个细节需要注意：通过给对象设置一个具有非空 __gc 元方法的元表，就可以把对象标记为需要进行析构处理。如果不标记对象，那么对象就不会被析构。所以如果在给对象 o 设置元表的时候，该元表没有 __gc 方法，那么该对象就不会被标记为需要析构处理。即使后续给元表增加元方法 __gc，Lua 也发现不了这种赋值的特殊之处，不会再把对象标记为需要进行析构处理。所有如果真的需要在后续设置元方法，那么可以给字段 __gc 先设置一个任意值作为占位符。

当垃圾收集器在同一个周期中析构多个对象时，它会按照对象被标记为需要析构处理的顺序逆序调用这些对象的析构器。一种常见的误解是认为正在被回收的对象之间的关联会影响对象析构的顺序。

1
2
3
4
5
6
7
8
9
10
> mt = {__gc = function(o) print(o[1]) end }
> list = nil
> for i = 1, 3 do
>> list = setmetatable({i, link = list}, mt)
>> end
> list = nil
> collectgarbage()
3
2
1

当一个析构器被调用时，它的参数正是被析构的对象，这称为临时复苏。在析构器执行期间，如果把对象存储在全局变量中，那么该对象在析构器返回后仍然可以访问，这称为永久复苏。

复苏必须是可传递的，如下代码中：

1
2
3
4
5
6
7
> A = {x = "this is A"}
> B = {f = A}
> setmetatable(B, {__gc= function(o) print(o.f.x) end})
table: 0x557e4de5ad30
> A, B = nil
> collectgarbage()
this is A

由于 B 的析构器访问了 A，因此 A 在 B 析构之前不能被回收，Lua 在运行析构器之前必须同时复苏 B 和 A。

由于复苏的存在，Lua 会在两个阶段中回收具有析构器的对象。当垃圾收集器首次发现某个具有析构器的对象不可达时，垃圾收集器就把这个对象复苏并将其放入待析构的队列中。一旦析构器开始运行，Lua 就将该对象标记为已经析构。当下一次垃圾收集器又发现这个对象不可达时，它就将这个对象删除。所以如果想保证程序中的所有垃圾被真正释放，那么必须调用 collectgarbage 两次。

如果一个对象直到程序运行结束时还没有被回收，那么 Lua 就会在整个 Lua 虚拟机关闭后调用它的析构器。这种特性可以在 Lua 中实现某种形式的 atexit 函数。

另一个技巧是允许程序在每次完成垃圾回收后调用指定的函数。由于析构器只运行一次，所以这种技巧是让每个析构器创建一个用来运行下一个析构器的新对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> do
>> local mt = {__gc = function(o)
>> print("new cycle")
>> setmetatable({}, getmetatable(o))
>> end
>> }
>> setmetatable({}, mt)
>> end

> collectgarbage()
new cycle
> collectgarbage()
new cycle
> collectgarbage()
new cycle

在每个垃圾收集周期内，垃圾收集器会在调用析构器前清理弱引用表中的值，在调用析构器之后再清理键。这种行为的原理在于我们经常使用带有弱引用键的表来保存对象的属性，因此析构器可能需要访问这些属性。

垃圾收集器

一直到 Lua5.0，Lua 使用的都是一个简单的 标记-清除 式垃圾收集器，这种收集器又被称为 stop-the-world（全局暂停式` 的收集器，意味着 Lua 会时不时停止主程序的运行来执行一次完整的垃圾收集周期。每个垃圾收集周期由 4 个阶段组成：标记、清理、清除和析构。

使用真正的垃圾收集器意味着 lua 可以处理对象引用之间的环，在使用环形数据结构时，不需要花费额外的精力，它们会像其他数据一样被回收。

Lua5.1 使用增量式垃圾收集器，它不需要在垃圾收集期间停止主程序的运行，相反它与解释器一起交替运行。当解释器分配一定数量内存，垃圾收集器也执行一小步。Lua5.2 引入了紧急垃圾收集，当内存分配失败时，Lua 会强制进行一次完整的垃圾收集，然后再尝试分配。

控制垃圾收集的步长

函数 collectgarbage 可以对垃圾收集器进行一些额外的控制。它的第一个参数用来说明执行何种操作；有的选项会用到一个整型作为第二个参数，称为 data。

任何垃圾收集器都是使用 CPU 时间换空间，pause（收集器的间歇率）和 stepmul（收集器的步进倍率）的默认值试图在这两者之间找到对于大多数应用来说足够好的平衡点。但是某些情况下仍然需要对他们进行优化。

  • 参数 pause 控制收集器在一次收集完成后等待多久再开始一次新的收集
  • 参数 stepmul 控制每分配 1kb 内存，垃圾收集器应该进行多少工作，该值越高，垃圾收集器使用的增量越小

collectgarbage 的另外一些参数用来在垃圾收集器运行时控制它的行为，例如 stop、restart、collect、step 参数。

协程

协程是一系列的可执行语句，拥有自己的栈、局部变量和指令指针，同时协程又与其他协程共享了全局变量和其他几乎一切资源。线程与协程的主要区别在于：一个多线程可以并行运行多个线程，而协程却需要彼此协作地运行，即在任意指定的时刻只能由一个协程运行，只有当正在运行的协程显式地被要求挂起时，其执行才会被暂停。

协程基础

Lua 中协程相关的所有函数都被放在表 coroutine 中：

  • create：用于创建新协程，该函数只有一个参数，即协程要执行的函数。create 返回一个 thread 类型的值，即新的协程
  • 一个协程具有 4 种状态：suspend、running、normal、dead。可以通过 coroutine.status() 来检查协程的状态
  • 协程被创建后，默认处于 suspend 状态，即协程不会在被创建时自动运行。coroutine.resume 用于启动或再次启动一个协程的执行，将其状态修改为 running
1
2
3
4
5
6
7
8
9
> co = coroutine.create(function() print("hi") end)
> print(type(co))
thread
> coroutine.status(co)
suspended
> coroutine.resume(co);
hi
> coroutine.status(co)
dead

协程真正的强大之处在于 yield，该函数可以让一个运行中的协程挂起自己，在后续再恢复运行。

1
2
3
4
5
6
7
> co = coroutine.create(function()
>> for i = 1, 10 do
>> print("co", i)
>> coroutine.yield()
>> end
>> end
>> )
1
2
3
4
> coroutine.resume(co);
co      1
> coroutine.status(co)
suspended

每次唤醒协程后，它就开始执行直到遇到第一个 yield。从协程角度来看，在 suspend 期间发生的活动都发生在协程调用 yield 期间，当我们唤醒协程时，yield 才最终返回，然后继续执行直到遇到下一个 yield 或执行结束。

1
2
3
4
5
6
7
8
9
10
11
> coroutine.resume(co);
co      2
> coroutine.resume(co);
co      3
......
> coroutine.resume(co);
co      10
> coroutine.resume(co);
>
> coroutine.resume(co)
false   cannot resume dead coroutine

如同函数 pcall 一样，函数 resume 也运行在保护模式中。因此协程中执行出错，Lua 不会显式错误信息，而是将错误信息返回给 resume 函数。

当协程 A 唤醒协程 B 时，协程 A 既不是挂起状态（因为不能唤醒 A），也不是运行状态（因为正在运行的协程是 B）。所以协程 A 此时的状态就被称为正常状态。

Lua 中一个非常有用的机制是通过一对 resume-yield 来交换数据：

  • 第一个 resume（没有对应等待的 yield）会把所有额外的参数传递给协程的主函数
  • coroutine.resume 的返回值中，第一个返回值为 true 时表示没有错误，之后的返回值对应 yield 的参数
  • coroutine.yield 的返回值是对应 resume 的参数
  • 当协程运行结束时，主函数的返回值将变成对应函数 resume 的返回值

Lua 提供的是所谓的非对称协程，即需要两个函数来控制协程：一个用于挂起协程，一个用于恢复协程。

哪个协程占据主循环

协程最经典之一就是生产者-消费者问题。成对的 resume-yield 可以调到调用者和被调用者之间的关系：一个协程调用 yield 时，它不是进入一个新的函数，而是返回一个挂起的调用（即函数 resume）。对函数 resume 的调用也不是启动一个新的函数，而是返回一个对 yield 的调用。这种特性使得双方都认为自己是主动方而对方是被动方。

如下是一种实现：

1
2
3
4
5
6
7
8
9
10
11
function receive()
    local status, value = coroutine.resume(producer)
    return value
end

function send()
    coroutine.yield(x)
end

producer = coroutine.create(send)
receive()

在该实现中，程序通过调用消费者启动。当消费者需要新值时，就唤醒生产者，生产者向消费者返回新值后挂起，直到消费者再次将其唤醒。这也被称为 消费者驱动 式的设计。另一种方式是生产者驱动式设计，其中消费者是协程。两者的思想都是相同。

可以通过过滤器来扩展上述设计，过滤器既是一个消费者又是一个生产者。如下是使用过滤器的生产者和消费者：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function receive(prod)
    local status, value = coroutine.resume(prod)
    return value
end

function send(x)
    coroutine.yield(x)
end

function producer()
    return coroutine.create(function()
        while true do
            local x = io.read()
            send(x)
        end
    end)
end

function filter(prod)
    return coroutine.create(function()
        for line = 1, math.huge do
            local x = receive(prod)
            x = string.format("%5d %s", line, x)
            send(x)
        end
    end)
end

function consumber(prod)
    while true do
        local x = receive(prod)
        io.write(x, "\n")
    end
end


consumber(filter(producer()))

在使用协程时，任务切换的开销小的多（基本与函数调用相同），因此生产者和消费者可以手拉手以相同速度运行，中间可以不用使用缓冲区。

将协程用作迭代器

一个迭代器可以产生由循环体消费的内容，用协程来实现迭代器看上去就很合适。如下程序用于生成排列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function permgen(a, n)
    n = n or #a
    if n <= 1 then
        printResult(a)
    else
        for i = 1, n do
            a[n], a[i] = a[i], a[n]
            permgen(a, n - 1)
            a[n], a[i] = a[i], a[n]
        end
    end
end

function printResult(a)
    for i = 1, #a do io.write(a[i], " ") end
    io.write('\n')
end

permgen({1, 2, 3})

可以将其代码转换成迭代器逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function permgen(a, n)
    n = n or #a
    if n <= 1 then
        coroutine.yield(a)
    else
        for i = 1, n do
            a[n], a[i] = a[i], a[n]
            permgen(a, n - 1)
            a[n], a[i] = a[i], a[n]
        end
    end
end

function permutations(a)
    local co = coroutine.create(function () permgen(a) end)
    return function()
        local code, res = coroutine.resume(co)
        return res
    end
end


function printResult(a)
    for i = 1, #a do io.write(a[i], " ") end
    io.write('\n')
end

for p in permutations{1, 2, 3} do
    printResult(p)
end

上面的代码使用了 Lua 中一种常见的模式，即将唤醒对应协程的调用包装在一个函数中。由于该模式非常常见，因此 Lua 专门提供了 coroutine.wrap 来完成该功能。该函数也用来创建一个新的协程，但是 wrap 函数并不返回协程而是一个函数，当该函数被调用时会唤醒协程。与原始函数 resume 不同，该函数第一个返回值不是错误代码，当遇到错误时该函数会抛出异常。

因此上述代码可以简化为：

1
2
3
function permutations(a)
    return coroutine.wrap(function () permgen(a) end)
end

事件驱动式编程

协程可以让我们使用事件循环来简化循环代码。如下是一个示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
local cmdQueue = {}

local lib = {}


function lib.readline(stream, callback)
    local nextCmd = function()
        callback(stream:read())
    end
    table.insert(cmdQueue, nextCmd)
end


function lib.writeline(stream, line, callback)
    local nextCmd = function()
        callback(stream:write(line))
    end
    table.insert(cmdQueue, nextCmd)
end


function lib.stop()
    table.insert(cmdQueue, "stop")
end


function lib.runloop()
    while true do
        local nextCmd = table.remove(cmdQueue, 1)
        if nextCmd == "stop" then
            break
        else
            nextCmd()
        end
    end
end

return lib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
local lib = require "async_lib"


function run(code)
    local co = coroutine.wrap(function()
        code()
        lib.stop()
    end)

    co()

    lib.runloop()
end


function putline(stream, line)
    local co = coroutine.running()
    local callback = (function() coroutine.resume(co) end)
    lib.writeline(stream, line, callback)
    coroutine.yield()
end

function getline(stream, line)
    local co = coroutine.running()
    local callback = (function(l) coroutine.resume(co, l) end)
    lib.readline(stream, callback)
    local line = coroutine.yield()
    return line
end


run(function()
    local t = {}
    local input = io.input()
    local out =  io.output()

    while true do
        local line = getline(input)
        if not line then
            break
        end
        t[#t + 1] = line
    end

    for i = #t, 1, -1 do
        putline(out, t[i] .. "\n")
    end
end)