From 8aeb7f59e1da79411c02d1c502d4e7331733e2a0 Mon Sep 17 00:00:00 2001 From: Teddy Date: Thu, 15 Aug 2013 13:53:59 +0800 Subject: ... --- Makefile | 2 +- gc.cpp | 75 +++++++++++++++++++++++++++++++++++++-------------------------- gc.h | 13 +++++++++-- model.cpp | 8 ++----- model.h | 7 ++---- 5 files changed, 60 insertions(+), 45 deletions(-) diff --git a/Makefile b/Makefile index 5232363..2558d7b 100644 --- a/Makefile +++ b/Makefile @@ -1,7 +1,7 @@ CXX = g++ -DGMP_SUPPORT BUILD_DIR = build -all: debug +all: gc_debug debug: CXX += -DGC_INFO -g -pg gc_debug: CXX += -DGC_INFO -DGC_DEBUG -g -pg release: CXX += -O2 diff --git a/gc.cpp b/gc.cpp index 28a7360..d03ce36 100644 --- a/gc.cpp +++ b/gc.cpp @@ -10,9 +10,12 @@ typedef unsigned long long ull; static EvalObj *gcq[GC_QUEUE_SIZE]; static Container *cyc_list[GC_QUEUE_SIZE]; +ObjEntry *oe_null; GarbageCollector::GarbageCollector() { - joined.clear(); + joined = new ObjEntry(NULL, NULL); + joined->next = oe_null = new ObjEntry(NULL, NULL); + joined_size = 0; pending_list = NULL; resolve_threshold = GC_CYC_THRESHOLD; } @@ -22,14 +25,12 @@ GarbageCollector::PendingEntry::PendingEntry( void GarbageCollector::expose(EvalObj *ptr) { - if (ptr == NULL) return; + if (ptr == NULL || ptr->gc_obj == NULL) return; #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx exposed. count = %lu \"%s\"\n", - (ull)ptr, ptr->gc_get_cnt() - 1, ptr->ext_repr().c_str()); + (ull)ptr, ptr->gc_obj->gc_cnt - 1, ptr->ext_repr().c_str()); #endif - /* if (ptr->gc_get_cnt() == 0) - puts("oops");*/ - if (ptr->gc_dec()) + if (--ptr->gc_obj->gc_cnt == 0) { #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx pending. \n", (ull)ptr); @@ -44,18 +45,15 @@ void GarbageCollector::force() { { np = p->next; EvalObj *obj = p->obj; - if (joined.count(obj) && obj->gc_get_cnt() == 0) + if (obj->gc_obj && !obj->gc_obj->gc_cnt) *r++ = obj; delete p; } // fetch the pending pointers in the list // clear the list pending_list = NULL; -/* for (EvalObj2Int::iterator it = mapping.begin(); - it != mapping.end(); it++) - if (it->second == 0) *r++ = it->first;*/ #ifdef GC_INFO - fprintf(stderr, "%ld\n", joined.size()); + fprintf(stderr, "%ld\n", joined_size); size_t cnt = 0; #endif #ifdef GC_DEBUG @@ -66,7 +64,8 @@ void GarbageCollector::force() { for (; l != r; l++) { #ifdef GC_DEBUG - fprintf(stderr, "GC: !!! destroying space 0x%llx: %s. \n", (ull)*l, (*l)->ext_repr().c_str()); + fprintf(stderr, "GC: !!! destroying space 0x%llx: %s. \n", + (ull)*l, (*l)->ext_repr().c_str()); #endif #ifdef GC_INFO cnt++; @@ -87,13 +86,10 @@ void GarbageCollector::force() { #ifdef GC_INFO fprintf(stderr, "GC: Forced clear, %lu objects are freed, " "%lu remains\n" - "=============================\n", cnt, joined.size()); + "=============================\n", cnt, joined_size); #endif #ifdef GC_DEBUG - for (EvalObjSet::iterator it = joined.begin(); - it != joined.end(); it++) - fprintf(stderr, "%llx => %s\n", (ull)*it, (*it)->ext_repr().c_str()); #endif } @@ -103,10 +99,10 @@ EvalObj *GarbageCollector::attach(EvalObj *ptr) { if (flag) mapping[ptr]++; else mapping[ptr] = 1; */ - ptr->gc_inc(); + ptr->gc_obj->gc_cnt++; #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx attached. count = %lu \"%s\"\n", - (ull)ptr, ptr->gc_get_cnt(), ptr->ext_repr().c_str()); + (ull)ptr, ptr->gc_obj->gc_cnt, ptr->ext_repr().c_str()); #endif /* if (mapping.size() > GC_QUEUE_SIZE >> 1) force();*/ @@ -114,17 +110,18 @@ EvalObj *GarbageCollector::attach(EvalObj *ptr) { } void GarbageCollector::cycle_resolve() { -// if (joined.size() < resolve_threshold) return; EvalObjSet visited; Container **clptr = cyc_list; - for (EvalObjSet::iterator it = joined.begin(); - it != joined.end(); it++) - if ((*it)->is_container()) + for (ObjEntry *i = joined->next; i != oe_null; i = i->next) + { + EvalObj *obj = i->obj; + if (obj->is_container()) { - Container *p = static_cast(*it); - (*clptr++ = p)->gc_refs = (*it)->gc_get_cnt(); // init the count + Container *p = static_cast(obj); + (*clptr++ = p)->gc_refs = i->gc_cnt; // init the count p->keep = false; } + } EvalObj **l = gcq, **r = l; for (Container **p = cyc_list; p < clptr; p++) @@ -153,23 +150,39 @@ void GarbageCollector::cycle_resolve() { void GarbageCollector::collect() { force(); - if (joined.size() < resolve_threshold) return; - cycle_resolve(); - force(); +// if (joined_size >= resolve_threshold) + { + cycle_resolve(); + force(); + } } size_t GarbageCollector::get_remaining() { - return joined.size(); + return joined_size; } void GarbageCollector::set_resolve_threshold(size_t new_thres) { resolve_threshold = new_thres; } -void GarbageCollector::join(EvalObj *ptr) { - joined.insert(ptr); +ObjEntry *GarbageCollector::join(EvalObj *ptr) { + ObjEntry *p = new ObjEntry(joined, joined->next); + p->prev->next = p; + p->next->prev = p; + p->gc_cnt = 0; + p->obj = ptr; + joined_size++; + return p; } void GarbageCollector::quit(EvalObj *ptr) { - joined.erase(ptr); + ObjEntry *p = ptr->gc_obj; + p->prev->next = p->next; + p->next->prev = p->prev; + ptr->gc_obj = NULL; + delete p; + joined_size--; } + +ObjEntry::ObjEntry(ObjEntry *_prev, ObjEntry *_next) : + prev(_prev), next(_next) {} diff --git a/gc.h b/gc.h index 2d1c179..9f1aca6 100644 --- a/gc.h +++ b/gc.h @@ -44,6 +44,13 @@ extern GarbageCollector gc; gc.collect(); \ } while (0) +struct ObjEntry { + EvalObj *obj; + size_t gc_cnt; + ObjEntry *prev, *next; + ObjEntry(ObjEntry *prev, ObjEntry *next); +}; + class GarbageCollector { struct PendingEntry { @@ -52,18 +59,20 @@ class GarbageCollector { PendingEntry(EvalObj *obj, PendingEntry *next); }; - EvalObjSet joined; + ObjEntry *joined; PendingEntry *pending_list; size_t resolve_threshold; + size_t joined_size; public: + GarbageCollector(); void collect(); void cycle_resolve(); void force(); void expose(EvalObj *ptr); void set_resolve_threshold(size_t new_thres); - void join(EvalObj *ptr); + ObjEntry *join(EvalObj *ptr); void quit(EvalObj *ptr); size_t get_remaining(); EvalObj *attach(EvalObj *ptr); diff --git a/model.cpp b/model.cpp index 32c79d0..ba664a8 100644 --- a/model.cpp +++ b/model.cpp @@ -23,13 +23,9 @@ bool FrameObj::is_parse_bracket() { return ftype & CLS_PAR_BRA; } -bool EvalObj::gc_dec() { return --gc_cnt == 0; } -void EvalObj::gc_inc() { gc_cnt++; } -size_t EvalObj::gc_get_cnt() { return gc_cnt; } - EvalObj::EvalObj(int _otype) : - FrameObj(CLS_EVAL_OBJ), gc_cnt(0), otype(_otype) { - gc.join(this); + FrameObj(CLS_EVAL_OBJ), otype(_otype) { + gc_obj = gc.join(this); } EvalObj::~EvalObj() { diff --git a/model.h b/model.h index ba40137..fd88f7d 100644 --- a/model.h +++ b/model.h @@ -48,14 +48,13 @@ class FrameObj { }; +class ObjEntry; class Pair; class ReprCons; /** @class EvalObj * Objects that represents a value in evaluation */ class EvalObj : public FrameObj { - private: - size_t gc_cnt; protected: /** * Report the type of the EvalObj, which can avoid the use of @@ -63,6 +62,7 @@ class EvalObj : public FrameObj { */ int otype; public: + ObjEntry *gc_obj; /** * Construct an EvalObj * @param otype the type of the EvalObj (CLS_PAIR_OBJ for a @@ -101,9 +101,6 @@ class EvalObj : public FrameObj { virtual bool is_true(); /** External representation construction */ virtual ReprCons *get_repr_cons() = 0; - bool gc_dec(); - void gc_inc(); - size_t gc_get_cnt(); }; typedef std::set EvalObjSet; -- cgit v1.2.3