From addbfae58d8afceb06d92f6ef1cdfed89c07518b Mon Sep 17 00:00:00 2001 From: Teddy Date: Wed, 14 Aug 2013 23:28:20 +0800 Subject: significant improvement on gc efficiency --- Makefile | 2 +- eval.cpp | 6 +++++- gc.cpp | 62 ++++++++++++++++++++++++++++++++++---------------------------- gc.h | 7 ++++--- model.cpp | 15 ++++++++++++++- model.h | 6 ++++++ parser.cpp | 1 + 7 files changed, 65 insertions(+), 34 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/eval.cpp b/eval.cpp index 2576157..fd301e7 100644 --- a/eval.cpp +++ b/eval.cpp @@ -11,7 +11,11 @@ EvalObj *eval_stack[EVAL_STACK_SIZE]; void Evaluator::add_builtin_routines() { #define ADD_ENTRY(name, rout) \ - envt->add_binding(new SymObj(name), rout) +do { \ + SymObj *tmp = new SymObj(name); \ + envt->add_binding(tmp, rout); \ + delete tmp; \ +} while (0) #define ADD_BUILTIN_PROC(name, rout) \ ADD_ENTRY(name, new BuiltinProcObj(rout, name)) diff --git a/gc.cpp b/gc.cpp index 14f7edd..4df2d46 100644 --- a/gc.cpp +++ b/gc.cpp @@ -12,7 +12,7 @@ static EvalObj *gcq[GC_QUEUE_SIZE]; static Container *cyc_list[GC_QUEUE_SIZE]; GarbageCollector::GarbageCollector() { - mapping.clear(); + joined.clear(); pending_list = NULL; resolve_threshold = GC_CYC_THRESHOLD; } @@ -22,21 +22,18 @@ GarbageCollector::PendingEntry::PendingEntry( void GarbageCollector::expose(EvalObj *ptr) { - bool flag = mapping.count(ptr); - if (flag) - { + if (ptr == NULL) return; #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx exposed. count = %lu \"%s\"\n", - (ull)ptr, mapping[ptr] - 1, ptr->ext_repr().c_str()); + (ull)ptr, ptr->gc_get_cnt() - 1, ptr->ext_repr().c_str()); #endif - if (!--mapping[ptr]) + if (ptr->gc_dec()) { #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx pending. \n", (ull)ptr); #endif pending_list = new PendingEntry(ptr, pending_list); } - } } void GarbageCollector::force() { @@ -44,8 +41,9 @@ void GarbageCollector::force() { for (PendingEntry *p = pending_list, *np; p; p = np) { np = p->next; - if (mapping.count(p->obj) && mapping[p->obj] == 0) - *r++ = p->obj; + EvalObj *obj = p->obj; + if (joined.count(obj) && obj->gc_get_cnt() == 0) + *r++ = obj; delete p; } // fetch the pending pointers in the list // clear the list @@ -55,7 +53,7 @@ void GarbageCollector::force() { if (it->second == 0) *r++ = it->first;*/ #ifdef GC_INFO - fprintf(stderr, "%ld\n", mapping.size()); + fprintf(stderr, "%ld\n", joined.size()); size_t cnt = 0; #endif #ifdef GC_DEBUG @@ -72,7 +70,6 @@ void GarbageCollector::force() { cnt++; #endif delete *l; - mapping.erase(*l); // maybe it's a complex structure, // so that more pointers are reported for (PendingEntry *p = pending_list, *np; p; p = np) @@ -88,40 +85,42 @@ void GarbageCollector::force() { #ifdef GC_INFO fprintf(stderr, "GC: Forced clear, %lu objects are freed, " "%lu remains\n" - "=============================\n", cnt, mapping.size()); + "=============================\n", cnt, joined.size()); #endif #ifdef GC_DEBUG - for (EvalObj2Int::iterator it = mapping.begin(); - it != mapping.end(); it++) - fprintf(stderr, "%llx => %s\n", (ull)it->first, it->first->ext_repr().c_str()); + for (EvalObjSet::iterator it = joined.begin(); + it != joined.end(); it++) + fprintf(stderr, "%llx => %s\n", (ull)*it, (*it)->ext_repr().c_str()); #endif } EvalObj *GarbageCollector::attach(EvalObj *ptr) { if (!ptr) return NULL; // NULL pointer - bool flag = mapping.count(ptr); +/* bool flag = mapping.count(ptr); if (flag) mapping[ptr]++; else mapping[ptr] = 1; + */ + ptr->gc_inc(); #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx attached. count = %lu \"%s\"\n", - (ull)ptr, mapping[ptr], ptr->ext_repr().c_str()); + (ull)ptr, ptr->gc_get_cnt(), ptr->ext_repr().c_str()); #endif - if (mapping.size() > GC_QUEUE_SIZE >> 1) - force(); +/* if (mapping.size() > GC_QUEUE_SIZE >> 1) + force();*/ return ptr; // passing through } void GarbageCollector::cycle_resolve() { - if (mapping.size() < resolve_threshold) return; +// if (joined.size() < resolve_threshold) return; EvalObjSet visited; Container **clptr = cyc_list; - for (EvalObj2Int::iterator it = mapping.begin(); - it != mapping.end(); it++) - if (it->first->is_container()) + for (EvalObjSet::iterator it = joined.begin(); + it != joined.end(); it++) + if ((*it)->is_container()) { - Container *p = static_cast(it->first); - (*clptr++ = p)->gc_refs = it->second; // init the count + Container *p = static_cast(*it); + (*clptr++ = p)->gc_refs = (*it)->gc_get_cnt(); // init the count p->keep = false; } @@ -144,7 +143,6 @@ void GarbageCollector::cycle_resolve() { if (!(*p)->keep) { delete *p; - mapping.erase(*p); } #ifdef GC_INFO fprintf(stderr, "GC: cycle resolved.\n"); @@ -153,15 +151,23 @@ void GarbageCollector::cycle_resolve() { void GarbageCollector::collect() { force(); - if (mapping.size() < resolve_threshold) return; + if (joined.size() < resolve_threshold) return; cycle_resolve(); force(); } size_t GarbageCollector::get_remaining() { - return mapping.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); +} + +void GarbageCollector::quit(EvalObj *ptr) { + joined.erase(ptr); +} diff --git a/gc.h b/gc.h index 452b0a0..78d26ae 100644 --- a/gc.h +++ b/gc.h @@ -4,10 +4,9 @@ #include "model.h" #include -const int GC_QUEUE_SIZE = 262144; +const int GC_QUEUE_SIZE = 64 * 1024 * 1024; const size_t GC_CYC_THRESHOLD = GC_QUEUE_SIZE >> 1; -typedef std::map EvalObj2Int; typedef std::set EvalObjSet; #define GC_CYC_TRIGGER(ptr) \ @@ -31,7 +30,7 @@ class GarbageCollector { PendingEntry(EvalObj *obj, PendingEntry *next); }; - EvalObj2Int mapping; + EvalObjSet joined; PendingEntry *pending_list; size_t resolve_threshold; @@ -42,6 +41,8 @@ class GarbageCollector { void force(); void expose(EvalObj *ptr); void set_resolve_threshold(size_t new_thres); + void join(EvalObj *ptr); + void quit(EvalObj *ptr); size_t get_remaining(); EvalObj *attach(EvalObj *ptr); }; diff --git a/model.cpp b/model.cpp index 64a3c96..32c79d0 100644 --- a/model.cpp +++ b/model.cpp @@ -4,9 +4,11 @@ #include "exc.h" #include "consts.h" #include "types.h" +#include "gc.h" const int REPR_STACK_SIZE = 262144; extern EmptyList *empty_list; +extern GarbageCollector gc; static EvalObjAddrHash hash; static ReprCons *repr_stack[REPR_STACK_SIZE]; @@ -21,7 +23,18 @@ bool FrameObj::is_parse_bracket() { return ftype & CLS_PAR_BRA; } -EvalObj::EvalObj(int _otype) : FrameObj(CLS_EVAL_OBJ), otype(_otype) {} +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); +} + +EvalObj::~EvalObj() { + gc.quit(this); +} bool EvalObj::is_container() { return otype & CLS_CONTAINER; diff --git a/model.h b/model.h index 9b5093e..8d272f8 100644 --- a/model.h +++ b/model.h @@ -63,6 +63,8 @@ class ReprCons; * 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 @@ -77,6 +79,7 @@ class EvalObj : public FrameObj { * CLS_SIM_OBJ */ EvalObj(int otype = CLS_SIM_OBJ); + ~EvalObj(); /** Check if the object is a simple object (instead of a call * invocation) * @return true if the object is not a construction (Pair) @@ -107,6 +110,9 @@ 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; diff --git a/parser.cpp b/parser.cpp index a8577d3..8fbbc4e 100644 --- a/parser.cpp +++ b/parser.cpp @@ -193,6 +193,7 @@ Pair *ASTGenerator::absorb(Tokenizor *tk) { Pair *_lst = TO_PAIR(lst); lst = _lst->car; delete _lst; + delete obj; } else { -- cgit v1.2.3-70-g09d2