Changeset 8369

Timestamp:

Jan 29, 2008, 5:50:19 PM (17 years ago)

Author:

Gary Byers

Message:

Implement an alternate approach to weak-hash-table processing
(the alternate approach is faster but doesn't handle circularity.)
Toggle between the traditional and new approaches (mostly as a
way of stress-testing.)

Location:

trunk/source/lisp-kernel

Files:

• gc-common.c (modified) (10 diffs)
• gc.h (modified) (3 diffs)
• x86-gc.c (modified) (5 diffs)

trunk/source/lisp-kernel/gc-common.c

@@ -89 +89 @@
 natural GCndnodes_in_area = 0, GCndynamic_dnodes_in_area = 0;
 LispObj GCweakvll = (LispObj)NULL;
+LispObj GCdwsweakvll = (LispObj)NULL;
 LispObj GCephemeral_low = 0;
 natural GCn_ephemeral_dnodes = 0;
@@ -210 +211 @@
     dnode,
     npairs = (header_element_count(hashp->header) - 
-              ((sizeof(hash_table_vector_header)/sizeof(LispObj)) -1)) >> 1;
+              (hash_table_vector_header_count -1)) >> 1;
   LispObj *pairp = (LispObj*) (hashp+1), weakelement;
   Boolean 
@@ -235 +236 @@
     pairp += 2;
   }
-}    
-    
+}
+
+void
+traditional_dws_mark_htabv(LispObj htabv)
+{
+  /* Do nothing, just add htabv to GCweakvll */
+  LispObj *base = (LispObj *) ptr_from_lispobj(untag(htabv));
+  
+  deref(base,1) = GCweakvll;
+  GCweakvll = htabv;
+}
+
+void
+ncircle_dws_mark_htabv(LispObj htabv)
+{
+  /* Do nothing, just add htabv to GCdwsweakvll */
+  LispObj *base = (LispObj *) ptr_from_lispobj(untag(htabv));
+  
+  deref(base,1) = GCdwsweakvll;
+  GCdwsweakvll = htabv;
+}
+
+void
+traditional_mark_weak_htabv(LispObj htabv)
+{
+  int i, skip = hash_table_vector_header_count;;
+
+  for (i = 2; i <= skip; i++) {
+    rmark(deref(htabv,i));
+  }
+
+  deref(htabv,1) = GCweakvll;
+  GCweakvll = htabv;
+}
+
+void
+ncircle_mark_weak_htabv(LispObj htabv)
+{
+  int i, skip = hash_table_vector_header_count;;
+  hash_table_vector_header *hashp = (hash_table_vector_header *)(untag(htabv));
+  natural
+    dnode,
+    npairs = (header_element_count(hashp->header) - 
+              (hash_table_vector_header_count - 1)) >> 1;
+  LispObj *pairp = (LispObj*) (hashp+1), weakelement;
+  Boolean 
+    weak_on_value = ((hashp->flags & nhash_weak_value_mask) != 0);
+  bitvector markbits = GCmarkbits;
+  int tag;
+
+  for (i = 2; i <= skip; i++) {
+    rmark(deref(htabv,i));
+  }
+  
+  if (!weak_on_value) {
+    pairp++;
+  }
+  /* unconditionally mark the non-weak element of each pair */
+  while (npairs--) {
+    rmark(*pairp);
+    pairp += 2;
+  }
+
+  deref(htabv,1) = GCweakvll;
+  GCweakvll = htabv;
+}
 
 
@@ -249 +314 @@
     weak_value = ((flags & nhash_weak_value_mask) != 0);
   int 
-    skip = (sizeof(hash_table_vector_header)/sizeof(LispObj))-1,
+    skip = hash_table_vector_header_count-1,
     key_tag,
     val_tag,
@@ -351 +416 @@
   
 void
-markhtabvs()
+traditional_markhtabvs()
 {
   LispObj this, header, pending;
@@ -389 +454 @@
             marked_new = true;
           }
-        } else {
-          deref(this,1) = (LispObj)NULL;
-          for (i = 2; i <= elements; i++) {
-            mark_root(deref(this,i));
-          }
         } 
       } else {
@@ -440 +500 @@
 
 void
+ncircle_markhtabvs()
+{
+  LispObj this, header, pending = 0;
+  int subtag;
+  bitvector markbits = GCmarkbits;
+  hash_table_vector_header *hashp;
+  Boolean marked_new;
+
+  /* First, process any weak hash tables that may have
+     been encountered by the link-inverting marker; we
+     should have more stack space now. */
+
+  while (GCdwsweakvll) {
+    this = GCdwsweakvll;
+    GCdwsweakvll = deref(this,1);
+    ncircle_mark_weak_htabv(this);
+  }
+
+  while (GCweakvll) {
+    this = GCweakvll;
+    GCweakvll = deref(this,1);
+      
+    header = header_of(this);
+    subtag = header_subtag(header);
+      
+    if (subtag == subtag_weak) {
+      natural weak_type = deref(this,2);
+      deref(this,1) = pending;
+      pending = this;
+      if ((weak_type & population_type_mask) == population_weak_alist) {
+        if (mark_weak_alist(this, weak_type)) {
+          marked_new = true;
+          }
+      }
+    } else if (subtag == subtag_hash_vector) {
+      reaphashv(this);
+    }
+  }
+
+  /* Now, everything's marked that's going to be,  and "pending" is a list
+     of populations.  CDR down that list and free
+     anything that isn't marked.
+     */
+
+  while (pending) {
+    this = pending;
+    pending = deref(this,1);
+    deref(this,1) = (LispObj)NULL;
+
+    subtag = header_subtag(header_of(this));
+    if (subtag == subtag_weak) {
+      reapweakv(this);
+    } else {
+      Bug(NULL, "Bad object on pending list: %s\n", this);
+    }
+  }
+
+  /* Finally, mark the termination lists in all terminatable weak vectors
+     They are now linked together on GCweakvll.
+     This is where to store  lisp_global(TERMINATION_LIST) if we decide to do that,
+     but it will force terminatable popualations to hold on to each other
+     (set TERMINATION_LIST before clearing GCweakvll, and don't clear deref(this,1)).
+     */
+  pending = GCweakvll;
+  GCweakvll = (LispObj)NULL;
+  while (pending) {
+    this = pending;
+    pending = deref(this,1);
+    deref(this,1) = (LispObj)NULL;
+    mark_root(deref(this,1+3));
+  }
+}
+
+void
 mark_tcr_tlb(TCR *tcr)
 {
@@ -568 +702 @@
   }
   return c;
+}
+
+weak_mark_fun dws_mark_weak_htabv = traditional_dws_mark_htabv;
+weak_mark_fun mark_weak_htabv = traditional_mark_weak_htabv;
+weak_process_fun markhtabvs = traditional_markhtabvs;
+
+void
+install_weak_mark_functions(int set) {
+  switch(set) {
+  case 0:
+  default:
+    dws_mark_weak_htabv = traditional_dws_mark_htabv;
+    mark_weak_htabv = traditional_mark_weak_htabv;
+    markhtabvs = traditional_markhtabvs;
+    break;
+  case 1:
+    dws_mark_weak_htabv = ncircle_dws_mark_htabv;
+    mark_weak_htabv = ncircle_mark_weak_htabv;
+    markhtabvs = ncircle_markhtabvs;
+    break;
+  }
 }
 
@@ -834 +989 @@
 #endif
 
+int weak_hash_toggle = 0;
+
 void 
 gc(TCR *tcr, signed_natural param)
@@ -849 +1006 @@
   TCR *other_tcr;
   natural static_dnodes;
+
+  install_weak_mark_functions(weak_hash_toggle);
+  weak_hash_toggle = 1 - weak_hash_toggle;
 
 #ifndef FORCE_DWS_MARK

trunk/source/lisp-kernel/gc.h

@@ -147 +147 @@
 LispObj GCarealow, GCareadynamiclow;
 natural GCndnodes_in_area, GCndynamic_dnodes_in_area;
-LispObj GCweakvll;
+LispObj GCweakvll,GCdwsweakvll;
 LispObj GCephemeral_low;
 natural GCn_ephemeral_dnodes;
@@ -165 +165 @@
 Boolean mark_weak_hash_vector(hash_table_vector_header *hashp, natural elements);
 Boolean mark_weak_alist(LispObj weak_alist, int weak_type);
-void markhtabvs(void);
 void mark_tcr_tlb(TCR *);
 void mark_tcr_xframes(TCR *);
@@ -185 +184 @@
 /* backend-interface */
 
+typedef void (*weak_mark_fun) (LispObj);
+weak_mark_fun mark_weak_htabv, dws_mark_weak_htabv;
+
+typedef void (*weak_process_fun)(void);
+
+weak_process_fun markhtabvs;
+
+
+#define hash_table_vector_header_count (sizeof(hash_table_vector_header)/sizeof(LispObj))
+
 void mark_root(LispObj);
+void rmark(LispObj);
 void mark_xp(ExceptionInformation *);
 LispObj dnode_forwarding_address(natural, int);

trunk/source/lisp-kernel/x86-gc.c

@@ -325 +325 @@
           ((hash_table_vector_header *) base)->cache_key = undefined;
           ((hash_table_vector_header *) base)->cache_value = lisp_nil;
-          deref(ptr_to_lispobj(base),1) = GCweakvll;
-          GCweakvll = n;
+          mark_weak_htabv(n);
           return;
         }
@@ -494 +493 @@
           ((hash_table_vector_header *) base)->cache_key = undefined;
           ((hash_table_vector_header *) base)->cache_value = lisp_nil;
-          deref(ptr_to_lispobj(base),1) = GCweakvll;
-          GCweakvll = n;
+          mark_weak_htabv(n);
           return;
         }
@@ -734 +732 @@
         ((hash_table_vector_header *) base)->cache_key = undefined;
         ((hash_table_vector_header *) base)->cache_value = lisp_nil;
-        deref(ptr_to_lispobj(base),1) = GCweakvll;
-        GCweakvll = this;
-        goto Climb;
+        dws_mark_weak_htabv(this);
+        element_count = hash_table_vector_header_count;
       }
     }
@@ -998 +995 @@
           ((hash_table_vector_header *) start)->cache_key = undefined;
           ((hash_table_vector_header *) start)->cache_value = lisp_nil;
-          start[1] = GCweakvll;
-          GCweakvll = (LispObj) (((natural) start) + fulltag_misc);
+          mark_weak_htabv((LispObj)start);
           element_count = 0;
         }
@@ -1295 +1291 @@
       if ((header_subtag(node) == subtag_hash_vector) &&
           ((((hash_table_vector_header *)p)->flags) & nhash_track_keys_mask)) {
-        natural skip = (sizeof(hash_table_vector_header)/sizeof(LispObj))-1;
+        natural skip = hash_table_vector_header_count-1;
         hashp = (hash_table_vector_header *) p;
         p++;