significant improvement on gc efficiency

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<Container*>(it->first);
-            (*clptr++ = p)->gc_refs = it->second;   // init the count
+            Container *p = static_cast<Container*>(*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 <map>
 
-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<EvalObj*, size_t> EvalObj2Int;
 typedef std::set<EvalObj*> 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<EvalObj*> 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
                 {