bug#54698: non-recursive GC marking [PATCH]

bug#54698: non-recursive GC marking [PATCH]

[Mattias Engdegård]

[-- 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)

bug#54698: non-recursive GC marking [PATCH]

[Lars Ingebrigtsen]

Mattias Engdegård <mattiase@acm.org> writes:

> The attached patch replaces recursion with an explicit stack for most
> common object types: conses, vectors, records, hash tables, symbols,
> functions etc.

That's wonderful -- I guess this fixes the segfaults we're seeing with
structures that recurse on the car?

Is there a max stack size?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#54698: non-recursive GC marking [PATCH]

[Mattias Engdegård]

4 apr. 2022 kl. 13.01 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> That's wonderful -- I guess this fixes the segfaults we're seeing with
> structures that recurse on the car?

Yes, it should.

> Is there a max stack size?

No, the mark stack grows as needed. I see no reason to limit the size since it's going to be much smaller than the size of the heap being traced in any case.

bug#54698: non-recursive GC marking [PATCH]

[Lars Ingebrigtsen]

Mattias Engdegård <mattiase@acm.org> writes:

>> Is there a max stack size?
>
> No, the mark stack grows as needed. I see no reason to limit the size
> since it's going to be much smaller than the size of the heap being
> traced in any case.

Sounds good.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#54698: non-recursive GC marking [PATCH]

[Lars Ingebrigtsen]

(bug#31362 and bug#46900 should probably be closed after applying this
patch, I guess.)

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Mon, 4 Apr 2022 13:16:26 +0200
> Cc: 54698@debbugs.gnu.org
> 
> > Is there a max stack size?
> 
> No, the mark stack grows as needed. I see no reason to limit the size since it's going to be much smaller than the size of the heap being traced in any case.

What happens with data that GC relocates, like when it relocates and
compacts string data?  If the relocated data is allocated on the heap
after the simulated stack, the original string data, which is now free
memory, will be "trapped" behind the simulated stack, and 'free' will
be unable to return it to the OS.  This could make the memory
footprint of Emacs larger than it could be.

Was this aspect considered and audited/tested?

bug#54698: non-recursive GC marking [PATCH]

[Mattias Engdegård]

4 apr. 2022 kl. 13.38 skrev Eli Zaretskii <eliz@gnu.org>:

> What happens with data that GC relocates, like when it relocates and
> compacts string data?  If the relocated data is allocated on the heap
> after the simulated stack, the original string data, which is now free
> memory, will be "trapped" behind the simulated stack, and 'free' will
> be unable to return it to the OS.  This could make the memory
> footprint of Emacs larger than it could be.

That effect is unlikely to be visible. I don't think a single (and not very big) allocation would contribute materially to heap fragmentation, given the amount of allocation being made all the time. (But prove me wrong!)

> Was this aspect considered and audited/tested?

Do you have a test case?

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> Feedback-ID:mattiase@acm.or
> From: Mattias Engdegård <mattiase@acm.org>
> Date: Mon, 4 Apr 2022 13:57:54 +0200
> Cc: larsi@gnus.org, 54698@debbugs.gnu.org
> 
> 4 apr. 2022 kl. 13.38 skrev Eli Zaretskii <eliz@gnu.org>:
> 
> > What happens with data that GC relocates, like when it relocates and
> > compacts string data?  If the relocated data is allocated on the heap
> > after the simulated stack, the original string data, which is now free
> > memory, will be "trapped" behind the simulated stack, and 'free' will
> > be unable to return it to the OS.  This could make the memory
> > footprint of Emacs larger than it could be.
> 
> That effect is unlikely to be visible. I don't think a single (and not very big) allocation would contribute materially to heap fragmentation, given the amount of allocation being made all the time. (But prove me wrong!)

I don't need to prove you wrong: if the problem is real, we will hear
about that soon enough.

In principle, even a small allocation can prevent a large free portion
of the arena from being returned to the OS.  And Lisp strings nowadays
tend to be a legion and some quite large in some applications, because
many packages abuse them (instead of using temporary buffers).

bug#54698: non-recursive GC marking [PATCH]

[Mattias Engdegård]

4 apr. 2022 kl. 14.25 skrev Eli Zaretskii <eliz@gnu.org>:

> I don't need to prove you wrong: if the problem is real, we will hear
> about that soon enough.

Yes, you are probably right about that.

4 apr. 2022 kl. 13.31 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> (bug#31362 and bug#46900 should probably be closed after applying this
> patch, I guess.)

Thanks, will do.

Pushed to master (after tidying up).

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Mattias Engdegård <mattiase@acm.org> writes:

> No, the mark stack grows as needed. I see no reason to limit the size
> since it's going to be much smaller than the size of the heap being
> traced in any case.

What happens if it runs out of memory?

The incremental GC I'm working on also has a similar stack for objects
that have not been marked yet, and it also grows dynamically.

If growing the stack fails, it aborts garbage collection and tells the
user to type C-x s and exit Emacs.  Objects are left with mark bits, but
that is the case when Lisp code is allowed to run "between" parts of
garbage collection anyway, and I hopefully did a good enough job fixing
the code that assumed objects cannot have mark bits during regular Lisp
execution.

bug#54698: non-recursive GC marking [PATCH]

[Mattias Engdegård]

5 apr. 2022 kl. 03.15 skrev Po Lu <luangruo@yahoo.com>:

> What happens if it runs out of memory?

Good question! In theory the answer is simple: abort, as with any other failed xmalloc.

In practice, though, malloc probably won't fail at all -- more likely the OS will keep handing out addresses from its 64-bit space and slowly swap itself to death. On Linux, the out-of-memory killer will murder some essential processes at some point. If you have a hard disk you will at least get a premonition of what is going to happen from the rumbling.

But it would take a lot of heap for the mark stack requirements to become that big; it's much more likely that you run out of memory allocating your Lisp objects (or something else) first.

> The incremental GC I'm working on also has a similar stack for objects
> that have not been marked yet, and it also grows dynamically.

That's nice! I'm using a monolithic stack because it's easiest and gives good performance. A segmented stack would be an alternative for extreme memory conditions but the extra segment underflow checks would make the common case slower. (I have a patch for using a segmented stack in the bytecode engine, where it makes more sense and the overhead is lower, but it's still nonzero.)

> If growing the stack fails, it aborts garbage collection and tells the
> user to type C-x s and exit Emacs.

Frankly I wouldn't trust saving buffers to be possible when growing the mark stack wasn't. Have you actually tested this?

>   Objects are left with mark bits, but
> that is the case when Lisp code is allowed to run "between" parts of
> garbage collection anyway, and I hopefully did a good enough job fixing
> the code that assumed objects cannot have mark bits during regular Lisp
> execution.

That requires some careful invariant maintenance but I could see it working. Is the collector generational as well? Otherwise I suppose the total GC cost is higher than before, right?

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Mattias Engdegård <mattiase@acm.org> writes:

> Good question! In theory the answer is simple: abort, as with any
> other failed xmalloc.

I think a failed xmalloc will also make Emacs prompt to "C-x s, then
exit".  But the regular memory_full codepath might not work during
garbage collection.  (Mark bits get left around, for example).

> In practice, though, malloc probably won't fail at all -- more likely
> the OS will keep handing out addresses from its 64-bit space and
> slowly swap itself to death. On Linux, the out-of-memory killer will
> murder some essential processes at some point. If you have a hard disk
> you will at least get a premonition of what is going to happen from
> the rumbling.
>
> But it would take a lot of heap for the mark stack requirements to
> become that big; it's much more likely that you run out of memory
> allocating your Lisp objects (or something else) first.

Indeed.

> That's nice! I'm using a monolithic stack because it's easiest and
> gives good performance. A segmented stack would be an alternative for
> extreme memory conditions but the extra segment underflow checks would
> make the common case slower. (I have a patch for using a segmented
> stack in the bytecode engine, where it makes more sense and the
> overhead is lower, but it's still nonzero.)

I agree.

> Frankly I wouldn't trust saving buffers to be possible when growing
> the mark stack wasn't. Have you actually tested this?

That code wasn't tested in an actual out-of-memory situation yet (it's
too soon to consider this), but hopefully it will work.  I think it
works when running out of memory in general, because otherwise it
wouldn't be what memory_full eventually asks the user to do.

Emacs keeps a small amount of malloc'd "spare memory" around during
normal execution, and frees it when running out of memory, so that some
allocation might be able to continue.  I didn't yet touch that
mechanism, but it should perhaps be replaced by a mechanism that
directly allocates objects out of that spare memory.

> That requires some careful invariant maintenance but I could see it
> working. Is the collector generational as well?

It isn't.

> Otherwise I suppose the total GC cost is higher than before, right?

Yes, the total GC cost is higher than before.  Lisp execution during the
garbage collection is also much slower than otherwise, since (for
starters) a linear search through the page aligned "block" of objects is
used every time a hardware write barrier is hit.  There's a lot of other
low hanging fruit for optimization as well, but it's too early to work
on those, since at present the garbage collector is not even working due
to the recent changes that added a manually managed stack to the
bytecode interpreter.

Thanks.

bug#54698: non-recursive GC marking [PATCH]

[Mattias Engdegård]

5 apr. 2022 kl. 10.39 skrev Po Lu <luangruo@yahoo.com>:

> I think a failed xmalloc will also make Emacs prompt to "C-x s, then
> exit".

Yes, you're probably right. (Never seen it happen myself.)

> That code wasn't tested in an actual out-of-memory situation yet (it's
> too soon to consider this), but hopefully it will work.  I think it
> works when running out of memory in general, because otherwise it
> wouldn't be what memory_full eventually asks the user to do.

Out-of-memory handling is difficult to do correctly and to test, especially on modern systems. You are right to make a reasonable effort at dealing with it but don't go overboard -- at some point effort is better spent on limiting user data loss in other ways (robust auto-save in particular).

>  There's a lot of other
> low hanging fruit for optimization as well, but it's too early to work
> on those, since at present the garbage collector is not even working due
> to the recent changes that added a manually managed stack to the
> bytecode interpreter.

Very sorry about that (but Progress stops for nobody)!
In fact the new bytecode stack should provide more opportunities for efficient GC, but let's discuss that elsewhere.

> Thanks.

You're welcome.

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Mattias Engdegård <mattiase@acm.org> writes:

> Very sorry about that (but Progress stops for nobody)!

No need to apologize, I'm responsible for the work I do in the
background, thanks.

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Tue, 5 Apr 2022 10:08:11 +0200
> Cc: Lars Ingebrigtsen <larsi@gnus.org>, 54698@debbugs.gnu.org
> 
> 5 apr. 2022 kl. 03.15 skrev Po Lu <luangruo@yahoo.com>:
> 
> > What happens if it runs out of memory?
> 
> Good question! In theory the answer is simple: abort, as with any other failed xmalloc.

Emacs isn't supposed to abort when xmalloc runs out of memory.  See
memory_full.

> In practice, though, malloc probably won't fail at all -- more likely the OS will keep handing out addresses from its 64-bit space and slowly swap itself to death. On Linux, the out-of-memory killer will murder some essential processes at some point.

You mean, Emacs fails to know when it approaches the memory limit,
and/or react reasonably when memory_full is called?  That'd be a bug,
IMO.

> But it would take a lot of heap for the mark stack requirements to become that big; it's much more likely that you run out of memory allocating your Lisp objects (or something else) first.

The memory allocated for the simulated stack during GC is
_in_addition_ to what was used for Lisp objects.

> > If growing the stack fails, it aborts garbage collection and tells the
> > user to type C-x s and exit Emacs.
> 
> Frankly I wouldn't trust saving buffers to be possible when growing the mark stack wasn't. Have you actually tested this?

Emacs preserves some memory for that reason.  If that doesn't work, we
should fix it, IMO.  Being able to save your edits when memory is full
is an important safety feature in Emacs.

bug#54698: non-recursive GC marking [PATCH]

[Philipp Stephani]

Am Di., 5. Apr. 2022 um 13:45 Uhr schrieb Eli Zaretskii <eliz@gnu.org>:
> > In practice, though, malloc probably won't fail at all -- more likely the OS will keep handing out addresses from its 64-bit space and slowly swap itself to death. On Linux, the out-of-memory killer will murder some essential processes at some point.
>
> You mean, Emacs fails to know when it approaches the memory limit,
> and/or react reasonably when memory_full is called?  That'd be a bug,
> IMO.

I think this is just how modern OSes behave: they will happily hand
out arbitrary amounts of memory and then kill processes without
warning if they use too much memory. By design, there's nothing these
processes can do about that.

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Philipp Stephani <p.stephani2@gmail.com>
> Date: Tue, 5 Apr 2022 14:31:17 +0200
> Cc: Mattias Engdegård <mattiase@acm.org>, 
> 	Po Lu <luangruo@yahoo.com>, Lars Ingebrigtsen <larsi@gnus.org>, 54698@debbugs.gnu.org
> 
> > You mean, Emacs fails to know when it approaches the memory limit,
> > and/or react reasonably when memory_full is called?  That'd be a bug,
> > IMO.
> 
> I think this is just how modern OSes behave: they will happily hand
> out arbitrary amounts of memory and then kill processes without
> warning if they use too much memory. By design, there's nothing these
> processes can do about that.

That's not my experience.

bug#54698: non-recursive GC marking [PATCH]

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > > I think this is just how modern OSes behave: they will happily hand
  > > out arbitrary amounts of memory and then kill processes without
  > > warning if they use too much memory. By design, there's nothing these
  > > processes can do about that.

  > That's not my experience.

A few weeks ago, when I had too little physical memory for a while,
I found that my machine would start thrashing, and then Linux would
kill a large process.  Fortunately that was IceCat, not Emacs.
A wizard told me it was indeed killing processes without warning,
but at that moment the thrashing process had no way to receive or
act on a warning.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

bug#54698: non-recursive GC marking [PATCH]

[Phil Sainty]

On 2022-04-06 16:09, Richard Stallman wrote:
> A few weeks ago, when I had too little physical memory for a while,
> I found that my machine would start thrashing, and then Linux would
> kill a large process.

Linux does indeed have such a feature.  There is a description here:

https://www.kernel.org/doc/gorman/html/understand/understand016.html

I do not know whether such a feature is common to modern systems
more generally, but the above article says "This is a controversial
part of the [virtual memory system] and it has been suggested that
it be removed on many occasions", so I don't imagine that it's
considered to be a standard approach.

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Richard Stallman <rms@gnu.org>
> Cc: p.stephani2@gmail.com, luangruo@yahoo.com, mattiase@acm.org,
> 	larsi@gnus.org, 54698@debbugs.gnu.org
> Date: Wed, 06 Apr 2022 00:09:25 -0400
> 
>   > > I think this is just how modern OSes behave: they will happily hand
>   > > out arbitrary amounts of memory and then kill processes without
>   > > warning if they use too much memory. By design, there's nothing these
>   > > processes can do about that.
> 
>   > That's not my experience.
> 
> A few weeks ago, when I had too little physical memory for a while,
> I found that my machine would start thrashing, and then Linux would
> kill a large process.  Fortunately that was IceCat, not Emacs.
> A wizard told me it was indeed killing processes without warning,
> but at that moment the thrashing process had no way to receive or
> act on a warning.

You seem to be saying that Emacs on GNU/Linux cannot reliably detect
that it's approaching the memory limit, or have already approached it.
That'd be sad if it were indeed 100% true, and couldn't be alleviated
by some system setting.  (I thought one could use "ulimit -v"?)  Or
maybe Emacs should have its own setting for how much memory is
available, if it can reliably tell how much is being used.

If indeed this cannot be solved on GNU/Linux, it is IMO sad, because
on MS-Windows I was saved several times by memory_full and what's
behind it, when I occasionally needed to visit very large files that
exceeded my system's capacity for Emacs.

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Eli Zaretskii <eliz@gnu.org> writes:

> You seem to be saying that Emacs on GNU/Linux cannot reliably detect
> that it's approaching the memory limit, or have already approached it.
> That'd be sad if it were indeed 100% true, and couldn't be alleviated
> by some system setting.  (I thought one could use "ulimit -v"?)  Or
> maybe Emacs should have its own setting for how much memory is
> available, if it can reliably tell how much is being used.
>
> If indeed this cannot be solved on GNU/Linux, it is IMO sad, because
> on MS-Windows I was saved several times by memory_full and what's
> behind it, when I occasionally needed to visit very large files that
> exceeded my system's capacity for Emacs.

Overcommit can be disabled on GNU/Linux (the relevant knob is
vm.overcommit_memory), which will malloc return an error when there is
no more memory left on the system, thereby triggering memory_full.

malloc can also fail when it runs out of virtual memory, especially on
32-bit systems.

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: rms@gnu.org,  p.stephani2@gmail.com,  mattiase@acm.org,  larsi@gnus.org,
>   54698@debbugs.gnu.org
> Date: Wed, 06 Apr 2022 20:05:14 +0800
> 
> Overcommit can be disabled on GNU/Linux (the relevant knob is
> vm.overcommit_memory), which will malloc return an error when there is
> no more memory left on the system, thereby triggering memory_full.

Then I think we should advise users to do that.

> malloc can also fail when it runs out of virtual memory, especially on
> 32-bit systems.

Why only 32-bit?  If overcommit is disabled, isn't the amount of VM
determined by the sum of physical memory + swap space?  If so, you
could run out of VM on 64-bit systems as well, no?

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Eli Zaretskii <eliz@gnu.org> writes:

> Then I think we should advise users to do that.

Sure, where would a good place to put that advice be?  etc/PROBLEMS
perhaps?

Thanks.

> Why only 32-bit?

Not "only", "especially" 32-bit systems.  They tend to have less virtual
memory available, and the amount of address space available to
individual processes is also very small compared to newer systems.

> If overcommit is disabled, isn't the amount of VM determined by the
> sum of physical memory + swap space?  If so, you could run out of VM
> on 64-bit systems as well, no?

Correct.

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: rms@gnu.org,  p.stephani2@gmail.com,  mattiase@acm.org,  larsi@gnus.org,
>   54698@debbugs.gnu.org
> Date: Wed, 06 Apr 2022 20:34:52 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Then I think we should advise users to do that.
> 
> Sure, where would a good place to put that advice be?  etc/PROBLEMS
> perhaps?

I'd first put that in the node "Memory Full" of the Emacs manual.

bug#54698: non-recursive GC marking [PATCH]

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

>> Overcommit can be disabled on GNU/Linux (the relevant knob is
>> vm.overcommit_memory), which will malloc return an error when there is
>> no more memory left on the system, thereby triggering memory_full.
>
> Then I think we should advise users to do that.

I think it's outside Emacs' scope to advise users how to set up their
operating systems.

(Especially after three decades of Linux -- the kernel has always worked
this way.)

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#54698: non-recursive GC marking [PATCH]

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > Overcommit can be disabled on GNU/Linux (the relevant knob is
  > vm.overcommit_memory), which will malloc return an error when there is
  > no more memory left on the system, thereby triggering memory_full.

Concretely, what is this "knob"?  Is it a per-process variable?  If
so, we could make Emacs set it, with a Lisp function to specify the
value.

What is the precise definition of "no more memory left"?

The thrashing that I observed did not immediately kill any process.
Rather, it continued for minutes before doing so.  So I don't think
there was "no more memory left on the system", because if that had
been the case, Linux would have known it immediately.


-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Richard Stallman <rms@gnu.org> writes:

> Concretely, what is this "knob"?  Is it a per-process variable?  If
> so, we could make Emacs set it, with a Lisp function to specify the
> value.

It's a kernel parameter.  It's not per-process, it applies to the entire
system.  Emacs could set it, but it would typically not have sufficient
privileges to do so.

> What is the precise definition of "no more memory left"?

It's complicated.  I think in addition to checking for free pages, Linux
also tries to reclaim some cached data, and the inode cache, before
determining that there is really no memory left.

> The thrashing that I observed did not immediately kill any process.
> Rather, it continued for minutes before doing so.  So I don't think
> there was "no more memory left on the system", because if that had
> been the case, Linux would have known it immediately.

Yes, the OOM killer typically kicks in before there is really no memory
left.

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: eliz@gnu.org,  p.stephani2@gmail.com,  mattiase@acm.org,
>   larsi@gnus.org,  54698@debbugs.gnu.org
> Date: Fri, 08 Apr 2022 13:49:18 +0800
> 
> Richard Stallman <rms@gnu.org> writes:
> 
> > Concretely, what is this "knob"?  Is it a per-process variable?  If
> > so, we could make Emacs set it, with a Lisp function to specify the
> > value.
> 
> It's a kernel parameter.

AFAIK, it can be set by editing a file.  Details are here:

  https://www.digitalocean.com/community/questions/how-can-i-disable-overcommit_memory
  https://serverfault.com/questions/485798/cent-os-how-do-i-turn-off-or-reduce-memory-overcommitment-and-is-it-safe-to-do

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Eli Zaretskii <eliz@gnu.org> writes:

> AFAIK, it can be set by editing a file.  Details are here:
>
>   https://www.digitalocean.com/community/questions/how-can-i-disable-overcommit_memory
>   https://serverfault.com/questions/485798/cent-os-how-do-i-turn-off-or-reduce-memory-overcommitment-and-is-it-safe-to-do

Yes, but typically you have to be root to write to that file.

How about adding this in the Memory Full node in the Emacs manual?

On GNU/Linux systems, the system does not normally report running out of
memory to Emacs, and can instead randomly kill processes when they run
out of memory.  We recommend that you turn this behavior off, so that
Emacs can respond correctly when it runs out of memory, by becoming the
super user, editing the file @code{/etc/sysctl.conf} to contain the
following lines, and then running the command @code{sysctl -p} as the
super user:

@indentedblock
vm.overcommit_memory=2
vm.overcommit_ratio=0
@end indentedblock

Thanks.

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: rms@gnu.org,  p.stephani2@gmail.com,  mattiase@acm.org,  larsi@gnus.org,
>   54698@debbugs.gnu.org
> Date: Fri, 08 Apr 2022 15:41:07 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > AFAIK, it can be set by editing a file.  Details are here:
> >
> >   https://www.digitalocean.com/community/questions/how-can-i-disable-overcommit_memory
> >   https://serverfault.com/questions/485798/cent-os-how-do-i-turn-off-or-reduce-memory-overcommitment-and-is-it-safe-to-do
> 
> Yes, but typically you have to be root to write to that file.

I'm sure RMS is root, or can become one, on his system.

If you are talking about Emacs doing that on its own, then I don''t
think this is a good idea regardless of privileges, since it isn't an
application's business to change a system-wide setting that affects
the entire OS.

> How about adding this in the Memory Full node in the Emacs manual?

I already said I thought we should do that.

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Eli Zaretskii <eliz@gnu.org> writes:

> I'm sure RMS is root, or can become one, on his system.
>
> If you are talking about Emacs doing that on its own, then I don''t
> think this is a good idea regardless of privileges, since it isn't an
> application's business to change a system-wide setting that affects
> the entire OS.

Yeah, we were discussing having Emacs do that by itself.

>> How about adding this in the Memory Full node in the Emacs manual?
>
> I already said I thought we should do that.

Thanks, will do.

bug#54698: non-recursive GC marking [PATCH]

[Lars Ingebrigtsen]

Po Lu <luangruo@yahoo.com> writes:

> On GNU/Linux systems, the system does not normally report running out of
> memory to Emacs, and can instead randomly kill processes when they run
> out of memory.  We recommend that you turn this behavior off, so that
> Emacs can respond correctly when it runs out of memory, by becoming the
> super user, editing the file @code{/etc/sysctl.conf} to contain the
> following lines, and then running the command @code{sysctl -p} as the
> super user:

I don't think we should recommend doing this.  It has serious
deleterious effects on the operating system, because many programs
written for GNU/Linux depends on the current behaviour (where malloc-ing
basically never ever fails).

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> I don't think we should recommend doing this.  It has serious
> deleterious effects on the operating system, because many programs
> written for GNU/Linux depends on the current behaviour (where malloc-ing
> basically never ever fails).

They will either get killed by the out-of-memory killer when overcommit
is on, or they will abort (or crash) on failed malloc.  IME all except
for some special niche programs work with overcommit off.

bug#54698: non-recursive GC marking [PATCH]

[Lars Ingebrigtsen]

Po Lu <luangruo@yahoo.com> writes:

> They will either get killed by the out-of-memory killer when overcommit
> is on, or they will abort (or crash) on failed malloc.  IME all except
> for some special niche programs work with overcommit off.

Users will see mysterious segfaults that they didn't see before
throughout the system.  Using the default settings (which, after all,
almost everybody does), you can ask the system for virtually infinite
amounts of memory, and the system will say "OK", and if you only use a
tiny bit of that, everything will be fine.

With your recommended settings, programs like that will segfault
instead.

It's the height of hubris as Emacs developers to recommend OS-wide
settings on something like this, and it makes us look like amateurs.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#54698: non-recursive GC marking [PATCH]

[Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Users will see mysterious segfaults that they didn't see before
> throughout the system.  Using the default settings (which, after all,
> almost everybody does), you can ask the system for virtually infinite
> amounts of memory, and the system will say "OK", and if you only use a
> tiny bit of that, everything will be fine.

With the default settings (0), you cannot ask the system for an infinite
amount of memory.  The kernel will reject deliberate overcommits of
memory, but will let programs like Emacs slowly run out of memory until
they are killed.  There is some guessing involved, and that guessing can
become unpredictable, leading to behavior like what Richard saw.

> With your recommended settings, programs like that will segfault
> instead.

Those programs which ask for huge amounts of heap and do not check the
return value of malloc will crash anyway under the default kernel
setting, which is why they don't exist.

> It's the height of hubris as Emacs developers to recommend OS-wide
> settings on something like this, and it makes us look like amateurs.

Overcommit is very controversial among even the Linux developers,
because it works well for some programs and does not for others.

IMO, it is reasonable to recommend the option that works best for us,
which is to turn overcommit off.

Thanks.

bug#54698: non-recursive GC marking [PATCH]

[Lars Ingebrigtsen]

Po Lu <luangruo@yahoo.com> writes:

> IMO, it is reasonable to recommend the option that works best for us,
> which is to turn overcommit off.

I don't think so, and neither does Stefan M., but I won't press the
issue.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#54698: non-recursive GC marking [PATCH]

[Phil Sainty]

On 2022-04-09 01:07, Lars Ingebrigtsen wrote:
> Po Lu <luangruo@yahoo.com> writes:
>> IMO, it is reasonable to recommend the option that works
>> best for us, which is to turn overcommit off.
> 
> I don't think so, and neither does Stefan M., but I won't
> press the issue.

How about we don't "recommend" anything, but instead simply
describe the issue and the options available?

If users see a *recommendation*, they might follow it without
understanding the ramifications.

If we're not pressuring users in any direction, then they
are less likely to make a change without researching it for
themselves.  (Indeed we might even "recommend" that they
research it for themselves, and provide some pointers to
where they can learn more about feature and its pros and
cons.)

I don't see any harm in pointing out the existence of this
feature, but advocating for a non-default configuration
seems like a rather dubious idea to me.


-Phil

bug#54698: non-recursive GC marking [PATCH]

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: Eli Zaretskii <eliz@gnu.org>,  rms@gnu.org,  p.stephani2@gmail.com,
>   mattiase@acm.org,  54698@debbugs.gnu.org
> Date: Fri, 08 Apr 2022 13:55:10 +0200
> 
> Po Lu <luangruo@yahoo.com> writes:
> 
> > On GNU/Linux systems, the system does not normally report running out of
> > memory to Emacs, and can instead randomly kill processes when they run
> > out of memory.  We recommend that you turn this behavior off, so that
> > Emacs can respond correctly when it runs out of memory, by becoming the
> > super user, editing the file @code{/etc/sysctl.conf} to contain the
> > following lines, and then running the command @code{sysctl -p} as the
> > super user:
> 
> I don't think we should recommend doing this.  It has serious
> deleterious effects on the operating system, because many programs
> written for GNU/Linux depends on the current behaviour (where malloc-ing
> basically never ever fails).

We could explain the advantages and disadvantages, and let users
decide.

bug#54698: non-recursive GC marking [PATCH]

[Andrea Corallo]

Mattias Engdegård <mattiase@acm.org> writes:

> 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.

Hi Mattias,

do you have any other performance measure for cases different than the
one mentioned?

Thanks

  Andrea

bug#54698: non-recursive GC marking [PATCH]

[Mattias Engdegård]

4 apr. 2022 kl. 16.32 skrev Andrea Corallo <akrl@sdf.org>:

> do you have any other performance measure for cases different than the
> one mentioned?

Well, there is the usual collection of special-purpose benchmarks, and I also timed the GC after a precise set of interactions involving scrolling through xdisp.c and typecore.ml, as well as running magit. And ran Relint, and a few more things I can't remember. The numbers were all largely consistent, but I encourage you to run your fav workload.

Anything particular on your mind?

bug#54698: non-recursive GC marking [PATCH]

[Andrea Corallo]

Mattias Engdegård <mattiase@acm.org> writes:

> 4 apr. 2022 kl. 16.32 skrev Andrea Corallo <akrl@sdf.org>:
>
>> do you have any other performance measure for cases different than the
>> one mentioned?
>
> Well, there is the usual collection of special-purpose benchmarks, and
> I also timed the GC after a precise set of interactions involving
> scrolling through xdisp.c and typecore.ml, as well as running
> magit. And ran Relint, and a few more things I can't remember. The
> numbers were all largely consistent, but I encourage you to run your
> fav workload.
>
> Anything particular on your mind?

We have some benchmarks in elisp-benchmarks that is GC bounded (IIRC
nbody at least), I guess would be worth running.

Thanks

  Andrea

bug#54698: non-recursive GC marking [PATCH]

[Mattias Engdegård]

4 apr. 2022 kl. 17.44 skrev Andrea Corallo <akrl@sdf.org>:

> We have some benchmarks in elisp-benchmarks that is GC bounded (IIRC
> nbody at least), I guess would be worth running.

Go for it! I ran another float-intensive benchmark and got a speedup of 2.6 % which is more than I hoped for given that tracing floats isn't really affected much by the change from recursion to stack as they have no subcomponents that need tracing.

And naturally this is all just some new go-fast stripes on the pig (and, more importantly, iron railings preventing it from going down the cliff), not the racehorse we really want.

bug#54698: non-recursive GC marking [PATCH]

[Andrea Corallo]

Mattias Engdegård <mattiase@acm.org> writes:

> 4 apr. 2022 kl. 17.44 skrev Andrea Corallo <akrl@sdf.org>:
>
>> We have some benchmarks in elisp-benchmarks that is GC bounded (IIRC
>> nbody at least), I guess would be worth running.
>
> Go for it!

I'm sorry I've really no time these days to test it myself.

But I think should be up to the proponent of such a deep (and nice)
change to provide a bare number of measures to convince the community
that there's no negative performance inpact in order to have the patch
accepted.

Best Regards

  Andrea