GC本を見ながら、コピーGCをC++で実装する。
中村 成洋 相川 光
秀和システム
売り上げランキング: 961
おすすめ度の平均:
GCの入門書として今のところ最強!
GC対象となるオブジェクトのベースクラス：
class GCObject {
size_t size;
GCObject* forwarding;
private:
~GCObject() { }
virtual void copy_children(class CopyGC*) { }
friend class CopyGC;
};
|
オブジェクトのサイズとコピー先を示すforwardingポインタを持ってるけど、forwardingポインタはコピー時にコピー元にだけ置ければいいからうまくやれば削れそうな気がする。
ここではコピー済みかどうかのタグは持たずに、forwardingポインタがNULL以外ならコピー済みとした。
今回のコピーGCではデストラクタは呼ばれないので、継承先クラスでデストラクタを作れないようにprivateにしている。
内部にオブジェクトを指すポインタを持っていたらcopy_children()メソッドをオーバーライドしてやる。
ヒープとオブジェクトを管理し、コピーGCするクラス：
class CopyGC {
size_t half_size;
char* from_start;
char* to_start;
char* free;
size_t left() const { return this->half_size - (this->free - this->from_start); }
public:
void set_heap(void* buf, size_t siz) {
this->half_size = siz / 2;
this->from_start = static_cast<char*>(buf);
this->to_start = static_cast<char*>(buf) + this->half_size;
this->free = this->from_start;
}
protected:
GCObject* new_obj(size_t size) {
if (size > this->left()) {
copying();
if (size > this->left()) {
allocation_fail();
}
}
GCObject* obj = reinterpret_cast<GCObject*>(this->free);
obj->size = size;
obj->forwarding = NULL;
this->free += size;
return obj;
}
void copying() {
this->free = this->to_start;
copy_live_objs();
SWAP(this->from_start, this->to_start);
}
virtual void copy_live_objs() = 0;
public:
GCObject* copy(GCObject* obj) {
if (obj->forwarding == NULL) {
memcpy(this->free, obj, obj->size);
obj->forwarding = reinterpret_cast<GCObject*>(this->free);
this->free += obj->size;
obj->forwarding->copy_children(this);
}
return obj->forwarding;
}
};
|
new_obj()でメモリを確保するときにアライメントとかとってない。
ヒープに空き容量がなかったらcopying()を呼び出してコピーGCする。
ルートをたどる処理は継承先でcopy_live_objs()をオーバーライドして実装する。
copy()でオブジェクトをto領域にコピーする。
ほとんどGC本の擬似コードどおりに書ける、素晴らしい！
====
これを使って、スタックマシンを作ってみる：
typedef GCObject* Value;
const Value nil = NULL;
class Integer : public GCObject {
int x;
Integer(int x_) : GCObject(), x(x_) { }
int get() const { return this->x; }
friend class Context;
};
bool is_integer(Value v) { return typeid(*v) == typeid(Integer); }
class Stack {
vector<Value> buf;
public:
Stack() : buf() { }
void clear() {
this->buf.clear();
}
void push(Value v) {
this->buf.push_back(v);
}
Value pop() {
int idx = this->buf.size();
if (idx > 0) {
Value v = this->buf[idx-1];
this->buf.pop_back();
return v;
} else {
assert(!"stack empty");
return nil;
}
}
void pop(int n) {
for (int i=0; i<n; ++i) {
this->buf.pop_back();
}
}
void remove(int idx) {
int n = this->buf.size();
assert(n >= idx + 1);
for (int i=n-idx; i<n; ++i) {
this->buf[i-1] = this->buf[i];
}
this->buf.pop_back();
}
Value peek(int idx) {
int n = this->buf.size();
assert(n >= idx + 1);
return this->buf[n - idx - 1];
}
void copy(CopyGC* gc) {
for (vector<Value>::iterator it = this->buf.begin(); it != this->buf.end(); ++it) {
*it = gc->copy(*it);
}
}
};
class Context : private CopyGC {
Stack stack;
Stack temp_stack;
void* heap;
public:
Context() : CopyGC(), stack(), temp_stack() {
const size_t HeapSize = 4 * 1024;
this->heap = malloc(HeapSize);
this->set_heap(this->heap, HeapSize);
}
~Context() {
free(this->heap);
stack.clear();
temp_stack.clear();
this->copying();
}
void push_integer(int x) {
Integer* p = new(new_obj(sizeof(*p))) Integer(x);
this->stack.push(p);
}
void pop() {
this->stack.pop();
}
void remove(int ofs) {
this->stack.remove(ofs);
}
void dup(int ofs=0) {
Value v = this->stack.peek(ofs);
this->push_value(v);
}
void add() {
Value v1 = this->stack.pop(); this->temp_stack.push(v1);
Value v2 = this->stack.pop(); this->temp_stack.push(v2);
if (is_integer(v1) && is_integer(v2)) {
Integer* p1 = static_cast<Integer*>(v1);
Integer* p2 = static_cast<Integer*>(v2);
this->push_integer(p1->get() + p2->get());
} else {
error_exit("not number");
}
this->temp_stack.pop(2);
}
void sub() {
Value v1 = this->stack.pop(); this->temp_stack.push(v1);
Value v2 = this->stack.pop(); this->temp_stack.push(v2);
if (is_integer(v1) && is_integer(v2)) {
Integer* p1 = static_cast<Integer*>(v1);
Integer* p2 = static_cast<Integer*>(v2);
this->push_integer(p1->get() - p2->get());
} else {
error_exit("not number");
}
this->temp_stack.pop(2);
}
void comp_le() {
Value v1 = this->stack.pop(); this->temp_stack.push(v1);
Value v2 = this->stack.pop(); this->temp_stack.push(v2);
if (is_integer(v1) && is_integer(v2)) {
Integer* p1 = static_cast<Integer*>(v1);
Integer* p2 = static_cast<Integer*>(v2);
this->push_integer(p1->get() <= p2->get());
} else {
error_exit("not number");
}
this->temp_stack.pop(2);
}
bool is_false() {
Value v = this->stack.pop();
return is_integer(v) && (static_cast<Integer*>(v))->get() == 0;
}
bool is_true() {
return !this->is_false();
}
void dump() {
Value v = this->stack.pop();
if (is_integer(v)) {
printf("%d\n", static_cast<Integer*>(v)->get());
} else {
error_exit("unknown type");
}
}
protected:
void push_value(Value v) {
this->stack.push(v);
}
virtual void copy_live_objs() {
this->stack.copy(this);
this->temp_stack.copy(this);
}
};
void fib(Context& ctx) {
ctx.push_integer(1);
ctx.dup(1);
ctx.comp_le();
if (ctx.is_true()) {
return;
} else {
ctx.push_integer(2);
ctx.dup(1);
ctx.sub();
fib(ctx);
ctx.push_integer(1);
ctx.dup(2);
ctx.sub();
fib(ctx);
ctx.add();
ctx.remove(1);
}
}
int main(int argc, char* argv[]) {
Context ctx;
int n = 10;
if (argc >= 2) {
n = atoi(argv[1]);
}
ctx.push_integer(n);
fib(ctx);
ctx.dump();
return 0;
}
|
コピーGCはヒープの確保が速くてすごくいい。
今の世の中、メモリはうなるほどあるので、ヒープが半分しか使えなくても問題ないかもしれない。
解放もCoalescingも必要ないし。
例によってフィボナッチ計算。
Cのプログラムで呼び出してるのにLuaのVMより遅いとかどんだけ。
