all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* bug#54698: non-recursive GC marking [PATCH]
@ 2022-04-03 18:40 Mattias Engdegård
  2022-04-04 11:01 ` Lars Ingebrigtsen
  2022-04-04 14:32 ` Andrea Corallo
  0 siblings, 2 replies; 43+ messages in thread
From: Mattias Engdegård @ 2022-04-03 18:40 UTC (permalink / raw)
  To: 54698

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

The GC uses recursion to traverse data structures for marking which imposes a limit to how big (or deeply nested) Lisp data structures can be, and usually results in an immediate Emacs crash without warning when that limit is exceeded.

The attached patch replaces recursion with an explicit stack for most common object types: conses, vectors, records, hash tables, symbols, functions etc. Recursion remains for some less common types (buffers, frames etc) but these are typically not used in quantities to cause a problem.

A side benefit is that GC becomes quite a bit faster as a result. Actual workloads such as byte-compilation are consequently sped up by a small but measurable amount.

The patch is explicitly unfinished in some uninteresting respects to make it easier to read; `process_mark_stack` needs reindenting.


[-- Attachment #2: gc-mark-stack.diff --]
[-- Type: application/octet-stream, Size: 11907 bytes --]

diff --git a/src/alloc.c b/src/alloc.c
index b06dd943ba..b008f45c8c 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -6085,6 +6085,8 @@ maybe_garbage_collect (void)
     garbage_collect ();
 }
 
+static inline bool mark_stack_empty_p (void);
+
 /* Subroutine of Fgarbage_collect that does most of the work.  */
 void
 garbage_collect (void)
@@ -6100,6 +6102,8 @@ garbage_collect (void)
   if (garbage_collection_inhibited)
     return;
 
+  eassert(mark_stack_empty_p ());
+
   /* Record this function, so it appears on the profiler's backtraces.  */
   record_in_backtrace (QAutomatic_GC, 0, 0);
 
@@ -6222,6 +6226,8 @@ garbage_collect (void)
   mark_and_sweep_weak_table_contents ();
   eassert (weak_hash_tables == NULL);
 
+  eassert (mark_stack_empty_p ());
+
   gc_sweep ();
 
   unmark_main_thread ();
@@ -6395,15 +6401,25 @@ mark_glyph_matrix (struct glyph_matrix *matrix)
       }
 }
 
+/* Whether to remember a few of the last marked values for debugging.  */
+#define GC_REMEMBER_LAST_MARKED 0
+
+#if GC_REMEMBER_LAST_MARKED
 enum { LAST_MARKED_SIZE = 1 << 9 }; /* Must be a power of 2.  */
 Lisp_Object last_marked[LAST_MARKED_SIZE] EXTERNALLY_VISIBLE;
 static int last_marked_index;
+#endif
 
+/* Whether to enable the mark_object_loop_halt debugging feature.  */
+#define GC_CDR_COUNT 0
+
+#if GC_CDR_COUNT
 /* For debugging--call abort when we cdr down this many
    links of a list, in mark_object.  In debugging,
    the call to abort will hit a breakpoint.
    Normally this is zero and the check never goes off.  */
 ptrdiff_t mark_object_loop_halt EXTERNALLY_VISIBLE;
+#endif
 
 static void
 mark_vectorlike (union vectorlike_header *header)
@@ -6457,19 +6473,6 @@ mark_char_table (struct Lisp_Vector *ptr, enum pvec_type pvectype)
     }
 }
 
-NO_INLINE /* To reduce stack depth in mark_object.  */
-static Lisp_Object
-mark_compiled (struct Lisp_Vector *ptr)
-{
-  int i, size = ptr->header.size & PSEUDOVECTOR_SIZE_MASK;
-
-  set_vector_marked (ptr);
-  for (i = 0; i < size; i++)
-    if (i != COMPILED_CONSTANTS)
-      mark_object (ptr->contents[i]);
-  return size > COMPILED_CONSTANTS ? ptr->contents[COMPILED_CONSTANTS] : Qnil;
-}
-
 /* Mark the chain of overlays starting at PTR.  */
 
 static void
@@ -6622,63 +6625,115 @@ mark_window (struct Lisp_Vector *ptr)
     (w, mark_discard_killed_buffers (w->next_buffers));
 }
 
-static void
-mark_hash_table (struct Lisp_Vector *ptr)
-{
-  struct Lisp_Hash_Table *h = (struct Lisp_Hash_Table *) ptr;
-
-  mark_vectorlike (&h->header);
-  mark_object (h->test.name);
-  mark_object (h->test.user_hash_function);
-  mark_object (h->test.user_cmp_function);
-  /* If hash table is not weak, mark all keys and values.  For weak
-     tables, mark only the vector and not its contents --- that's what
-     makes it weak.  */
-  if (NILP (h->weak))
-    mark_object (h->key_and_value);
-  else
+/* Entry of the mark stack.  */
+struct mark_entry
+{
+  ptrdiff_t n;		        /* number of values, or 0 if a single value */
+  union {
+    Lisp_Object value;		/* when n = 0 */
+    Lisp_Object *values;	/* when n > 0 */
+  } u;
+};
+
+/* This stack is used during marking for traversing data structures without
+   using C recursion.  */
+struct mark_stack
+{
+  struct mark_entry *stack;	/* base of stack */
+  ptrdiff_t size;		/* allocated size in entries */
+  ptrdiff_t sp;			/* current number of entries */
+};
+
+static struct mark_stack mark_stk = {NULL, 0, 0};
+
+static inline bool
+mark_stack_empty_p (void)
+{
+  return mark_stk.sp <= 0;
+}
+
+/* Pop and return a value from the mark stack (which must be nonempty).  */
+static inline Lisp_Object
+mark_stack_pop (void)
+{
+  eassume (!mark_stack_empty_p ());
+  struct mark_entry *e = &mark_stk.stack[mark_stk.sp - 1];
+  if (e->n == 0)		/* single value */
     {
-      eassert (h->next_weak == NULL);
-      h->next_weak = weak_hash_tables;
-      weak_hash_tables = h;
-      set_vector_marked (XVECTOR (h->key_and_value));
+      --mark_stk.sp;
+      return e->u.value;
     }
+  /* Array of values: pop them left to right, which seems to be slightly
+     faster than right to left.  */
+  e->n--;
+  if (e->n == 0)
+    --mark_stk.sp;		/* last value consumed */
+  return (++e->u.values)[-1];
 }
 
-void
-mark_objects (Lisp_Object *obj, ptrdiff_t n)
+NO_INLINE static void
+grow_mark_stack (void)
 {
-  for (ptrdiff_t i = 0; i < n; i++)
-    mark_object (obj[i]);
+  struct mark_stack *ms = &mark_stk;
+  eassert (ms->sp == ms->size);
+  ptrdiff_t min_incr = ms->sp == 0 ? 8192 : 1;
+  ptrdiff_t oldsize = ms->size;
+  ms->stack = xpalloc (ms->stack, &ms->size, min_incr, -1, sizeof *ms->stack);
+  eassert (ms->sp < ms->size);
 }
 
-/* Determine type of generic Lisp_Object and mark it accordingly.
+/* Push VALUE onto the mark stack.  */
+static inline void
+mark_stack_push_value (Lisp_Object value)
+{
+  if (mark_stk.sp >= mark_stk.size)
+    grow_mark_stack ();
+  mark_stk.stack[mark_stk.sp++] = (struct mark_entry){.n = 0, .u.value = value};
+}
 
-   This function implements a straightforward depth-first marking
-   algorithm and so the recursion depth may be very high (a few
-   tens of thousands is not uncommon).  To minimize stack usage,
-   a few cold paths are moved out to NO_INLINE functions above.
-   In general, inlining them doesn't help you to gain more speed.  */
+/* Push the N values at VALUES onto the mark stack.  */
+static inline void
+mark_stack_push_values (Lisp_Object *values, ptrdiff_t n)
+{
+  eassume (n >= 0);
+  if (n == 0)
+    return;
+  if (mark_stk.sp >= mark_stk.size)
+    grow_mark_stack ();
+  mark_stk.stack[mark_stk.sp++] = (struct mark_entry){.n = n,
+						      .u.values = values};
+}
 
-void
-mark_object (Lisp_Object arg)
+/* Traverse and mark objects on the mark stack above BASE_SP.
+
+   Traversal is depth-first using the mark stack for most common
+   object types.  Recursion is used for other types, in the hope that
+   they are rare enough that C stack usage is kept low.  */
+static void
+process_mark_stack (ptrdiff_t base_sp)
 {
-  register Lisp_Object obj;
-  void *po;
 #if GC_CHECK_MARKED_OBJECTS
   struct mem_node *m = NULL;
 #endif
+#if GC_CDR_COUNT
   ptrdiff_t cdr_count = 0;
+#endif
 
-  obj = arg;
- loop:
+  eassume (mark_stk.sp >= base_sp && base_sp >= 0);
 
-  po = XPNTR (obj);
+  while (mark_stk.sp > base_sp)
+    {
+  // FIXME: reindent loop body
+  Lisp_Object obj = mark_stack_pop ();
+ mark_obj: ;
+  void *po = XPNTR (obj);
   if (PURE_P (po))
-    return;
+    continue;
 
+#if GC_REMEMBER_LAST_MARKED
   last_marked[last_marked_index++] = obj;
   last_marked_index &= LAST_MARKED_SIZE - 1;
+#endif
 
   /* Perform some sanity checks on the objects marked here.  Abort if
      we encounter an object we know is bogus.  This increases GC time
@@ -6781,16 +6836,6 @@ #define CHECK_ALLOCATED_AND_LIVE_SYMBOL()		((void) 0)
 	    mark_buffer ((struct buffer *) ptr);
             break;
 
-          case PVEC_COMPILED:
-            /* Although we could treat this just like a vector, mark_compiled
-               returns the COMPILED_CONSTANTS element, which is marked at the
-               next iteration of goto-loop here.  This is done to avoid a few
-               recursive calls to mark_object.  */
-            obj = mark_compiled (ptr);
-            if (!NILP (obj))
-              goto loop;
-            break;
-
           case PVEC_FRAME:
             mark_frame (ptr);
             break;
@@ -6800,8 +6845,27 @@ #define CHECK_ALLOCATED_AND_LIVE_SYMBOL()		((void) 0)
             break;
 
 	  case PVEC_HASH_TABLE:
-            mark_hash_table (ptr);
-	    break;
+	    {
+	      struct Lisp_Hash_Table *h = (struct Lisp_Hash_Table *)ptr;
+	      ptrdiff_t size = ptr->header.size & PSEUDOVECTOR_SIZE_MASK;
+	      set_vector_marked (ptr);
+	      mark_stack_push_values (ptr->contents, size);
+	      mark_stack_push_value (h->test.name);
+	      mark_stack_push_value (h->test.user_hash_function);
+	      mark_stack_push_value (h->test.user_cmp_function);
+	      if (NILP (h->weak))
+		mark_stack_push_value (h->key_and_value);
+	      else
+		{
+		  /* For weak tables, mark only the vector and not its
+		     contents --- that's what makes it weak.  */
+		  eassert (h->next_weak == NULL);
+		  h->next_weak = weak_hash_tables;
+		  weak_hash_tables = h;
+		  set_vector_marked (XVECTOR (h->key_and_value));
+		}
+	      break;
+	    }
 
 	  case PVEC_CHAR_TABLE:
 	  case PVEC_SUB_CHAR_TABLE:
@@ -6828,11 +6892,11 @@ #define CHECK_ALLOCATED_AND_LIVE_SYMBOL()		((void) 0)
 	      {
 		set_vector_marked (ptr);
 		struct Lisp_Subr *subr = XSUBR (obj);
-		mark_object (subr->native_intspec);
-		mark_object (subr->command_modes);
-		mark_object (subr->native_comp_u);
-		mark_object (subr->lambda_list);
-		mark_object (subr->type);
+		mark_stack_push_value (subr->native_intspec);
+		mark_stack_push_value (subr->command_modes);
+		mark_stack_push_value (subr->native_comp_u);
+		mark_stack_push_value (subr->lambda_list);
+		mark_stack_push_value (subr->type);
 	      }
 #endif
 	    break;
@@ -6841,9 +6905,16 @@ #define CHECK_ALLOCATED_AND_LIVE_SYMBOL()		((void) 0)
 	    emacs_abort ();
 
 	  default:
-	    /* A regular vector, or a pseudovector needing no special
-	       treatment.  */
-	    mark_vectorlike (&ptr->header);
+	    {
+	      /* A regular vector or pseudovector needing no special
+		 treatment.  */
+	      ptrdiff_t size = ptr->header.size;
+	      if (size & PSEUDOVECTOR_FLAG)
+		size &= PSEUDOVECTOR_SIZE_MASK;
+	      set_vector_marked (ptr);
+	      mark_stack_push_values (ptr->contents, size);
+	    }
+	    break;
 	  }
       }
       break;
@@ -6858,16 +6929,16 @@ #define CHECK_ALLOCATED_AND_LIVE_SYMBOL()		((void) 0)
         set_symbol_marked (ptr);
 	/* Attempt to catch bogus objects.  */
 	eassert (valid_lisp_object_p (ptr->u.s.function));
-	mark_object (ptr->u.s.function);
-	mark_object (ptr->u.s.plist);
+	mark_stack_push_value (ptr->u.s.function);
+	mark_stack_push_value (ptr->u.s.plist);
 	switch (ptr->u.s.redirect)
 	  {
-	  case SYMBOL_PLAINVAL: mark_object (SYMBOL_VAL (ptr)); break;
+	  case SYMBOL_PLAINVAL: mark_stack_push_value (SYMBOL_VAL (ptr)); break;
 	  case SYMBOL_VARALIAS:
 	    {
 	      Lisp_Object tem;
 	      XSETSYMBOL (tem, SYMBOL_ALIAS (ptr));
-	      mark_object (tem);
+	      mark_stack_push_value (tem);
 	      break;
 	    }
 	  case SYMBOL_LOCALIZED:
@@ -6898,19 +6969,20 @@ #define CHECK_ALLOCATED_AND_LIVE_SYMBOL()		((void) 0)
 	  break;
 	CHECK_ALLOCATED_AND_LIVE (live_cons_p, MEM_TYPE_CONS);
         set_cons_marked (ptr);
-	/* If the cdr is nil, avoid recursion for the car.  */
-	if (NILP (ptr->u.s.u.cdr))
+	/* Avoid growing the stack if the cdr is nil.
+	   In any case, make sure the car is expanded first.  */
+	if (!NILP (ptr->u.s.u.cdr))
 	  {
-	    obj = ptr->u.s.car;
-	    cdr_count = 0;
-	    goto loop;
+	    mark_stack_push_value (ptr->u.s.u.cdr);
+#if GC_CDR_COUNT
+	    cdr_count++;
+	    if (cdr_count == mark_object_loop_halt)
+	      emacs_abort ();
+#endif
 	  }
-	mark_object (ptr->u.s.car);
-	obj = ptr->u.s.u.cdr;
-	cdr_count++;
-	if (cdr_count == mark_object_loop_halt)
-	  emacs_abort ();
-	goto loop;
+	/* Speedup hack for the common case (successive list elements).  */
+	obj = ptr->u.s.car;
+	goto mark_obj;
       }
 
     case Lisp_Float:
@@ -6930,11 +7002,29 @@ #define CHECK_ALLOCATED_AND_LIVE_SYMBOL()		((void) 0)
       emacs_abort ();
     }
 
+    }
+
 #undef CHECK_LIVE
 #undef CHECK_ALLOCATED
 #undef CHECK_ALLOCATED_AND_LIVE
 }
 
+void
+mark_object (Lisp_Object obj)
+{
+  ptrdiff_t sp = mark_stk.sp;
+  mark_stack_push_value (obj);
+  process_mark_stack (sp);
+}
+
+void
+mark_objects (Lisp_Object *objs, ptrdiff_t n)
+{
+  ptrdiff_t sp = mark_stk.sp;
+  mark_stack_push_values (objs, n);
+  process_mark_stack (sp);
+}
+
 /* Mark the Lisp pointers in the terminal objects.
    Called by Fgarbage_collect.  */
 
-- 
2.32.0 (Apple Git-132)


^ permalink raw reply related	[flat|nested] 43+ messages in thread

end of thread, other threads:[~2022-04-09  0:28 UTC | newest]

Thread overview: 43+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2022-04-03 18:40 bug#54698: non-recursive GC marking [PATCH] Mattias Engdegård
2022-04-04 11:01 ` Lars Ingebrigtsen
2022-04-04 11:16   ` Mattias Engdegård
2022-04-04 11:29     ` Lars Ingebrigtsen
2022-04-04 11:31       ` Lars Ingebrigtsen
2022-04-04 11:38     ` Eli Zaretskii
2022-04-04 11:57       ` Mattias Engdegård
2022-04-04 12:25         ` Eli Zaretskii
2022-04-04 17:18           ` Mattias Engdegård
2022-04-05  1:15     ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-05  8:08       ` Mattias Engdegård
2022-04-05  8:39         ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-05 11:11           ` Mattias Engdegård
2022-04-05 11:26             ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-05 11:43         ` Eli Zaretskii
2022-04-05 12:31           ` Philipp Stephani
2022-04-05 13:12             ` Eli Zaretskii
2022-04-06  4:09               ` Richard Stallman
2022-04-06  5:48                 ` Phil Sainty
2022-04-06 10:59                 ` Eli Zaretskii
2022-04-06 12:05                   ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-06 12:23                     ` Eli Zaretskii
2022-04-06 12:34                       ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-06 14:10                         ` Eli Zaretskii
2022-04-06 12:52                       ` Lars Ingebrigtsen
2022-04-08  4:24                     ` Richard Stallman
2022-04-08  5:49                       ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-08  6:16                         ` Eli Zaretskii
2022-04-08  7:41                           ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-08 11:15                             ` Eli Zaretskii
2022-04-08 11:32                               ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-08 11:55                             ` Lars Ingebrigtsen
2022-04-08 11:58                               ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-08 12:07                                 ` Lars Ingebrigtsen
2022-04-08 12:16                                   ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-04-08 13:07                                     ` Lars Ingebrigtsen
2022-04-09  0:28                                       ` Phil Sainty
2022-04-08 12:13                               ` Eli Zaretskii
2022-04-04 14:32 ` Andrea Corallo
2022-04-04 14:39   ` Mattias Engdegård
2022-04-04 15:44     ` Andrea Corallo
2022-04-04 16:04       ` Mattias Engdegård
2022-04-05  9:10         ` Andrea Corallo

Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.