diff options
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | eval.cpp | 1 | ||||
| -rw-r--r-- | gc.cpp | 45 | ||||
| -rw-r--r-- | gc.h | 17 | ||||
| -rw-r--r-- | main.cpp | 1 | ||||
| -rw-r--r-- | model.h | 7 | ||||
| -rw-r--r-- | types.cpp | 58 | ||||
| -rw-r--r-- | types.h | 20 |
8 files changed, 133 insertions, 22 deletions
@@ -1,8 +1,8 @@ CXX = g++ -DGMP_SUPPORT BUILD_DIR = build -all: release -debug: CXX += -g -pg +all: gc_debug +debug: CXX += -DGC_INFO -g -pg gc_debug: CXX += -DGC_INFO -DGC_DEBUG -g -pg release: $(BUILD_DIR) $(BUILD_DIR)/sonsi @@ -24,7 +24,7 @@ $(BUILD_DIR): mkdir -p $(BUILD_DIR) $(BUILD_DIR)/%.o : %.cpp - $(CXX) -o $@ -c $< -Wall -O2 + $(CXX) -o $@ -c $< -Wall clean: rm -rf $(BUILD_DIR) @@ -205,6 +205,7 @@ EvalObj *Evaluator::run_expr(Pair *prog) { else throw TokenError(opt->ext_repr(), SYN_ERR_CAN_NOT_APPLY); gc.force(); + gc.cycle_resolve(); } } } @@ -1,6 +1,7 @@ #include "gc.h" #include "exc.h" #include "consts.h" +#include <vector> #if defined(GC_DEBUG) || defined (GC_INFO) #include <cstdio> @@ -8,10 +9,10 @@ typedef unsigned long long ull; #endif static EvalObj *gcq[GC_QUEUE_SIZE]; +static Container *cyc_list[GC_QUEUE_SIZE]; GarbageCollector::GarbageCollector() { mapping.clear(); - pend_cnt = 0; pending_list = NULL; } @@ -42,7 +43,7 @@ void GarbageCollector::force() { for (PendingEntry *p = pending_list, *np; p; p = np) { np = p->next; - if (mapping[p->obj] == 0) + if (mapping.count(p->obj) && mapping[p->obj] == 0) *r++ = p->obj; delete p; } // fetch the pending pointers in the list @@ -111,3 +112,43 @@ EvalObj *GarbageCollector::attach(EvalObj *ptr) { return ptr; // passing through } +void GarbageCollector::cycle_resolve() { + if (mapping.size() < GC_CYC_THRESHOLD) + return; + EvalObjSet visited; + Container **clptr = cyc_list; + for (EvalObj2Int::iterator it = mapping.begin(); + it != mapping.end(); it++) + if (it->first->is_container()) + { + Container *p = static_cast<Container*>(it->first); + (*clptr++ = p)->gc_refs = it->second; // init the count + p->keep = false; + } + + EvalObj **l = gcq, **r = l; + for (Container **p = cyc_list; p < clptr; p++) + (*p)->gc_decrement(); + for (Container **p = cyc_list; p < clptr; p++) + if ((*p)->gc_refs) + { + *r++ = *p; + visited.insert(*p); + } + for (; l != r; l++) + { + Container *p = static_cast<Container*>(*l); + p->keep = true; + p->gc_trigger(r, visited); + } + for (Container **p = cyc_list; p < clptr; p++) + if (!(*p)->keep) + { + delete *p; + mapping.erase(*p); + } +#ifdef GC_INFO + fprintf(stderr, "GC: cycle resolved.\n"); +#endif + force(); +} @@ -5,8 +5,23 @@ #include <map> const int GC_QUEUE_SIZE = 262144; +const size_t GC_CYC_THRESHOLD = 1000; typedef std::map<EvalObj*, size_t> EvalObj2Int; +typedef std::set<EvalObj*> EvalObjSet; + +#define GC_CYC_TRIGGER(ptr) \ +do { \ + if ((ptr) && (ptr)->is_container() && !visited.count(ptr)) \ + visited.insert(*tail++ = (ptr)); \ +} while (0) + +#define GC_CYC_DEC(ptr) \ +do { \ + if ((ptr) && (ptr)->is_container()) \ + static_cast<Container*>(ptr)->gc_refs--; \ +} while (0) + class GarbageCollector { @@ -17,11 +32,11 @@ class GarbageCollector { }; EvalObj2Int mapping; - size_t pend_cnt; PendingEntry *pending_list; public: GarbageCollector(); + void cycle_resolve(); void force(); void expose(EvalObj *ptr); EvalObj *attach(EvalObj *ptr); @@ -35,6 +35,7 @@ void load_file(const char *fname) { fprintf(stderr, "An error occured: %s\n", e.get_msg().c_str()); } gc.force(); + gc.cycle_resolve(); } } @@ -2,6 +2,7 @@ #define MODEL_H #include <string> +#include <set> using std::string; @@ -103,12 +104,14 @@ class EvalObj : public FrameObj { virtual ReprCons *get_repr_cons() = 0; }; +typedef std::set<EvalObj*> EvalObjSet; class Container: public EvalObj { public: + bool keep; size_t gc_refs; - Container(int otype); + Container(int otype = 0); virtual void gc_decrement() = 0; - virtual void gc_trigger(EvalObj ** &tail) = 0; + virtual void gc_trigger(EvalObj ** &tail, EvalObjSet &visited) = 0; }; /** @class RetAddr @@ -28,15 +28,13 @@ Pair::~Pair() { } void Pair::gc_decrement() { - if (car->is_container()) - static_cast<Container*>(car)->gc_refs--; - if (cdr->is_container()) - static_cast<Container*>(cdr)->gc_refs--; + GC_CYC_DEC(car); + GC_CYC_DEC(cdr); } -void Pair::gc_trigger(EvalObj ** &tail) { - *tail++ = car; - *tail++ = cdr; +void Pair::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) { + GC_CYC_TRIGGER(car); + GC_CYC_TRIGGER(cdr); } ReprCons *Pair::get_repr_cons() { @@ -59,7 +57,10 @@ SymObj::SymObj(const string &str) : return new ReprStr(val); } -OptObj::OptObj() : EvalObj(CLS_SIM_OBJ | CLS_OPT_OBJ) {} +OptObj::OptObj() : Container(CLS_SIM_OBJ | CLS_OPT_OBJ) {} + +void OptObj::gc_decrement() {} +void OptObj::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) {} ProcObj::ProcObj(Pair *_body, Environment *_envt, EvalObj *_params) : OptObj(), body(_body), params(_params), envt(_envt) { @@ -114,6 +115,18 @@ Pair *ProcObj::call(Pair *_args, Environment * &genvt, return body; // Move pc to the proc entry point } +void ProcObj::gc_decrement() { + GC_CYC_DEC(body); + GC_CYC_DEC(params); + GC_CYC_DEC(envt); +} + +void ProcObj::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) { + GC_CYC_TRIGGER(body); + GC_CYC_TRIGGER(params); + GC_CYC_TRIGGER(envt); +} + ReprCons *ProcObj::get_repr_cons() { return new ReprStr("#<Procedure>"); } @@ -268,7 +281,8 @@ ReprCons *BuiltinProcObj::get_repr_cons() { return new ReprStr("#<Builtin Procedure: " + name + ">"); } -Environment::Environment(Environment *_prev_envt) : prev_envt(_prev_envt) { +Environment::Environment(Environment *_prev_envt) : + Container(), prev_envt(_prev_envt) { gc.attach(prev_envt); } @@ -283,6 +297,20 @@ ReprCons *Environment::get_repr_cons() { return new ReprStr("#<Environment>"); } +void Environment::gc_decrement() { + GC_CYC_DEC(prev_envt); + for (Str2EvalObj::iterator it = binding.begin(); + it != binding.end(); it++) + GC_CYC_DEC(it->second); +} + +void Environment::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) { + GC_CYC_TRIGGER(prev_envt); + for (Str2EvalObj::iterator it = binding.begin(); + it != binding.end(); it++) + GC_CYC_TRIGGER(it->second); +} + bool Environment::add_binding(SymObj *sym_obj, EvalObj *eval_obj, bool def) { bool found = false; string name(sym_obj->val); @@ -337,7 +365,7 @@ EvalObj *Environment::get_obj(EvalObj *obj) { Continuation::Continuation(Environment *_envt, Pair *_pc, Continuation *_prev_cont, Pair *_proc_body) : - prev_cont(_prev_cont), envt(_envt), pc(_pc), proc_body(_proc_body) { + Container(), prev_cont(_prev_cont), envt(_envt), pc(_pc), proc_body(_proc_body) { gc.attach(prev_cont); gc.attach(envt); } @@ -347,6 +375,16 @@ Continuation::~Continuation() { gc.expose(envt); } +void Continuation::gc_decrement() { + GC_CYC_DEC(prev_cont); + GC_CYC_DEC(envt); +} + +void Continuation::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) { + GC_CYC_TRIGGER(prev_cont); + GC_CYC_TRIGGER(envt); +} + ReprCons *Continuation::get_repr_cons() { return new ReprStr("#<Continuation>"); } @@ -54,7 +54,7 @@ class Pair : public Container {/*{{{*/ ~Pair(); ReprCons *get_repr_cons(); void gc_decrement(); - void gc_trigger(EvalObj ** &tail); + void gc_trigger(EvalObj ** &tail, EvalObjSet &visited); };/*}}}*/ /** @class EmptyList @@ -137,7 +137,7 @@ class Continuation; /** @class OptObj * "Operators" in general sense */ -class OptObj: public EvalObj {/*{{{*/ +class OptObj: public Container {/*{{{*/ public: OptObj(); /** @@ -150,6 +150,9 @@ class OptObj: public EvalObj {/*{{{*/ */ virtual Pair *call(Pair *args, Environment * &envt, Continuation * &cont, FrameObj ** &top_ptr) = 0; + virtual void gc_decrement(); + virtual void gc_trigger(EvalObj ** &tail, EvalObjSet &visited); + };/*}}}*/ /** @class ProcObj @@ -170,6 +173,9 @@ class ProcObj: public OptObj {/*{{{*/ Pair *call(Pair *args, Environment * &envt, Continuation * &cont, FrameObj ** &top_ptr); ReprCons *get_repr_cons(); + + void gc_decrement(); + void gc_trigger(EvalObj ** &tail, EvalObjSet &visited); };/*}}}*/ /** @class SpecialOptObj @@ -331,7 +337,7 @@ class PromObj: public EvalObj {/*{{{*/ /** @class Environment * The environment of current evaluation, i.e. the local variable binding */ -class Environment : public EvalObj{/*{{{*/ +class Environment : public Container{/*{{{*/ private: Environment *prev_envt; /**< Pointer to the upper-level environment */ Str2EvalObj binding; /**< Store all pairs of identifier and its @@ -354,6 +360,9 @@ class Environment : public EvalObj{/*{{{*/ * */ EvalObj *get_obj(EvalObj *obj); ReprCons *get_repr_cons(); + + void gc_decrement(); + void gc_trigger(EvalObj ** &tail, EvalObjSet &visited); };/*}}}*/ /** @class Continuation @@ -361,7 +370,7 @@ class Environment : public EvalObj{/*{{{*/ * being made (Behave like a stack frame in C). When the call has accomplished, * the system will restore all the registers according to the continuation. */ -class Continuation : public EvalObj {/*{{{*/ +class Continuation : public Container {/*{{{*/ public: /** Linking the previous continuation on the chain */ Continuation *prev_cont; @@ -377,6 +386,9 @@ class Continuation : public EvalObj {/*{{{*/ Pair *proc_body); ~Continuation(); ReprCons *get_repr_cons(); + + void gc_decrement(); + void gc_trigger(EvalObj ** &tail, EvalObjSet &visited); };/*}}}*/ /** @class InexactNumObj |