Re: Eager garbage collection

Re: Eager garbage collection

[Spencer Baugh]

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>The time to do a GC doesn't depend on the amount of garbage so much as
>the size of the heap, but I think I like your idea.  Better yet: keep
>track of the time that each GC takes and use that as a guide for the
>idle-time delay.

OK, I added an exponential-moving-average to track the time that GC
uses, and use it as the idle-time delay, with the idea that if we
reach idle time X, the naive best estimate of the total idle time is
2*X. See following patches.

[PATCH 1/3] Add gc-estimated-time variable

[Spencer Baugh]

---
 src/alloc.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index 2b3643e35b..8d31903089 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -6129,10 +6129,19 @@ garbage_collect (void)
   /* Accumulate statistics.  */
   if (FLOATP (Vgc_elapsed))
     {
+      const struct timespec this_gc_elapsed = timespec_sub (current_timespec (), start);
       static struct timespec gc_elapsed;
-      gc_elapsed = timespec_add (gc_elapsed,
-				 timespec_sub (current_timespec (), start));
+      gc_elapsed = timespec_add (gc_elapsed, this_gc_elapsed);
       Vgc_elapsed = make_float (timespectod (gc_elapsed));
+      static double gc_time_ema;
+      if (gc_time_ema == 0.0) {
+        /* initialize exponential moving average to first GC time */
+        gc_time_ema = timespectod (this_gc_elapsed);
+      } else {
+        /* decay very fast, since heap size can change rapidly */
+        gc_time_ema = 0.5 * gc_time_ema + 0.5 * timespectod (this_gc_elapsed);
+      }
+      Vgc_estimated_time = make_float (gc_time_ema);
     }
 
   gcs_done++;
@@ -7528,6 +7537,11 @@ do hash-consing of the objects allocated to pure space.  */);
 The time is in seconds as a floating point value.  */);
   DEFVAR_INT ("gcs-done", gcs_done,
               doc: /* Accumulated number of garbage collections done.  */);
+  DEFVAR_LISP ("gc-estimated-time", Vgc_estimated_time,
+	       doc: /* An estimate of the time required for the next garbage collection.
+The time is in seconds as a floating point value.
+This is calculated as an exponential moving average of the time
+required for previous garbage collections.  */);
 
   DEFVAR_INT ("integer-width", integer_width,
 	      doc: /* Maximum number N of bits in safely-calculated integers.
-- 
2.28.0

Re: [PATCH 1/3] Add gc-estimated-time variable

[Eli Zaretskii]

> From: Spencer Baugh <sbaugh@catern.com>
> Date: Tue, 17 Nov 2020 19:20:48 -0500
> Cc: Spencer Baugh <sbaugh@catern.com>
> 

Thanks, a few comments regarding style and coding conventions:

>    if (FLOATP (Vgc_elapsed))
>      {
> +      const struct timespec this_gc_elapsed = timespec_sub (current_timespec (), start);

Please avoid such long lines, break them into several shorter lines.

> +      if (gc_time_ema == 0.0) {
> +        /* initialize exponential moving average to first GC time */
> +        gc_time_ema = timespectod (this_gc_elapsed);
> +      } else {
> +        /* decay very fast, since heap size can change rapidly */
> +        gc_time_ema = 0.5 * gc_time_ema + 0.5 * timespectod (this_gc_elapsed);
> +      }

This is not our style of using braces, please reformat to use our
style.

[PATCH 2/3] Add garbage-collect-maybe function

[Spencer Baugh]

---
 src/alloc.c | 33 +++++++++++++++++++++++++++++++++
 src/lisp.h  |  1 +
 2 files changed, 34 insertions(+)

diff --git a/src/alloc.c b/src/alloc.c
index 8d31903089..c6c07d5dbe 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -5961,6 +5961,21 @@ maybe_garbage_collect (void)
     garbage_collect ();
 }
 
+/* Like maybe_garbage_collect, but with the GC threshold halved, so
+   that we'll GC sooner than we would otherwise.
+   Returns true if we GC'd.  */
+bool
+maybe_garbage_collect_eagerly (EMACS_INT factor)
+{
+  bump_consing_until_gc (gc_cons_threshold, Vgc_cons_percentage);
+  EMACS_INT since_gc = gc_threshold - consing_until_gc;
+  if (factor >= 1 && since_gc > gc_threshold / factor) {
+    garbage_collect ();
+    return true;
+  } else
+    return false;
+}
+
 /* Subroutine of Fgarbage_collect that does most of the work.  */
 void
 garbage_collect (void)
@@ -6215,6 +6230,23 @@ See Info node `(elisp)Garbage Collection'.  */)
   return CALLMANY (Flist, total);
 }
 
+DEFUN ("garbage-collect-maybe", Fgarbage_collect_maybe,
+Sgarbage_collect_maybe, 1, 1, "",
+       doc: /* Call `garbage-collect' if enough allocation happened.
+FACTOR determined what "enough" means here:
+a FACTOR of N means to run the GC if more than 1/Nth of the allocations
+needed to triger automatic allocation took place.
+Returns t if we garbage collected, and nil otherwise.  */)
+  (Lisp_Object factor)
+{
+  CHECK_FIXNAT (factor);
+  EMACS_INT fact = XFIXNAT (factor);
+  if (maybe_garbage_collect_eagerly(fact))
+    return Qt;
+  else
+    return Qnil;
+}
+
 /* Mark Lisp objects in glyph matrix MATRIX.  Currently the
    only interesting objects referenced from glyphs are strings.  */
 
@@ -7564,6 +7596,7 @@ N should be nonnegative.  */);
   defsubr (&Smake_finalizer);
   defsubr (&Spurecopy);
   defsubr (&Sgarbage_collect);
+  defsubr (&Sgarbage_collect_maybe);
   defsubr (&Smemory_info);
   defsubr (&Smemory_use_counts);
 #ifdef GNU_LINUX
diff --git a/src/lisp.h b/src/lisp.h
index 76d74200ac..5ef47fa234 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3793,6 +3793,7 @@ flush_stack_call_func (void (*func) (void *arg), void *arg)
 
 extern void garbage_collect (void);
 extern void maybe_garbage_collect (void);
+extern bool maybe_garbage_collect_eagerly (EMACS_INT factor);
 extern const char *pending_malloc_warning;
 extern Lisp_Object zero_vector;
 extern EMACS_INT consing_until_gc;
-- 
2.28.0

Re: [PATCH 2/3] Add garbage-collect-maybe function

[Eli Zaretskii]

> From: Spencer Baugh <sbaugh@catern.com>
> Date: Tue, 17 Nov 2020 19:20:49 -0500
> Cc: Spencer Baugh <sbaugh@catern.com>
> 

Thanks, a few comments regarding style and coding conventions:

> +  if (factor >= 1 && since_gc > gc_threshold / factor) {
> +    garbage_collect ();
> +    return true;
> +  } else
> +    return false;

Style of braces again.

> +FACTOR determined what "enough" means here:
          ^^^^^^^^^^
"determines"

> +a FACTOR of N means to run the GC if more than 1/Nth of the allocations
> +needed to triger automatic allocation took place.

  "If FACTOR is a positive number N, it means to run GC ..."

> +Returns t if we garbage collected, and nil otherwise.  */)

  "Return t if GC happened, nil otherwise".

(IOW, avoid the "we" part.)

> +  if (maybe_garbage_collect_eagerly(fact))
                                     ^^
Please leave a blank between the name of the function and the opening
brace.

[PATCH 3/3] Start opportunistic GC timer at startup

[Spencer Baugh]

---
 lisp/startup.el | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

diff --git a/lisp/startup.el b/lisp/startup.el
index 9f67dfde12..412ed0ca0e 100644
--- a/lisp/startup.el
+++ b/lisp/startup.el
@@ -1008,6 +1008,32 @@ the `--debug-init' option to view a complete error backtrace."
     (when debug-on-error-should-be-set
       (setq debug-on-error debug-on-error-from-init-file))))
 
+(defcustom gc-opportunistic-eager-factor 2
+  "How eager we should be when GCing while Emacs is idle.
+Emacs will call garbage-collect-maybe with this argument to
+eagerly GC after gc-estimated-time idle seconds have passed.
+If this is nil, we won't perform GC while Emacs is idle.
+"
+  :type 'integer)
+
+(defvar gc-next-opportunistic-timer nil
+  "The timer for the next opportunistic GC
+This is set by `gc-start-opportunistic'.")
+
+(defun gc-start-opportunistic ()
+  "Start a timer to GC after `gc-estimated-time' idle seconds.
+The GC is performed with `garbage-collect-maybe', and is passed
+`gc-opportunistic-eager-factor' as its single argument.
+If `gc-opportunistic-eager-factor' is nil, we won't do anything.
+This function is itself run by an idle timer at Emacs startup."
+  (when gc-opportunistic-eager-factor
+    (when gc-next-opportunistic-timer
+      (cancel-timer gc-next-opportunistic-timer))
+    (setq gc-next-opportunistic-timer
+          (run-with-idle-timer
+           gc-estimated-time nil
+           #'garbage-collect-maybe gc-opportunistic-eager-factor))))
+
 (defun command-line ()
   "A subroutine of `normal-top-level'.
 Amongst another things, it parses the command-line arguments."
@@ -1420,6 +1446,15 @@ please check its value")
 		 (eq face-ignored-fonts old-face-ignored-fonts))
       (clear-face-cache)))
 
+  ;; Start opportunistic GC (after loading the init file, so we obey
+  ;; its settings).  This is desirable for two reason:
+  ;; - It reduces the number of times we have to GC in the middle of
+  ;;   an operation.
+  ;; - It means we GC when the C stack is short, reducing the risk of false
+  ;;   positives from the conservative stack scanning.
+  (when gc-opportunistic-eager-factor
+    (run-with-idle-timer 1 t #'gc-start-opportunistic))
+
   (setq after-init-time (current-time))
   ;; Display any accumulated warnings after all functions in
   ;; `after-init-hook' like `desktop-read' have finalized possible
-- 
2.28.0

Re: [PATCH 3/3] Start opportunistic GC timer at startup

[Eli Zaretskii]

> From: Spencer Baugh <sbaugh@catern.com>
> Date: Tue, 17 Nov 2020 19:20:50 -0500
> Cc: Spencer Baugh <sbaugh@catern.com>

Thanks, a few comments regarding style and coding conventions:

> +(defcustom gc-opportunistic-eager-factor 2
> +  "How eager we should be when GCing while Emacs is idle.
> +Emacs will call garbage-collect-maybe with this argument to
> +eagerly GC after gc-estimated-time idle seconds have passed.
> +If this is nil, we won't perform GC while Emacs is idle.

This doesn't say that the value should be either nil or a positive
number, a float.  Also, please avoid saying 'we" in documentation and
comments.  Finally, referebces to other functions and variables should
be quoted `like this', so they are converted into hyperlinks.

> +  :type 'integer)

Please always include a :version tag when you add new defcustoms.

> +(defvar gc-next-opportunistic-timer nil
> +  "The timer for the next opportunistic GC
                                            ^
Period missing at end of sentence.

> +(defun gc-start-opportunistic ()
> +  "Start a timer to GC after `gc-estimated-time' idle seconds.
> +The GC is performed with `garbage-collect-maybe', and is passed
> +`gc-opportunistic-eager-factor' as its single argument.
> +If `gc-opportunistic-eager-factor' is nil, we won't do anything.
> +This function is itself run by an idle timer at Emacs startup."

There's no need to explain the function's algorithm in a doc string,
that's what comments are for.  The doc string should explain what the
function does (not how it does that), and how to use it.

Re: Eager garbage collection

[Stefan Monnier]

>>The time to do a GC doesn't depend on the amount of garbage so much as
>>the size of the heap, but I think I like your idea.  Better yet: keep
>>track of the time that each GC takes and use that as a guide for the
>>idle-time delay.
>
> OK, I added an exponential-moving-average to track the time that GC
> uses, and use it as the idle-time delay, with the idea that if we
> reach idle time X, the naive best estimate of the total idle time is
> 2*X. See following patches.

The code is looking pretty good.  I have a few minor comments to make
about it, but the only significant one is that it's a bit more than what
we can consider as trivial.

AFAICT you haven't yet signed the copyright paperwork for contributions
to Emacs, so we'd need you to do that before we can accept your code.

If that's OK with you, then please fill the form below and send it to
the FSF as instructed so they can send you the relevant paperwork to
sign,


        Stefan


Please email the following information to assign@gnu.org, and we
will send you the assignment form for your past and future changes.

Please use your full legal name (in ASCII characters) as the subject
line of the message.
----------------------------------------------------------------------
REQUEST: SEND FORM FOR PAST AND FUTURE CHANGES

[What is the name of the program or package you're contributing to?]
Emacs

[Did you copy any files or text written by someone else in these changes?
Even if that material is free software, we need to know about it.]


[Do you have an employer who might have a basis to claim to own
your changes?  Do you attend a school which might make such a claim?]


[For the copyright registration, what country are you a citizen of?]


[What year were you born?]


[Please write your email address here.]


[Please write your postal address here.]





[Which files have you changed so far, and which new files have you written
so far?]

Re: Eager garbage collection

[Spencer Baugh]

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>>The time to do a GC doesn't depend on the amount of garbage so much as
>>>the size of the heap, but I think I like your idea.  Better yet: keep
>>>track of the time that each GC takes and use that as a guide for the
>>>idle-time delay.
>>
>> OK, I added an exponential-moving-average to track the time that GC
>> uses, and use it as the idle-time delay, with the idea that if we
>> reach idle time X, the naive best estimate of the total idle time is
>> 2*X. See following patches.
>
> The code is looking pretty good.  I have a few minor comments to make
> about it, but the only significant one is that it's a bit more than what
> we can consider as trivial.
>
> AFAICT you haven't yet signed the copyright paperwork for contributions
> to Emacs, so we'd need you to do that before we can accept your code.

I actually submitted the paperwork just yesterday (finally got around to
it since I was sending this in) - I assume it's still being processed.

Re: Eager garbage collection

[Stefan Monnier]

> I actually submitted the paperwork just yesterday (finally got around to
> it since I was sending this in)

Great, and sorry 'bout the duplicate.

> - I assume it's still being processed.

Most likely, yes.


        Stefan

Re: Eager garbage collection

[Andrea Corallo via Emacs development discussions.]

My question is, what is the advantage of this implementation respect the
pure Lisp one we have?

<https://gitlab.com/koral/gcmh/-/blob/master/gcmh.el>

AFAIU they achieve the same.  If that's the case I indeed prefer the
Lisp one as simpler and easier to extend.

Regards

  Andrea

Re: Eager garbage collection

[Eli Zaretskii]

> Cc: emacs-devel@gnu.org
> Date: Wed, 18 Nov 2020 08:02:17 +0000
> From: Andrea Corallo via "Emacs development discussions." <emacs-devel@gnu.org>
> 
> My question is, what is the advantage of this implementation respect the
> pure Lisp one we have?
> 
> <https://gitlab.com/koral/gcmh/-/blob/master/gcmh.el>
> 
> AFAIU they achieve the same.  If that's the case I indeed prefer the
> Lisp one as simpler and easier to extend.

AFAICT, the basic idea is very different, so the results will probably
also be different.

In general, I cannot say I like the idea of enlarging the GC threshold
based on some heuristic ideas regarding when it matters and when it
doesn't.  There be dragons.

Re: Eager garbage collection

[Andrea Corallo via Emacs development discussions.]

Eli Zaretskii <eliz@gnu.org> writes:

>> Cc: emacs-devel@gnu.org
>> Date: Wed, 18 Nov 2020 08:02:17 +0000
>> From: Andrea Corallo via "Emacs development discussions." <emacs-devel@gnu.org>
>> 
>> My question is, what is the advantage of this implementation respect the
>> pure Lisp one we have?
>> 
>> <https://gitlab.com/koral/gcmh/-/blob/master/gcmh.el>
>> 
>> AFAIU they achieve the same.  If that's the case I indeed prefer the
>> Lisp one as simpler and easier to extend.
>
> AFAICT, the basic idea is very different, so the results will probably
> also be different.

My understanding is that they both:

  - Run the normal GC with a threshold X1
  - Run after an idle time t GC with threshold X2, where X2 < X1

This patch compute X2 in terms of X1 using
`gc-opportunistic-eager-factor' while in gcmh one specify
`gcmh-low-cons-threshold' and `gcmh-high-cons-threshold' but
conceptually looks the same to me.

Am I wrong?

  Andrea

Re: Eager garbage collection

[Eli Zaretskii]

> From: Andrea Corallo <akrl@sdf.org>
> Cc: sbaugh@catern.com, emacs-devel@gnu.org
> Date: Wed, 18 Nov 2020 15:30:24 +0000
> 
> > AFAICT, the basic idea is very different, so the results will probably
> > also be different.
> 
> My understanding is that they both:
> 
>   - Run the normal GC with a threshold X1
>   - Run after an idle time t GC with threshold X2, where X2 < X1
> 
> This patch compute X2 in terms of X1 using
> `gc-opportunistic-eager-factor' while in gcmh one specify
> `gcmh-low-cons-threshold' and `gcmh-high-cons-threshold' but
> conceptually looks the same to me.
> 
> Am I wrong?

The devil, as usually, is in the details.  What is radically different
between the two is the value of X1.  In the gcmh.el case, the value of
X1 is alarmingly large, something I keep warning people against for a
long time.  I don't want us to adopt such dangerous practices.  And
using that large value is central to the idea of gcmh.el, so if we
lower it significantly, I wouldn't expect it to provide significant
benefits.

Re: Eager garbage collection

[Andrea Corallo via Emacs development discussions.]

Eli Zaretskii <eliz@gnu.org> writes:

> The devil, as usually, is in the details.  What is radically different
> between the two is the value of X1.  In the gcmh.el case, the value of
> X1 is alarmingly large, something I keep warning people against for a
> long time.  I don't want us to adopt such dangerous practices.  And
> using that large value is central to the idea of gcmh.el, so if we
> lower it significantly, I wouldn't expect it to provide significant
> benefits.

I see, I was discussing the implementations rather than the defaults.
Indeed these are easy to change to what we think is suitable for going
into master.

  Andrea

Re: Eager garbage collection

[Eli Zaretskii]

> From: Andrea Corallo <akrl@sdf.org>
> Cc: sbaugh@catern.com, emacs-devel@gnu.org
> Date: Wed, 18 Nov 2020 17:26:21 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > The devil, as usually, is in the details.  What is radically different
> > between the two is the value of X1.  In the gcmh.el case, the value of
> > X1 is alarmingly large, something I keep warning people against for a
> > long time.  I don't want us to adopt such dangerous practices.  And
> > using that large value is central to the idea of gcmh.el, so if we
> > lower it significantly, I wouldn't expect it to provide significant
> > benefits.
> 
> I see, I was discussing the implementations rather than the defaults.
> Indeed these are easy to change to what we think is suitable for going
> into master.

Once again, I think the central idea of that package is that the GC
threshold is raised to a dangerously high level while commands run.
If you lower that high threshold, the whole concept of the package
will collapse, and the effect will be much smaller than the author
intended.

So it isn't just a matter of changing the defaults.

Re: Eager garbage collection

[Andrea Corallo via Emacs development discussions.]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Andrea Corallo <akrl@sdf.org>
>> Cc: sbaugh@catern.com, emacs-devel@gnu.org
>> Date: Wed, 18 Nov 2020 17:26:21 +0000
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> > The devil, as usually, is in the details.  What is radically different
>> > between the two is the value of X1.  In the gcmh.el case, the value of
>> > X1 is alarmingly large, something I keep warning people against for a
>> > long time.  I don't want us to adopt such dangerous practices.  And
>> > using that large value is central to the idea of gcmh.el, so if we
>> > lower it significantly, I wouldn't expect it to provide significant
>> > benefits.
>> 
>> I see, I was discussing the implementations rather than the defaults.
>> Indeed these are easy to change to what we think is suitable for going
>> into master.
>
> Once again, I think the central idea of that package is that the GC
> threshold is raised to a dangerously high level while commands run.
> If you lower that high threshold, the whole concept of the package
> will collapse, and the effect will be much smaller than the author
> intended.
>
> So it isn't just a matter of changing the defaults.

I was dicussing gcmh implementation as an option to be included in place
of the one proposed by Spencer, not the defaults that I've *not*
suggested for inclusion.

That said as the consensus goes for Spencer's implementation I believe
these are outdated details.

  Andrea

Re: Eager garbage collection

[Spencer Baugh]

Andrea Corallo <akrl@sdf.org> writes:
> My question is, what is the advantage of this implementation respect the
> pure Lisp one we have?
>
> <https://gitlab.com/koral/gcmh/-/blob/master/gcmh.el>
>
> AFAIU they achieve the same.  If that's the case I indeed prefer the
> Lisp one as simpler and easier to extend.

The core necessary thing that requires C changes is making a garbage
collection function which "maybe" does a garbage collect.

gcmh.el always does a full garbage collection when idle, even if there's
no garbage.  That will hurt responsiveness, especially with a very large
heap (as gcmh configures), because GC takes time proportional to the
size of the heap, not the amount of garbage.

Possibly, we could rely on the fact that maybe_gc gets called
automatically as part of Lisp evaluation.  Then we'd just want to ensure
that GC happens eagerly, which we could do by lowering gc-cons-threshold
while idle.  But that's excessively magical, I would say.

Although, I suppose we could just expose consing_until_gc, or some other
variable, to Lisp.  Then the eager maybe-GC logic could be in Lisp:
Recalculate a local consing_until_gc and decide whether or not to call
garbage-collect based on that, just like the C code does.  It would
duplicate some logic between Lisp and C, but maybe that's ok.

If others think that's a good idea, I can change to just exposing
consing_until_gc.

Re: Eager garbage collection

[Andrea Corallo via Emacs development discussions.]

Spencer Baugh <sbaugh@catern.com> writes:

> Andrea Corallo <akrl@sdf.org> writes:
>> My question is, what is the advantage of this implementation respect the
>> pure Lisp one we have?
>>
>> <https://gitlab.com/koral/gcmh/-/blob/master/gcmh.el>
>>
>> AFAIU they achieve the same.  If that's the case I indeed prefer the
>> Lisp one as simpler and easier to extend.
>
> The core necessary thing that requires C changes is making a garbage
> collection function which "maybe" does a garbage collect.
>
> gcmh.el always does a full garbage collection when idle, even if there's
> no garbage.  That will hurt responsiveness, especially with a very large
> heap (as gcmh configures), because GC takes time proportional to the
> size of the heap, not the amount of garbage.

Correct that was a conscious decision, in the assumption that the user
is unlikely to be interacting with Emacs at that moment I deemed was
good to clean-up all the garbage unconditionally.

> Possibly, we could rely on the fact that maybe_gc gets called
> automatically as part of Lisp evaluation.  Then we'd just want to ensure
> that GC happens eagerly, which we could do by lowering gc-cons-threshold
> while idle.  But that's excessively magical, I would say.

There is nothing magical about and I believe is how it should be
implemented.

Setting a lower threshold there also prevents functions that may be
executed by timers to leave the heap with garbage just before the user
start the next command.

If we don't like the idle unconditional garbage collection of the GCMH
we can just remove it.  At that point the only thing we should expose
from C is the last GC elapsed time.

  Andrea

Re: Eager garbage collection

[Stefan Monnier]

> Setting a lower threshold there also prevents functions that may be
> executed by timers to leave the heap with garbage just before the user
> start the next command.

This is risky, tho, because a low threshold will increase the proportion
of time spent in GC, which could negatively impact the performance of
process-filters.

I do think it is good to move as much of the code to Elisp.  But the
patch Spencer sent only has 2 small parts in C: the gc-time tracker and
the gc-maybe function.

We could move the gc-time tracker to Elisp (and it could be a good idea
to do so, since I can imagine getting fancier in there.  E.g. instead of
tracking the actual GC time, we could track the "time relative to heap
size" which might allow us to better predict the time taken by the next
GC), but we'd still need some changes to the C code for example so that
`post-gc-hook` gets access to the elapsed time of the last GC.

For gc-maybe, we could arguably code it all in Elisp, indeed, as:

    (defun gc-maybe (factor)
      (let ((gc-cons-threshold (/ gc-cons-threshold factor))
            (gc-cons-percentage (/ gc-cons-percentage factor)))
        (eval (+ 1 1)))) ;; This internally calls the `maybe_gc` C function.

The `eval` part is quite hackish, tho, and the workings depend on
exactly when those gc-cons-* settings take effect which is not
documented either.

In contrast the C version is clear and direct, so I think I'm pretty
happy with the C version.


        Stefan

Re: Eager garbage collection

[Andrea Corallo via Emacs development discussions.]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Setting a lower threshold there also prevents functions that may be
>> executed by timers to leave the heap with garbage just before the user
>> start the next command.
>
> This is risky, tho, because a low threshold will increase the proportion
> of time spent in GC, which could negatively impact the performance of
> process-filters.

When I say low threshold I think to something in the magniture order of
the current default, so in practice this is not a problem.

Also I though was a feature to have the guarantee that before starting
the next command after idle the garbage was under a certain threshold.

As a consequence I still have the Lisp as my favorite.

That said, I indeed like the feature :)

  Andrea

Re: Eager garbage collection

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Wed, 18 Nov 2020 11:52:26 -0500
> Cc: Spencer Baugh <sbaugh@catern.com>, Andrea Corallo <akrl@sdf.org>
> 
> In contrast the C version is clear and direct, so I think I'm pretty
> happy with the C version.

Indeed, I see no good reason to move this part to Lisp, especially
since it is all too easy to trigger GC from Lisp implementation of GC
without noticing.

Re: Eager garbage collection

[Eli Zaretskii]

> From: Spencer Baugh <sbaugh@catern.com>
> Date: Tue, 17 Nov 2020 19:20:47 -0500
> 
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
> >The time to do a GC doesn't depend on the amount of garbage so much as
> >the size of the heap, but I think I like your idea.  Better yet: keep
> >track of the time that each GC takes and use that as a guide for the
> >idle-time delay.
> 
> OK, I added an exponential-moving-average to track the time that GC
> uses, and use it as the idle-time delay, with the idea that if we
> reach idle time X, the naive best estimate of the total idle time is
> 2*X. See following patches.

I'm trying to understand whether we should enable this by default or
not.  The decision should depend on the overall effect of this
feature, and on whether it has any downsides.  IME, changes in GC
details frequently have unintended consequences.  Can you present some
evidence of the effect of using the feature, either measurements or
even anecdotal evidence?

More generally, perhaps we need some tools to measure the effect of
this (e.g., how many GC's happened during some rime interval, how much
time each GC took, how large is the VM size of Emacs, etc.  Then we
could ask people to present numbers with and without the feature, and
make the decision based on that.

Thanks.

Re: Eager garbage collection

[Spencer Baugh]

Eli Zaretskii <eliz@gnu.org> writes:
> I'm trying to understand whether we should enable this by default or
> not.  The decision should depend on the overall effect of this
> feature, and on whether it has any downsides.  IME, changes in GC
> details frequently have unintended consequences.  Can you present some
> evidence of the effect of using the feature, either measurements or
> even anecdotal evidence?
>
> More generally, perhaps we need some tools to measure the effect of
> this (e.g., how many GC's happened during some rime interval, how much
> time each GC took, how large is the VM size of Emacs, etc.  Then we
> could ask people to present numbers with and without the feature, and
> make the decision based on that.

One easy thing is to count how many GCs actually get triggered by the
idle opportunistic logic, and compare that to the total GCs.  That is a
proxy for some other properties, including "Is this moving substantial
numbers of GCs to run while idle?"

My v2 of the patch series adds such a counter (in addition to fixing the
style issues you mentioned); I'll send that shortly.

Spencer Baugh (3):
  Add gc-estimated-time variable
  Add garbage-collect-maybe function
  Start opportunistic GC timer at startup

 lisp/startup.el | 56 +++++++++++++++++++++++++++++++++++++++++++++++++
 src/alloc.c     | 55 ++++++++++++++++++++++++++++++++++++++++++++++--
 src/lisp.h      |  1 +
 3 files changed, 110 insertions(+), 2 deletions(-)

I'll run this for a while and see how it goes for me...

This doesn't answer the "What effect does this have on the input latency
experienced by the user?" question, though, which I think is perhaps the
most important question.  Not sure how to answer it, since it will
depend on user configurations and behavior.

The ultimate last resort for this question is to just add it, disabled
by default; then we can get feedback from users who enable it.  But
maybe we can find enough information to persuade ourselves that it is
good without having to wait for an entire release cycle like that.

Andrea, do you have any thoughts from GCMH on how to performance test
this?

[PATCH v2 1/3] Add gc-estimated-time variable

[Spencer Baugh]

---
 src/alloc.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index 2b3643e35b..fd572c0175 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -6129,10 +6129,19 @@ garbage_collect (void)
   /* Accumulate statistics.  */
   if (FLOATP (Vgc_elapsed))
     {
+      const struct timespec this_gc_elapsed =
+        timespec_sub (current_timespec (), start);
       static struct timespec gc_elapsed;
-      gc_elapsed = timespec_add (gc_elapsed,
-				 timespec_sub (current_timespec (), start));
+      gc_elapsed = timespec_add (gc_elapsed, this_gc_elapsed);
       Vgc_elapsed = make_float (timespectod (gc_elapsed));
+      static double gc_time_ema;
+      if (gc_time_ema == 0.0)
+        /* Initialize exponential moving average to first GC time. */
+        gc_time_ema = timespectod (this_gc_elapsed);
+      else
+        /* Decay very fast, since heap size can change rapidly. */
+        gc_time_ema = 0.5 * gc_time_ema + 0.5 * timespectod (this_gc_elapsed);
+      Vgc_estimated_time = make_float (gc_time_ema);
     }
 
   gcs_done++;
@@ -7528,6 +7537,11 @@ do hash-consing of the objects allocated to pure space.  */);
 The time is in seconds as a floating point value.  */);
   DEFVAR_INT ("gcs-done", gcs_done,
               doc: /* Accumulated number of garbage collections done.  */);
+  DEFVAR_LISP ("gc-estimated-time", Vgc_estimated_time,
+	       doc: /* An estimate of the time required for the next garbage collection.
+The time is in seconds as a floating point value.
+This is calculated as an exponential moving average of the time
+required for previous garbage collections.  */);
 
   DEFVAR_INT ("integer-width", integer_width,
 	      doc: /* Maximum number N of bits in safely-calculated integers.
-- 
2.28.0

Re: [PATCH v2 1/3] Add gc-estimated-time variable

[Eli Zaretskii]

> From: Spencer Baugh <sbaugh@catern.com>
> Cc: Spencer Baugh <sbaugh@catern.com>,
> 	Eli Zaretskii <eliz@gnu.org>
> Date: Sun, 22 Nov 2020 00:08:27 -0500
> 
> +        /* Decay very fast, since heap size can change rapidly. */
> +        gc_time_ema = 0.5 * gc_time_ema + 0.5 * timespectod (this_gc_elapsed);
> +      Vgc_estimated_time = make_float (gc_time_ema);

> +  DEFVAR_LISP ("gc-estimated-time", Vgc_estimated_time,
> +	       doc: /* An estimate of the time required for the next garbage collection.

I guess "Estimated time before next garbage collection" is somewhat
clearer, since "required" in this context might be confusing?

> +The time is in seconds as a floating point value.
> +This is calculated as an exponential moving average of the time
> +required for previous garbage collections.  */);

I don't think the last sentence should be in the doc string.  it
doesn't add anything useful, and the source code is available.

Thanks.

Re: [PATCH v2 1/3] Add gc-estimated-time variable

[Stefan Monnier]

>> +  DEFVAR_LISP ("gc-estimated-time", Vgc_estimated_time,
>> +	       doc: /* An estimate of the time required for the next garbage collection.
> I guess "Estimated time before next garbage collection" is somewhat
> clearer, since "required" in this context might be confusing?

Actually, I think it's more correct to say that it's the average time of
previous GCs (which our code then uses as an estimate of the time
that will be required by the next GC).


        Stefan

[PATCH v2 2/3] Add garbage-collect-maybe function

[Spencer Baugh]

---
 src/alloc.c | 37 +++++++++++++++++++++++++++++++++++++
 src/lisp.h  |  1 +
 2 files changed, 38 insertions(+)

diff --git a/src/alloc.c b/src/alloc.c
index fd572c0175..cc48acb17a 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -5961,6 +5961,23 @@ maybe_garbage_collect (void)
     garbage_collect ();
 }
 
+/* Like maybe_garbage_collect, but with the GC threshold reduced by
+   FACTOR, so that we'll GC sooner than we would otherwise.
+   Returns true if we GC'd.  */
+bool
+maybe_garbage_collect_eagerly (EMACS_INT factor)
+{
+  bump_consing_until_gc (gc_cons_threshold, Vgc_cons_percentage);
+  EMACS_INT since_gc = gc_threshold - consing_until_gc;
+  if (factor >= 1 && since_gc > gc_threshold / factor)
+    {
+      garbage_collect ();
+      return true;
+    }
+  else
+    return false;
+}
+
 /* Subroutine of Fgarbage_collect that does most of the work.  */
 void
 garbage_collect (void)
@@ -6215,6 +6232,25 @@ See Info node `(elisp)Garbage Collection'.  */)
   return CALLMANY (Flist, total);
 }
 
+DEFUN ("garbage-collect-maybe", Fgarbage_collect_maybe,
+Sgarbage_collect_maybe, 1, 1, "",
+       doc: /* Call `garbage-collect' if enough allocation happened.
+FACTOR determines what "enough" means here:
+If FACTOR is a positive number N, it means to run GC if more than
+1/Nth of the allocations needed to triger automatic allocation took
+place.
+Therefore, as N gets higher, this is more likely to perform a GC.
+Returns t if GC happened, and nil otherwise.  */)
+  (Lisp_Object factor)
+{
+  CHECK_FIXNAT (factor);
+  EMACS_INT fact = XFIXNAT (factor);
+  if (maybe_garbage_collect_eagerly (fact))
+    return Qt;
+  else
+    return Qnil;
+}
+
 /* Mark Lisp objects in glyph matrix MATRIX.  Currently the
    only interesting objects referenced from glyphs are strings.  */
 
@@ -7564,6 +7600,7 @@ N should be nonnegative.  */);
   defsubr (&Smake_finalizer);
   defsubr (&Spurecopy);
   defsubr (&Sgarbage_collect);
+  defsubr (&Sgarbage_collect_maybe);
   defsubr (&Smemory_info);
   defsubr (&Smemory_use_counts);
 #ifdef GNU_LINUX
diff --git a/src/lisp.h b/src/lisp.h
index 76d74200ac..5ef47fa234 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3793,6 +3793,7 @@ flush_stack_call_func (void (*func) (void *arg), void *arg)
 
 extern void garbage_collect (void);
 extern void maybe_garbage_collect (void);
+extern bool maybe_garbage_collect_eagerly (EMACS_INT factor);
 extern const char *pending_malloc_warning;
 extern Lisp_Object zero_vector;
 extern EMACS_INT consing_until_gc;
-- 
2.28.0

Re: [PATCH v2 2/3] Add garbage-collect-maybe function

[Eli Zaretskii]

> From: Spencer Baugh <sbaugh@catern.com>
> Cc: Spencer Baugh <sbaugh@catern.com>,
> 	Eli Zaretskii <eliz@gnu.org>
> Date: Sun, 22 Nov 2020 00:08:28 -0500
> 
> +DEFUN ("garbage-collect-maybe", Fgarbage_collect_maybe,
> +Sgarbage_collect_maybe, 1, 1, "",
> +       doc: /* Call `garbage-collect' if enough allocation happened.
> +FACTOR determines what "enough" means here:
> +If FACTOR is a positive number N, it means to run GC if more than
> +1/Nth of the allocations needed to triger automatic allocation took
                                      ^^^^^^
"trigger"

The "1/Nth of the allocations needed to triger automatic allocation"
part is confusing.  Did you mean "1/Nth of the allocations determined
by `gc-cons-threshold' and `gc-cons-percentage'"?

[PATCH v2 3/3] Start opportunistic GC timer at startup

[Spencer Baugh]

---
 lisp/startup.el | 56 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)

diff --git a/lisp/startup.el b/lisp/startup.el
index 9f67dfde12..a9dc75f542 100644
--- a/lisp/startup.el
+++ b/lisp/startup.el
@@ -1008,6 +1008,53 @@ the `--debug-init' option to view a complete error backtrace."
     (when debug-on-error-should-be-set
       (setq debug-on-error debug-on-error-from-init-file))))
 
+(defcustom gc-opportunistic-eager-factor 2
+  "Factor to use for `garbage-collect-maybe' with opportunistic GC.
+This should be a positive integer or nil.
+If non-nil, Emacs will call `garbage-collect-maybe' with this
+argument as part of opportunistic GC triggered by
+`gc-start-opportunistic'.
+If this is nil, `gc-start-opportunistic' will do nothing."
+  :type 'integer
+  :version "28.1")
+
+(defvar gc-opportunistic-performed 0
+  "The number of opportunistic GCs we have actually performed.
+This is incremented by `gc-start-opportunistic', if and when it
+actually does a GC.")
+
+(defvar gc-next-opportunistic-timer nil
+  "The timer for the next opportunistic GC.
+This is set by `gc-start-opportunistic'.")
+
+(defun gc-start-opportunistic ()
+  "Start an opportunistic GC which may run at some point in the future.
+
+This function may perform a single GC at some point while Emacs
+is idle, with the goal of improving interactive performance by
+avoiding GC while the user is actively interacting with Emacs.
+
+The higher `gc-opportunistic-eager-factor' is, the more likely
+this function is to actually perform a GC.  Note that increasing
+this variable can worsen performance by performing excessive GCs.
+If `gc-opportunistic-eager-factor' is nil, this function will do
+nothing.
+
+If `gc-opportunistic-eager-factor' is non-nil at Emacs startup,
+this function will be run by an idle timer.  Such a timer can
+also be started after Emacs startup with `run-with-idle-timer'."
+  (when gc-opportunistic-eager-factor
+    (when gc-next-opportunistic-timer
+      (cancel-timer gc-next-opportunistic-timer))
+    (setq gc-next-opportunistic-timer
+          (run-with-idle-timer
+           gc-estimated-time nil
+           (lambda ()
+             (if (garbage-collect-maybe gc-opportunistic-eager-factor)
+                 (setq gc-opportunistic-performed
+                       (1+ gc-opportunistic-performed))))
+           ))))
+
 (defun command-line ()
   "A subroutine of `normal-top-level'.
 Amongst another things, it parses the command-line arguments."
@@ -1420,6 +1467,15 @@ please check its value")
 		 (eq face-ignored-fonts old-face-ignored-fonts))
       (clear-face-cache)))
 
+  ;; Start opportunistic GC (after loading the init file, so we obey
+  ;; its settings).  This is desirable for two reason:
+  ;; - It reduces the number of times we have to GC in the middle of
+  ;;   an operation.
+  ;; - It means we GC when the C stack is short, reducing the risk of false
+  ;;   positives from the conservative stack scanning.
+  (when gc-opportunistic-eager-factor
+    (run-with-idle-timer 1 t #'gc-start-opportunistic))
+
   (setq after-init-time (current-time))
   ;; Display any accumulated warnings after all functions in
   ;; `after-init-hook' like `desktop-read' have finalized possible
-- 
2.28.0

Re: [PATCH v2 3/3] Start opportunistic GC timer at startup

[Stefan Monnier]

> +(defun gc-start-opportunistic ()
> +  "Start an opportunistic GC which may run at some point in the future.
> +
> +This function may perform a single GC at some point while Emacs
> +is idle, with the goal of improving interactive performance by
> +avoiding GC while the user is actively interacting with Emacs.
> +
> +The higher `gc-opportunistic-eager-factor' is, the more likely
> +this function is to actually perform a GC.  Note that increasing
> +this variable can worsen performance by performing excessive GCs.
> +If `gc-opportunistic-eager-factor' is nil, this function will do
> +nothing.
> +
> +If `gc-opportunistic-eager-factor' is non-nil at Emacs startup,
> +this function will be run by an idle timer.  Such a timer can
> +also be started after Emacs startup with `run-with-idle-timer'."
> +  (when gc-opportunistic-eager-factor
> +    (when gc-next-opportunistic-timer
> +      (cancel-timer gc-next-opportunistic-timer))
> +    (setq gc-next-opportunistic-timer
> +          (run-with-idle-timer
> +           gc-estimated-time nil
> +           (lambda ()
> +             (if (garbage-collect-maybe gc-opportunistic-eager-factor)
> +                 (setq gc-opportunistic-performed
> +                       (1+ gc-opportunistic-performed))))
> +           ))))
> +
>  (defun command-line ()
>    "A subroutine of `normal-top-level'.
>  Amongst another things, it parses the command-line arguments."
> @@ -1420,6 +1467,15 @@ please check its value")
>  		 (eq face-ignored-fonts old-face-ignored-fonts))
>        (clear-face-cache)))
>  
> +  ;; Start opportunistic GC (after loading the init file, so we obey
> +  ;; its settings).  This is desirable for two reason:
> +  ;; - It reduces the number of times we have to GC in the middle of
> +  ;;   an operation.
> +  ;; - It means we GC when the C stack is short, reducing the risk of false
> +  ;;   positives from the conservative stack scanning.
> +  (when gc-opportunistic-eager-factor
> +    (run-with-idle-timer 1 t #'gc-start-opportunistic))

This looks a bit complicated: why use 2 timers?

I currently use the following instead:

    (defvar gc--opportunistic-counter 0)
    
    (defun gc--opportunistic ()
      "Run the GC during idle time."
      ;; This is good for two reason:
      ;; - It reduces the number of times we have to GC in the middle of
      ;;   an operation.
      ;; - It means we GC when the C stack is short, reducing the risk of false
      ;;   positives from the conservative stack scanning.
      (when (garbage-collect-maybe 3)
        (setq gc--opportunistic-counter (1+ gc--opportunistic-counter))
        ;; Recalibrate the timer.
        (cancel-function-timers #'gc--opportunistic)
        (run-with-idle-timer
         ;; FIXME: Magic formula!
         (+ 1 (* 10 (/ gc-elapsed gcs-done))) t #'gc--opportunistic)))
    (run-with-idle-timer 1 t #'gc--opportunistic)

Also notice that I use a different idle time (I think we should impose
a minimum of at the very least 0.2s, I used 1s), and I think
we may want to play with that as well.

When I looked at `gc--opportunistic-performed` I wasn't sure what to
think of it, when comparing it to `gcs-done`: I don't want this to be
too high (because that means we're doing way more GCs) and I don't want
it to be too low either (because it likely means it's ineffective).

Maybe what I want to compare it against is the number of commands
during which the GC is run exactly once?  The idea is to filter out
those commands which are compute-intensive and hence run the GC
internally (for which an opportunistic GC is of no use anyway).

So I added:

    (defvar gc--opportunistic-single-gc-cmds 0)
    (let ((last-gcs nil))
      (add-hook 'pre-command-hook (lambda () (setq last-gcs gcs-done)))
      (add-hook 'post-command-hook
                (lambda ()
                  (if (eq (1- gcs-done) last-gcs)
                      (setq gc--opportunistic-single-gc-cmds
                            (1+ gc--opportunistic-single-gc-cmds))))))

So far, this seems to indicate that it's working:
OT1H `gc--opportunistic-single-gc-cmds` stays much lower than
`gc--opportunistic-counter`, indicating that we seem to be able to avoid
GC in many cases, and OTOH `gc--opportunistic-counter` is much lower
than `gcs-done` indicating that we're not excessively increasing the
number of GCS.


        Stefan

Re: [PATCH v2 3/3] Start opportunistic GC timer at startup

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org,  Eli Zaretskii <eliz@gnu.org>
> Date: Fri, 04 Dec 2020 18:19:27 -0500
> 
> Maybe what I want to compare it against is the number of commands
> during which the GC is run exactly once?  The idea is to filter out
> those commands which are compute-intensive and hence run the GC
> internally (for which an opportunistic GC is of no use anyway).

What do you mean by "during which"?  Is the time used by redisplay
after a command included or isn't it?

My point is that commands are separate from redisplay in Emacs, and
there's a lot of GC that's unfortunately goes on as part of, or
immediately after, a redisplay cycle in latest versions of Emacs.

> So I added:
> 
>     (defvar gc--opportunistic-single-gc-cmds 0)
>     (let ((last-gcs nil))
>       (add-hook 'pre-command-hook (lambda () (setq last-gcs gcs-done)))
>       (add-hook 'post-command-hook
>                 (lambda ()
>                   (if (eq (1- gcs-done) last-gcs)
>                       (setq gc--opportunistic-single-gc-cmds
>                             (1+ gc--opportunistic-single-gc-cmds))))))
> 
> So far, this seems to indicate that it's working:
> OT1H `gc--opportunistic-single-gc-cmds` stays much lower than
> `gc--opportunistic-counter`, indicating that we seem to be able to avoid
> GC in many cases, and OTOH `gc--opportunistic-counter` is much lower
> than `gcs-done` indicating that we're not excessively increasing the
> number of GCS.

What is the effect on the memory footprint?

Re: [PATCH v2 3/3] Start opportunistic GC timer at startup

[Stefan Monnier]

>> Maybe what I want to compare it against is the number of commands
>> during which the GC is run exactly once?  The idea is to filter out
>> those commands which are compute-intensive and hence run the GC
>> internally (for which an opportunistic GC is of no use anyway).
>
> What do you mean by "during which"?
> Is the time used by redisplay after a command included or isn't it?

I wish it were, but the measurement method I'm using (via
post-command-hook) doesn't do that, sadly.

> My point is that commands are separate from redisplay in Emacs, and
> there's a lot of GC that's unfortunately goes on as part of, or
> immediately after, a redisplay cycle in latest versions of Emacs.

Indeed (tho I don't understand why you say "or immediately after").

>> So I added:
>> 
>>     (defvar gc--opportunistic-single-gc-cmds 0)
>>     (let ((last-gcs nil))
>>       (add-hook 'pre-command-hook (lambda () (setq last-gcs gcs-done)))
>>       (add-hook 'post-command-hook
>>                 (lambda ()
>>                   (if (eq (1- gcs-done) last-gcs)
>>                       (setq gc--opportunistic-single-gc-cmds
>>                             (1+ gc--opportunistic-single-gc-cmds))))))
>> 
>> So far, this seems to indicate that it's working:
>> OT1H `gc--opportunistic-single-gc-cmds` stays much lower than
>> `gc--opportunistic-counter`, indicating that we seem to be able to avoid
>> GC in many cases, and OTOH `gc--opportunistic-counter` is much lower
>> than `gcs-done` indicating that we're not excessively increasing the
>> number of GCS.
>
> What is the effect on the memory footprint?

Haven't noticed any impact (and I don't expect it to have much impact
since, contrary to Andrea's ELisp package, I don't touch the normal
thresholds, so the GCs can only be more frequent).


        Stefan

Re: [PATCH v2 3/3] Start opportunistic GC timer at startup

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: sbaugh@catern.com,  emacs-devel@gnu.org
> Date: Sat, 05 Dec 2020 08:55:50 -0500
> 
> > My point is that commands are separate from redisplay in Emacs, and
> > there's a lot of GC that's unfortunately goes on as part of, or
> > immediately after, a redisplay cycle in latest versions of Emacs.
> 
> Indeed (tho I don't understand why you say "or immediately after").

Simply because I don't know whether GC happens while redisplay runs,
or the first time we call eval/funcall/whatever that checks whether GC
is due.  What I see is frequent GCs "about the same time" as
redisplay, and I never bothered finding out whether it's actually
inside the call to redisplay_internal.

Re: [PATCH v2 3/3] Start opportunistic GC timer at startup

[Stefan Monnier]

>> > My point is that commands are separate from redisplay in Emacs, and
>> > there's a lot of GC that's unfortunately goes on as part of, or
>> > immediately after, a redisplay cycle in latest versions of Emacs.
>> Indeed (tho I don't understand why you say "or immediately after").
> Simply because I don't know whether GC happens while redisplay runs,
> or the first time we call eval/funcall/whatever that checks whether GC
> is due.  What I see is frequent GCs "about the same time" as
> redisplay, and I never bothered finding out whether it's actually
> inside the call to redisplay_internal.

Ah, right, I misread "allocation" where you wrote "GC".

The redisplay can cause a lot of allocation (usually via jit-lock) which
in turn can trigger GC either during redisplay or very soon
after, indeed.


        Stefan

Re: Eager garbage collection

[Eli Zaretskii]

> From: Spencer Baugh <sbaugh@catern.com>
> Cc: emacs-devel@gnu.org, Andrea Corallo <akrl@sdf.org>
> Date: Sun, 22 Nov 2020 00:07:31 -0500
> 
> I'll run this for a while and see how it goes for me...

Thanks.

> This doesn't answer the "What effect does this have on the input latency
> experienced by the user?" question, though, which I think is perhaps the
> most important question.  Not sure how to answer it, since it will
> depend on user configurations and behavior.

For starters, please report your subjective impression from the effect
(or lack thereof) this has on the responsiveness, when you type the
first command after some short period of idleness.

Eager garbage collection

[sbaugh]

Inspired by http://akrl.sdf.org/ and an earlier patch from Stefan
Monnier, I've written the below patch.  Previously, on no user input, we
called maybe_gc, which doesn't do much.  This patch turns that call into
an eager garbage collection attempt.

Ideally, this will reduce the rate of garbage collections happening in
the middle of user operations.

I've tested this a bit and, at least, it seems to successfully trigger
eager garbage collections when there is no user input.

Does this kind of change seem plausible?

diff --git a/src/alloc.c b/src/alloc.c
index 2b3643e35b..33f0a8ab3b 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -5961,6 +5961,16 @@ maybe_garbage_collect (void)
     garbage_collect ();
 }
 
+/* Like maybe_garbage_collect, but with the GC threshold halved as a
+   way to GC eagerly.  The GC threshold will be reset on our next call
+   to maybe_garbage_collect. */
+void
+maybe_garbage_collect_eagerly (void)
+{
+  if (bump_consing_until_gc (gc_cons_threshold/2, Vgc_cons_percentage) < 0)
+    garbage_collect ();
+}
+
 /* Subroutine of Fgarbage_collect that does most of the work.  */
 void
 garbage_collect (void)
diff --git a/src/keyboard.c b/src/keyboard.c
index 49a0a8bd23..da384e9b45 100644
--- a/src/keyboard.c
+++ b/src/keyboard.c
@@ -2752,7 +2752,7 @@ read_char (int commandflag, Lisp_Object map,
 
       /* If there is still no input available, ask for GC.  */
       if (!detect_input_pending_run_timers (0))
-	maybe_gc ();
+	maybe_garbage_collect_eagerly ();
     }
 
   /* Notify the caller if an autosave hook, or a timer, sentinel or
diff --git a/src/lisp.h b/src/lisp.h
index 76d74200ac..8778a07fbb 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3793,6 +3793,7 @@ flush_stack_call_func (void (*func) (void *arg), void *arg)
 
 extern void garbage_collect (void);
 extern void maybe_garbage_collect (void);
+extern void maybe_garbage_collect_eagerly (void);
 extern const char *pending_malloc_warning;
 extern Lisp_Object zero_vector;
 extern EMACS_INT consing_until_gc;

Re: Eager garbage collection

[Stefan Monnier]

> Does this kind of change seem plausible?

I'd be happy to include something like this yes.  Some comments below:

> +/* Like maybe_garbage_collect, but with the GC threshold halved as a
> +   way to GC eagerly.  The GC threshold will be reset on our next call
> +   to maybe_garbage_collect. */

I think the second sentence deserves to be expanded a bit, explaining
why it's OK not to restore the original values (why they'll be reset by
the next call to maybe_garbage_collect and why nothing bad will happen
until then).  Alternatively, we could also just explicitly call
`bump_consing_until_gc` in the else branch and skip the whole discussion.

> +void
> +maybe_garbage_collect_eagerly (void)
> +{
> +  if (bump_consing_until_gc (gc_cons_threshold/2, Vgc_cons_percentage) < 0)
> +    garbage_collect ();
> +}

If your Emacs session is moderately large, `gc_cons_threshold` will be
irrelevant and it'll be Vgc_cons_percentage which will determine the
gc_threshold.

How 'bout we replace

    if (bump_consing_until_gc (gc_cons_threshold/2, Vgc_cons_percentage) < 0)

with

    EMACS_INT since_gc = gc_threshold - consing_until_gc;
    if (since_gc > gc_threshold / N)

where N could be 2 like you had (tho I could see argument for making it
larger, e.g. some people may want to bump the normal threshold by say
5 and then use 10 here, so as to strongly bias Emacs to only ever run
the GC while idle).

>        /* If there is still no input available, ask for GC.  */
>        if (!detect_input_pending_run_timers (0))
> -	maybe_gc ();
> +	maybe_garbage_collect_eagerly ();
>      }

This will cause an eager GC right after Emacs goes idle, which can
happen while the user is actively typing.  I think it would be
preferable to run this from an idle timer to make sure that we run
during an actual pause of incoming events.  Your code effectively uses
an idle-time of 0, and I'm not sure what idle-time we should
use instead.

Admittedly, using an idle time of 0 means we start the GC right at the
beginning of the (potentially short) pause, which also makes it more
likely that we'll have finished GC before the next event comes in.


        Stefan

Re: Eager garbage collection

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Mon, 16 Nov 2020 10:07:58 -0500
> Cc: emacs-devel@gnu.org
> 
> This will cause an eager GC right after Emacs goes idle, which can
> happen while the user is actively typing.  I think it would be
> preferable to run this from an idle timer to make sure that we run
> during an actual pause of incoming events.  Your code effectively uses
> an idle-time of 0, and I'm not sure what idle-time we should
> use instead.
> 
> Admittedly, using an idle time of 0 means we start the GC right at the
> beginning of the (potentially short) pause, which also makes it more
> likely that we'll have finished GC before the next event comes in.

Starting GC immediately when Emacs becomes idle will degrade
responsiveness if there's a lot of garbage, because once GC starts, it
runs to completion no matter what.

So maybe this "eager" GC should also be sensitive to the amount of
garbage, in a sense that it should wait more if there's lot of it.

Re: Eager garbage collection

[Stefan Monnier]

>> This will cause an eager GC right after Emacs goes idle, which can
>> happen while the user is actively typing.  I think it would be
>> preferable to run this from an idle timer to make sure that we run
>> during an actual pause of incoming events.  Your code effectively uses
>> an idle-time of 0, and I'm not sure what idle-time we should
>> use instead.
>> 
>> Admittedly, using an idle time of 0 means we start the GC right at the
>> beginning of the (potentially short) pause, which also makes it more
>> likely that we'll have finished GC before the next event comes in.
>
> Starting GC immediately when Emacs becomes idle will degrade
> responsiveness if there's a lot of garbage, because once GC starts, it
> runs to completion no matter what.

Indeed.

> So maybe this "eager" GC should also be sensitive to the amount of
> garbage, in a sense that it should wait more if there's lot of it.

The time to do a GC doesn't depend on the amount of garbage so much as
the size of the heap, but I think I like your idea.  Better yet: keep
track of the time that each GC takes and use that as a guide for the
idle-time delay.


        Stefan

Re: Eager garbage collection

[yyoncho]

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

>
> Starting GC immediately when Emacs becomes idle will degrade
> responsiveness if there's a lot of garbage, because once GC starts, it
> runs to completion no matter what.
>

IMHO it will be interesting to test how emacs will behave if the GC process
is changed to allow
running a mode in which it will stop in the event of user input. It can be
used for on-idle garbage
collection.

[-- Attachment #2: Type: text/html, Size: 653 bytes --]

Re: Eager garbage collection

[Eli Zaretskii]

> From: yyoncho <yyoncho@gmail.com>
> Date: Wed, 18 Nov 2020 20:00:02 +0200
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, sbaugh@catern.com, 
> 	emacs-devel <emacs-devel@gnu.org>
> 
> IMHO it will be interesting to test how emacs will behave if the GC process is changed to allow
> running a mode in which it will stop in the event of user input.

Can this be done without redesigning the current GC implementation?

Re: Eager garbage collection

[Stefan Monnier]

>> IMHO it will be interesting to test how emacs will behave if the GC
>> process is changed to allow running a mode in which it will stop in
>> the event of user input.
> Can this be done without redesigning the current GC implementation?

It can probably be done with a complete redesign, but I don't think it'd
be a trivial change.


        Stefan

Re: Eager garbage collection

[Stefan Monnier]

>>> IMHO it will be interesting to test how emacs will behave if the GC
>>> process is changed to allow running a mode in which it will stop in
>>> the event of user input.
>> Can this be done without redesigning the current GC implementation?
> It can probably be done with a complete redesign, but I don't think it'd
                          ^^^^
                         without
Duh!


        Stefan