Triển Khai Một Hệ Thống Thu Gom Rác Đơn Giản Trong C++

2010-02-01 Khoảng 1000 từ 5 phút

Nội dung

Dưới đây là bản dịch và diễn giải lại bằng tiếng Việt phong phú, tuân thủ hoàn toàn yêu cầu của bạn:

Xây dựng hệ thống GC đánh dấu-thu gom nhẹ trong C++

Gần đây tôi có nhu cầu đóng gói lại một engine bằng C++ để tích hợp với QT. Mặc dù engine gốc được viết bằng C thuần và phần lớn ứng dụng sử dụng Lua, việc quản lý vòng đời đối tượng phụ thuộc hoàn toàn vào cơ chế GC của Lua. Về chi tiết này, bạn có thể tham khảo bài viết trước đây của tôi “Quản lý vòng đời C-Object trong Lua”.

Khi chuyển đổi lớp trung gian sang C++, một trong những vấn đề nảy sinh là thiếu cơ chế GC tích hợp sẵn. Trước đây tôi từng viết một thư viện GC, nhưng chưa đáp ứng được yêu cầu về tính đơn giản trong một số trường hợp cụ thể. Nhân dịp nghỉ Tết, tôi đã dành thời gian tối ưu hóa thiết kế và xây dựng một khung GC đơn giản hơn chỉ với hơn 150 dòng mã, đủ để trình bày trực tiếp trong bài viết này.

Đây vẫn là những đoạn mã thử nghiệm (toy code), tôi hoàn thành trong vòng một ngày với một số điểm chưa hoàn thiện. Tuy nhiên, nó đủ để minh họa rõ ràng nguyên lý hoạt động.

Mục tiêu thiết kế

Giải quyết tham chiếu vòng: Sử dụng cơ chế đánh dấu (mark) thay vì đếm tham chiếu truyền thống, đồng thời đảm bảo hiệu năng ngang hoặc cao hơn.
Đơn giản hóa sử dụng: Tránh phụ thuộc vào kỹ thuật template phức tạp hay quá nhiều “syntactic sugar” để giữ mã nguồn dễ tiếp cận.
Tách biệt giao diện và cài đặt: Không cứng nhắc theo kiểu COM, mà tận dụng tối đa cơ chế sẵn có của C++.
Dễ bảo trì và mở rộng: Mã nguồn dễ hiểu, ít rủi ro sai sót, thuận tiện cho việc nâng cấp sau này.

Thiết kế giao diện

i_gcobject.h - Giao diện chính cho các đối tượng có thể thu gom

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// file: i_gcobject.h
#ifndef I_GCOBJECT_H
#define I_GCOBJECT_H

struct interface i_gcobject {
    virtual ~i_gcobject() {}
    virtual void touch() {}
    virtual void mark() = 0;
    virtual void grab() = 0;
    virtual void release() = 0;

    static void collect();
};

#endif

Các phương thức chính:

mark(): Đánh dấu đối tượng đang hoạt động
grab(): Kết nối đối tượng với “root” (nút gốc)
release(): Ngắt kết nối khỏi root
touch() (template method): Hỗ trợ đánh dấu các thành phần bên trong đối tượng

i_gcholder.h - Giao diện quản lý root node

1
2
3
4
5
6
7
8


// file: i_gcholder.h
#include "i_gcobject.h"

interface i_gcholder : virtual i_gcobject {
    virtual void hold(i_gcobject *) = 0;
    virtual void unhold(i_gcobject *) = 0;
    static i_gcholder* create();
};

Triển khai cụ thể

gcobject.h/cpp - Lớp cơ sở gcobject

 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


// gcobject.h
class gcobject : virtual i_gcobject {
    bool marked;
public:
    gcobject();
    void mark() override;
    void grab() override;
    void release() override;
    struct f_unmarked;
};

// gcobject.cpp
#include "gcobject.h"
#include "i_gcholder.h"
#include <vector>
#include <algorithm>

static bool gc_trigger;
static std::vector<gcobject*> gc_pool;
static i_gcholder* gc_root = i_gcholder::create();

struct gcobject::f_unmarked {
    bool operator()(gcobject* obj) {
        if (obj->marked != gc_trigger) {
            delete obj;
            return true;
        }
        return false;
    }
};

gcobject::gcobject() : marked(!gc_trigger) {
    gc_pool.push_back(this);
}

void gcobject::mark() {
    if (marked != gc_trigger) {
        marked = gc_trigger;
        touch();
    }
}

void gcobject::grab() {
    gc_root->hold(this);
}

void gcobject::release() {
    gc_root->unhold(this);
}

void i_gcobject::collect() {
    gc_root->mark();
    gc_pool.erase(
        std::remove_if(gc_pool.begin(), gc_pool.end(), gcobject::f_unmarked()),
        gc_pool.end()
    );
    gc_trigger = !gc_trigger;
}

gcholder.cpp - Quản lý tập hợp các đối tượng cần giữ

 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


// gcholder.cpp
#include "i_gcholder.h"
#include "gcobject.h"
#include <vector>
#include <algorithm>

class gcholder : public virtual i_gcholder, virtual gcobject {
    std::vector<i_gcobject*> hold_set;
    std::vector<i_gcobject*> unhold_set;
    bool set_changed;
    bool hold_set_sorted, unhold_set_sorted;

    void combine_set() {
        if (!hold_set_sorted) {
            std::sort(hold_set.begin(), hold_set.end());
            hold_set_sorted = true;
        }
        if (!unhold_set_sorted) {
            std::sort(unhold_set.begin(), unhold_set.end());
            unhold_set_sorted = true;
        }
        // ... (logic kết hợp các tập hợp)
    }

    virtual void touch() {
        if (set_changed) {
            combine_set();
            set_changed = false;
        }
        std::for_each(hold_set.begin(), hold_set.end(), 
            { obj->mark(); });
    }
};

i_gcholder* i_gcholder::create() {
    return new gcholder;
}

Ví dụ minh họa: Cây nhị phân với GC

test.cpp

 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


#include "gcobject.h"
#include <set>
#include <cstdio>

interface i_tree : virtual i_gcobject {
    virtual void link(i_tree* p) = 0;
    static i_tree* create();
};

class tree : public virtual i_tree, virtual gcobject {
    tree* parent;
    std::multiset<tree*> children;

    void touch() override {
        if (parent) parent->mark();
        for (auto child : children) child->mark();
    }

public:
    tree() : parent(nullptr) {
        printf("Tạo node %p\n", this);
    }
    ~tree() {
        printf("Xóa node %p\n", this);
    }
};

int main() {
    i_tree* root = i_tree::create();
    root->grab();
    
    i_tree* node = i