hash: some streamlining in weak table processing.

* gc.c (mark_obj_norec): New function. Just marks
an object reachable without recursing over its
sub-objects.
(gc_mark_norec): New function.

* gc.h (gc_mark_norec): Declared.

* hash.c (do_weak_tables): Cache the table, mask and
vector pointer in a local variable, since these pointers
are not expected to change across function calls, and
can go into registers.
When visiting an entry that should be reachable, we
mark that entry immediately, and also use the new
gc_mark_norec function to mark the chain cons cell
reachable.  I.e. we mark the chain backbone cons,
and that cons' car field, that being the entry.
Thus by the time we march through the chain, we
have marked all of it. Thus, the table entries don't
have to be iterated and marked any more. We use
gc_mark_norec to mark the table, and explicitly mark
its two special slots. The upshot of all this is that
we don't have to make an extra pass over the table,
and the chains, to mark things; we combine the marking
with the expunging of weak values.

3 files changed, 67 insertions, 10 deletions

diff --git a/gc.c b/gc.c
index eafc354c..5fbf5c88 100644
--- a/gc.c
+++ b/gc.c
@@ -497,6 +497,43 @@ tail_call:
   assert (0 && "corrupt type field");
 }
 
+static void mark_obj_norec(val obj)
+{
+  type_t t;
+
+  if (!is_ptr(obj))
+    return;
+
+  t = obj->t.type;
+
+  if ((t & REACHABLE) != 0)
+    return;
+
+#if CONFIG_GEN_GC
+  if (!full_gc && obj->t.gen > 0)
+    return;
+#endif
+
+  if ((t & FREE) != 0)
+    abort();
+
+#if CONFIG_GEN_GC
+  if (obj->t.gen == -1)
+    obj->t.gen = 0;  /* Will be promoted to generation 1 by sweep_one */
+#endif
+
+  obj->t.type = convert(type_t, t | REACHABLE);
+
+#if CONFIG_EXTRA_DEBUGGING
+  if (obj == break_obj) {
+#if HAVE_VALGRIND
+    VALGRIND_PRINTF_BACKTRACE("object %p marked\n", convert(void *, obj));
+#endif
+    breakpt();
+  }
+#endif
+}
+
 void cobj_mark_op(val obj)
 {
   (void) obj;
@@ -959,6 +996,11 @@ void gc_mark(val obj)
   mark_obj(obj);
 }
 
+void gc_mark_norec(val obj)
+{
+  mark_obj_norec(obj);
+}
+
 void gc_conservative_mark(val maybe_obj)
 {
   mark_obj_maybe(maybe_obj);
diff --git a/gc.h b/gc.h
index e89e695a..464268bf 100644
--- a/gc.h
+++ b/gc.h
@@ -36,6 +36,7 @@ void gc(void);
 int gc_state(int);
 int gc_inprogress(void);
 void gc_mark(val);
+void gc_mark_norec(val obj);
 void gc_conservative_mark(val);
 void gc_mark_mem(val *low, val *high);
 int gc_is_reachable(val);
diff --git a/hash.c b/hash.c
index f258bcb7..c5db4941 100644
--- a/hash.c
+++ b/hash.c
@@ -1357,11 +1357,15 @@ static void do_weak_tables(void)
 
   for (; h != 0; h = h->next) {
     ucnum i, c = 0;
+    val table = h->table;
+    val *vec = table->v.vec;
+    ucnum mask = h->mask;
+
     /* The table of a weak hash was spuriously reached by conservative GC;
        it's a waste of time doing weak processing, since all keys and
        values have been transitively marked as reachable; and so we
        won't find anything to remove. */
-    if (gc_is_reachable(h->table))
+    if (gc_is_reachable(table))
       continue;
 
     switch (h->wkopt) {
@@ -1371,8 +1375,8 @@ static void do_weak_tables(void)
     case hash_weak_keys:
       /* Sweep through all entries. Delete any which have keys
          that are garbage. */
-      for (i = 0; i <= h->mask; i++) {
-        val *pchain = &h->table->v.vec[i];
+      for (i = 0; i <= mask; i++) {
+        val *pchain = &vec[i];
         val *iter;
 
         for (iter = pchain; *iter; ) {
@@ -1384,6 +1388,8 @@ static void do_weak_tables(void)
               breakpt();
 #endif
           } else {
+            gc_mark(entry);
+            gc_mark_norec(*iter);
             iter = us_cdr_p(*iter);
             c++;
           }
@@ -1393,8 +1399,8 @@ static void do_weak_tables(void)
     case hash_weak_vals:
       /* Sweep through all entries. Delete any which have values
          that are garbage. */
-      for (i = 0; i <= h->mask; i++) {
-        val *pchain = &h->table->v.vec[i];
+      for (i = 0; i <= mask; i++) {
+        val *pchain = &vec[i];
         val *iter;
 
         for (iter = pchain; *iter; ) {
@@ -1406,6 +1412,8 @@ static void do_weak_tables(void)
               breakpt();
 #endif
           } else {
+            gc_mark(entry);
+            gc_mark_norec(*iter);
             iter = us_cdr_p(*iter);
             c++;
           }
@@ -1415,8 +1423,8 @@ static void do_weak_tables(void)
     case hash_weak_and:
       /* Sweep through all entries. Delete any which have keys
          and values that are garbage. */
-      for (i = 0; i <= h->mask; i++) {
-        val *pchain = &h->table->v.vec[i];
+      for (i = 0; i <= mask; i++) {
+        val *pchain = &vec[i];
         val *iter;
 
         for (iter = pchain; *iter; ) {
@@ -1430,6 +1438,8 @@ static void do_weak_tables(void)
               breakpt();
 #endif
           } else {
+            gc_mark(entry);
+            gc_mark_norec(*iter);
             iter = us_cdr_p(*iter);
             c++;
           }
@@ -1439,8 +1449,8 @@ static void do_weak_tables(void)
     case hash_weak_or:
       /* Sweep through all entries. Delete any which have keys
          or values that are garbage. */
-      for (i = 0; i <= h->mask; i++) {
-        val *pchain = &h->table->v.vec[i];
+      for (i = 0; i <= mask; i++) {
+        val *pchain = &vec[i];
         val *iter;
 
         for (iter = pchain; *iter; ) {
@@ -1454,6 +1464,8 @@ static void do_weak_tables(void)
               breakpt();
 #endif
           } else {
+            gc_mark(entry);
+            gc_mark_norec(*iter);
             iter = us_cdr_p(*iter);
             c++;
           }
@@ -1463,7 +1475,9 @@ static void do_weak_tables(void)
     }
 
     /* Garbage is gone now. Seal things by marking the vector. */
-    gc_mark(h->table);
+    gc_mark_norec(table);
+    gc_mark(vec[vec_alloc]);
+    gc_mark(vec[vec_length]);
     h->count = c;
   }