(gc_sweep): Check cons cell mark bits word by word

and optimize the case where they are all 1.

2 files changed, 50 insertions, 17 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index 1ee960f80c4..8356d0ea04f 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,8 +1,13 @@
+2007-09-23  Dmitry Antipov  <dmantipov@yandex.ru>
+
+        * alloc.c (gc_sweep): Check cons cell mark bits word by word
+        and optimize the case where they are all 1.
+
 2007-09-23  Johannes Weiner  <hannes@saeurebad.de>
 
-        * lisp.h (abs): Define if unknown.
-        * keyboard.c, sound.c, w32term.c, xfaces.c, xterm.c: Don't
-        define abs now it's in lisp.h.
+        * lisp.h (abs): Define if not defined.
+        * keyboard.c, sound.c, w32term.c, xfaces.c, xterm.c:
+        Don't define `abs', since it's defined in lisp.h.
 
 2007-09-22  Eli Zaretskii  <eliz@gnu.org>
 
diff --git a/src/alloc.c b/src/alloc.c
index 2599d5c8ad8..9ba21c2c47a 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -6028,23 +6028,51 @@ gc_sweep ()
 
     for (cblk = cons_block; cblk; cblk = *cprev)
       {
-        register int i;
+        register int i = 0;
         int this_free = 0;
-        for (i = 0; i < lim; i++)
-          if (!CONS_MARKED_P (&cblk->conses[i]))
-            {
-              this_free++;
-              cblk->conses[i].u.chain = cons_free_list;
-              cons_free_list = &cblk->conses[i];
+        int ilim = (lim + BITS_PER_INT - 1) / BITS_PER_INT;
+
+        /* Scan the mark bits an int at a time.  */
+        for (i = 0; i <= ilim; i++)
+          {
+            if (cblk->gcmarkbits[i] == -1)
+              {
+                /* Fast path - all cons cells for this int are marked.  */
+                cblk->gcmarkbits[i] = 0;
+                num_used += BITS_PER_INT;
+              }
+            else
+              {
+                /* Some cons cells for this int are not marked.
+                   Find which ones, and free them.  */
+                int start, pos, stop;
+
+                start = i * BITS_PER_INT;
+                stop = lim - start;
+                if (stop > BITS_PER_INT)
+                  stop = BITS_PER_INT;
+                stop += start;
+
+                for (pos = start; pos < stop; pos++)
+                  {
+                    if (!CONS_MARKED_P (&cblk->conses[pos]))
+                      {
+                        this_free++;
+                        cblk->conses[pos].u.chain = cons_free_list;
+                        cons_free_list = &cblk->conses[pos];
 #if GC_MARK_STACK
-              cons_free_list->car = Vdead;
+                        cons_free_list->car = Vdead;
 #endif
-            }
-          else
-            {
-              num_used++;
-              CONS_UNMARK (&cblk->conses[i]);
-            }
+                      }
+                    else
+                      {
+                        num_used++;
+                        CONS_UNMARK (&cblk->conses[pos]);
+                      }
+                  }
+              }
+          }
+
         lim = CONS_BLOCK_SIZE;
         /* If this block contains only free conses and we have already
            seen more than two blocks worth of free conses then deallocate