GC: marking traversal and pure symbols

[Dmitry Antipov]

Here is another thing I've observed within GC.

Depends on the structure of a Lisp world, from 70 to 80 percents of a symbols
has the value of Qunbound, 50 - 60 % has function value Qunbound and 60 - 70 %
has nil property list. These constraints adds some overload to marking traversal
since Qnil and Qunbound will be reached very often, their mark bits will be 
checked
again and again, etc. (Note Qnil is also reachable from a lot of other objects).

This overload may be partially avoided by allocating Qunbound and Qnil from pure
space. In this case, the number of times when the marking traversal reaches them
will be the same, but mark_object will returns just after a fast check for pure
object (which is performed anyway) without additional type and GC mark bit check
for an object passed.

For a typical workloads involving an intensive Lisp evaluations, marking time
may be reduced with 0.5 - 2 %, or from ~100 to ~600 usecs (3 GHz P4) per GC,
at the cost of having just 2 symbols in pure space.

Dmitry

Index: alloc.c
===================================================================
RCS file: /sources/emacs/emacs/src/alloc.c,v
retrieving revision 1.410
diff -u -r1.410 alloc.c
--- alloc.c     8 Jun 2007 19:59:46 -0000       1.410
+++ alloc.c     5 Jul 2007 13:11:27 -0000
@@ -3237,6 +3237,23 @@
   n_symbol_blocks = 0;
 }
 
+/* Initialize symbol fields to default values.  */
+
+static INLINE void
+symbol_init (sym, name)
+     struct Lisp_Symbol *sym;
+     Lisp_Object name;
+{
+  sym->xname = name;
+  sym->plist = Qnil;
+  sym->value = Qunbound;
+  sym->function = Qunbound;
+  sym->next = 0;
+  sym->gcmarkbit = 0;
+  sym->interned = SYMBOL_UNINTERNED;
+  sym->constant = 0;
+  sym->indirect_variable = 0;
+}
 
 DEFUN ("make-symbol", Fmake_symbol, Smake_symbol, 1, 1, 0,
        doc: /* Return a newly allocated uninterned symbol whose name is NAME.
@@ -3281,15 +3298,7 @@
 #endif
 
   p = XSYMBOL (val);
-  p->xname = name;
-  p->plist = Qnil;
-  p->value = Qunbound;
-  p->function = Qunbound;
-  p->next = NULL;
-  p->gcmarkbit = 0;
-  p->interned = SYMBOL_UNINTERNED;
-  p->constant = 0;
-  p->indirect_variable = 0;
+  symbol_init (p, name);
   consing_since_gc += sizeof (struct Lisp_Symbol);
   symbols_consed++;
   return val;
@@ -4956,6 +4965,21 @@
   return new;
 }
 
+/* Return a symbol allocated from pure space.  */
+
+Lisp_Object
+make_pure_symbol (name)
+     Lisp_Object name;
+{
+  Lisp_Object symbol;
+  struct Lisp_Symbol *sym;
+
+  sym = (struct Lisp_Symbol *) pure_alloc (sizeof *sym, Lisp_Symbol);
+  symbol_init (sym, name);
+  XSETSYMBOL (symbol, sym);
+  return symbol;
+}
+
 
 DEFUN ("purecopy", Fpurecopy, Spurecopy, 1, 1, 0,
        doc: /* Make a copy of object OBJ in pure storage.
Index: lisp.h
===================================================================
RCS file: /sources/emacs/emacs/src/lisp.h,v
retrieving revision 1.577
diff -u -r1.577 lisp.h
--- lisp.h      8 Jun 2007 19:56:24 -0000       1.577
+++ lisp.h      5 Jul 2007 13:11:27 -0000
@@ -2582,6 +2582,7 @@
 extern Lisp_Object make_string_from_bytes P_ ((const char *, int, int));
 extern Lisp_Object make_specified_string P_ ((const char *, int, int, int));
 EXFUN (Fpurecopy, 1);
+extern Lisp_Object make_pure_symbol P_ ((Lisp_Object));
 extern Lisp_Object make_pure_string P_ ((char *, int, int, int));
 extern Lisp_Object pure_cons P_ ((Lisp_Object, Lisp_Object));
 extern Lisp_Object make_pure_vector P_ ((EMACS_INT));
Index: lread.c
===================================================================
RCS file: /sources/emacs/emacs/src/lread.c,v
retrieving revision 1.371
diff -u -r1.371 lread.c
--- lread.c     8 Jun 2007 19:57:46 -0000       1.371
+++ lread.c     5 Jul 2007 13:11:28 -0000
@@ -3602,7 +3602,7 @@
 
   XSETFASTINT (oblength, OBARRAY_SIZE);
 
-  Qnil = Fmake_symbol (make_pure_string ("nil", 3, 3, 0));
+  Qnil = make_pure_symbol (make_pure_string ("nil", 3, 3, 0));
   Vobarray = Fmake_vector (oblength, make_number (0));
   initial_obarray = Vobarray;
   staticpro (&initial_obarray);
@@ -3617,7 +3617,7 @@
   tem = &XVECTOR (Vobarray)->contents[hash];
   *tem = Qnil;
 
-  Qunbound = Fmake_symbol (make_pure_string ("unbound", 7, 7, 0));
+  Qunbound = make_pure_symbol (make_pure_string ("unbound", 7, 7, 0));
   XSYMBOL (Qnil)->function = Qunbound;
   XSYMBOL (Qunbound)->value = Qunbound;
   XSYMBOL (Qunbound)->function = Qunbound;