深入 Lua Garbage Collector(一)

看到一个 Bob Nystrom 写的 C 语言实现的 Garbage Collector

借着这个小程序顺便深入地了解一下Lua的垃圾回收机制

Garbage Collector算法小结

这是之前做的一点小笔记:

C Garbage Collector

首先还是先来看看这个 C 的基本的垃圾回收器

采用的算法

用的是经典的 Mark & Sweep 算法

在上面的笔记里面已经介绍的很清楚了

该算法的工作原理几乎与我们对 可访问性(reachability) 的定义完全一样:

  1. 从根节点开始,依次遍历整个对象图。每当你访问到一个对象,在上面设置一个 标记(mark) 位,置为 true 。

  2. 一旦搞定,找出所有标记位为 not 的对象集,然后删除它们。

对象对

要想清理垃圾,首先我们得制造点垃圾出来

所以假设我们正在为一种简单的语言编写一个解释器。它是动态的类型并且有两种类型的变量: intpair 。 下面是用枚举来标示一个对象的类型:

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
typedef enum {

    OBJ_INT,

    OBJ_PAIR

} ObjectType;

// 因为一个对象在虚拟机中可以是这两个当中的任意一种类型,所以在C中用tagged union 来实现对象

typedef struct sObject {

    //表示对象类型:pair or int

    ObjectType type;

    unsigned char marked;

    //仅维持一张由所有分配过(内存)的对象(组成)的链表。

    struct sObject*next;

    //union持有这个数据

    //union就是一个结构体,它将字段重叠在内存中

    union {

        int value;

        struct {

            struct sObject* head;

            struct sObject* tail;

        };

    };

} Object;  

—|—


小虚拟机

虚拟机要么基于栈( JVM , CLR ),要么基于寄存器( Lua ),其实本质上说都是基于栈的,它用来保存一个表达式中间需要用到的临时变量和局部变量

下面我们建立一个简洁的虚拟机模型:

1

2

3

4

5

6

7

8

9

10

11

12

13

14
// 小虚拟机

typedef struct {

    Object* stack[STACK_MAX];

    int stackSize;

    //虚拟机会保留链表头的痕迹

    Object* firstObject;

    //追踪创建了多少个对象

    int numObjects;

    //多少数目之后清理

    int maxObjects;

} VM;  

—|—


虚拟机的操作

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20
// 初始化一个虚拟机

VM* () {

    VM* vm = malloc(sizeof(VM));

    vm->stackSize = 0;

    Object* firstObject = NULL;

    vm->numObjects = 0;

    vm->maxObjects = 8;

    return vm;

}

//操作虚拟机堆栈

void push(VM* vm, Object* value) {

    assert(vm->stackSize < STACK_MAX, "Stack overflow!!!");

    vm->stack[vm->stackSize++] = value;

}

Object* pop(VM* vm) {

    assert(vm->stackSize > 0, "Stack underflow!!!");

    return vm->stack[--vm->stackSize];

}  

—|—


Mark

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16
void mark(Object* object) {

    //检查循环!

    if (object->marked) return;

    object->marked = 1;

    if (object->type == OBJ_PAIR) {

        mark(object->head);

        mark(object->tail);

    }

}

void markAll(VM* vm) {

    for (int i = 0; i < vm->stackSize; i++) {

        mark(vm->stack[i]);

    }

}  

—|—


Sweep

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20
//清理

//仅维持一张由所有分配过(内存)的对象(组成)的链表。

void sweep(VM* vm) {

    Object** object = &vm->firstObject;

    while (*object) {

        if (!(*object)->marked) {

            //没有访问过,所以从链表中移除然后释放它

            Object* unreached = *object;

            *object = unreached->next;

            free(unreached);

            vm->numObjects--;

        } else {

            //访问过,所以不标记它

            (*object)->marked = 0;

            object = &(*object)->next;

        }

    }

}  

—|—


GC

1

2

3

4

5

6

7

8

9

10
void gc(VM* vm) {

    int numObjects = vm->numObjects;

    markAll(vm);

    sweep(vm);

    vm->maxObjects = vm->numObjects * 2;

    printf("Collected %d objects, %d remaining.n", numObjects - vm->numObjects,

            vm->numObjects);

}  

—|—


对象操作函数

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
Object* newObject(VM* vm, ObjectType type) {

    if (vm->numObjects == vm->maxObjects) gc(vm);

    Object* object = malloc(sizeof(Object));

    object->type = type;

    //无论何时创建对象,都添加到链表中

    object->next = vm->firstObject;

    vm->firstObject = object;

    object->marked = 0;

    vm->numObjects++;

    return object;

}

//编写方法将每种类型的对象压到虚拟机的栈上

void pushInt(VM* vm, int intValue) {

    Object* object = newObject(vm, OBJ_INT);

    object->value = intValue;

    

    push(vm, object);

}

Object* pushPair(VM* vm) {

    Object* object = newObject(vm, OBJ_PAIR);

    object->tail = pop(vm);

    object->head = pop(vm);

    push(vm, object);

    return object;

}

void objectPrint(Object* object) {

    switch (object->type) {

        case OBJ_INT:

        printf("%d", object->value);

        break;

        case OBJ_PAIR:

        printf("(");

        objectPrint(object->head);

        printf(", ");

        objectPrint(object->tail);

        printf(")");

        break;

    }

}  

—|—


free、test、main

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

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90
void freeVM(VM  *vm) {

    vm->stackSize = 0;

    gc(vm);

    free(vm);

}

void test1() {

    printf("Test1: Objects on stack are preserved.n");

    VM* vm = newVM();

    pushInt(vm, 1);

    pushInt(vm, 2);

    gc(vm);

    assert(vm->numObjects == 2, "Should have preserved objects.");

    freeVM(vm);

}

void test2() {

    printf("Test2: Objects on stack are collected.n");

    VM* vm = newVM();

    pushInt(vm, 1);

    pushInt(vm, 2);

    pop(vm);

    pop(vm);

    gc(vm);

    assert(vm->numObjects == 0, "Should have collected objects.");

    freeVM(vm);

}

void test3() {

    printf("Test3: Reach nested objects.n");

    VM* vm = newVM();

    pushInt(vm, 1);

    pushInt(vm, 2);

    pushPair(vm);

    pushInt(vm, 3);

    pushInt(vm, 4);

    pushPair(vm);

    pushPair(vm);

    gc(vm);

    assert(vm->numObjects == 7, "Should have reached objects.");

    freeVM(vm);

}

void test4() {

    printf("Test4: Handle cycles.n");

    VM* vm = newVM();

    pushInt(vm, 1);

    pushInt(vm, 2);

    Object* a = pushPair(vm);

    pushInt(vm, 3);

    pushInt(vm, 4);

    Object* b = pushPair(vm);

    //建立一个循环, 并且让2 和 4 不可到达和收集

    a->tail = b;

    b->tail = a;

    gc(vm);

    assert(vm->numObjects == 4, "Should have collected objects.");

    freeVM(vm);

}

void perfTest() {

    printf("Performance Tsetn");

    VM* vm = newVM();

    for (int i = 0; i < 1000; i++) {

        for (int j = 0; j < 20; j++) {

            pushInt(vm, i);

        }

        for (int k = 0; k < 20; k++) {

            pop(vm);

        }

    }

    freeVM(vm);

}

int main(int argc, const char * argv[]) {

    test1();

    test2();

    test3();

    test4();

    perfTest();

    return 0;

}  

—|—


测试结果

总结

这个简单的收集器与目前 RubyLua 中的收集器非常的相似,所以下一次我们将深入了解 LuaGC 机制。

糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017