GC: marking traversal and pure symbols

GC: marking traversal and pure symbols

[Dmitry Antipov]

[-- Attachment #1: Type: text/plain, Size: 1013 bytes --]

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

[-- Attachment #2: pure_qunbound_qnil.patch --]
[-- Type: text/plain, Size: 3322 bytes --]

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;

[-- Attachment #3: Type: text/plain, Size: 142 bytes --]

_______________________________________________
Emacs-devel mailing list
Emacs-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/emacs-devel

Re: GC: marking traversal and pure symbols

[Richard Stallman]

We can't make Qnil pure, because its plist can be written.
(It can also be defined as a function, though that would be an
ugly thing to do.)

However, we could make Qunbound pure, since it is just a token, not a
real symbol.  It is used only for EQ comparisons at C level.

Would someone like to try that?

Re: GC: marking traversal and pure symbols

[David Kastrup]

Richard Stallman <rms@gnu.org> writes:

> We can't make Qnil pure, because its plist can be written.
> (It can also be defined as a function, though that would be an
> ugly thing to do.)

Would it not make sense to restrict the purity notion to the value
cell of a symbol?

What would be the bad consequences of that?

-- 
David Kastrup

Re: GC: marking traversal and pure symbols

[Andreas Schwab]

David Kastrup <dak@gnu.org> writes:

> Richard Stallman <rms@gnu.org> writes:
>
>> We can't make Qnil pure, because its plist can be written.
>> (It can also be defined as a function, though that would be an
>> ugly thing to do.)
>
> Would it not make sense to restrict the purity notion to the value
> cell of a symbol?

It wouldn't buy us anything, since the value of Qnil is nil.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: GC: marking traversal and pure symbols

[Ken Raeburn]

On Jul 6, 2007, at 00:38, Richard Stallman wrote:
> We can't make Qnil pure, because its plist can be written.
> (It can also be defined as a function, though that would be an
> ugly thing to do.)

I've seen that done, many years ago -- and the person who did it ran  
into interesting problems.  I think there was some Emacs code shipped  
that had a loop over a list testing to see if the car of the list was  
a function, or something like that -- depending on the fact that nil  
doesn't (normally) have a function binding to break the loop.  I have  
no idea if the problem is still present.

It wouldn't strike me as a bad thing to make the function slot of  
Qnil unsettable this way...

Ken

Re: GC: marking traversal and pure symbols

[Andreas Schwab]

Ken Raeburn <raeburn@raeburn.org> writes:

> It wouldn't strike me as a bad thing to make the function slot of Qnil
> unsettable this way...

That is already impossible.

ELISP> (defun nil () nil)
*** Eval error ***  Attempt to set a constant symbol: nil

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: GC: marking traversal and pure symbols

[Richard Stallman]

    Would it not make sense to restrict the purity notion to the value
    cell of a symbol?

On some platforms, pure storage is (or at least was) stored in
read-only memory.  If nil is in read-only memory, we cannot make
its plist cell writable.