Opportunistic garbage collection

Opportunistic garbage collection

[Stefan Monnier]

I recently bumped into http://akrl.sdf.org/ where they mention a hack of
running the GC from an idle timer, and I was wondering why that would be
a good idea compared to the opportunistic GC we already do.

So I went a look for what we do, and the only thing I found was

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

in src/keyboard.c which doesn't seem to be of any use since this
maybe_gc will very rarely fire: the Elisp code we ran just before should
have called `maybe_gc` already (probably many times, actually).

So unless I missed the other place were we take advantage of idle time
to force an "early" GC, I suggest we install a patch like the one below
(which does more or less what I thought Emacs had been doing all along).

WDYT?


        Stefan


diff --git a/lisp/startup.el b/lisp/startup.el
index a9b58c5e01..33fc901411 100644
--- a/lisp/startup.el
+++ b/lisp/startup.el
@@ -971,6 +971,13 @@ startup--load-user-init-file
     (when debug-on-error-should-be-set
       (setq debug-on-error debug-on-error-from-init-file))))
 
+(defcustom gc-cons-opportunistic-idle-time 5
+  "Number of seconds before trying an opportunistic GC.
+After this number of seconds of idle time, Emacs tries to collect
+garbage more eagerly (i.e. with thresholds halved) in the hope
+to avoid running the GC later during non-idle time."
+  :type 'integer)
+
 (defun command-line ()
   "A subroutine of `normal-top-level'.
 Amongst another things, it parses the command-line arguments."
@@ -1368,6 +1375,16 @@ command-line
 		 (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-cons-opportunistic-idle-time
+    (run-with-idle-timer gc-cons-opportunistic-idle-time t
+                         #'garbage-collect-maybe 2))
+
   (setq after-init-time (current-time))
   ;; Display any accumulated warnings after all functions in
   ;; `after-init-hook' like `desktop-read' have finalized possible
diff --git a/src/alloc.c b/src/alloc.c
index 402fada1ad..14d387861c 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -6016,6 +6016,28 @@ garbage_collect (void)
   garbage_collect_1 (&gcst);
 }
 
+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.  */)
+  (Lisp_Object factor)
+{
+  CHECK_FIXNAT (factor);
+  EMACS_INT fact = XFIXNAT (factor);
+  byte_ct new_csgc = consing_since_gc * fact;
+  if (new_csgc / fact != consing_since_gc)
+    /* Overflow!  */
+    garbage_collect ();
+  else
+    {
+      consing_since_gc = new_csgc;
+      maybe_gc ();
+      consing_since_gc /= fact;
+    }
+  return Qnil;
+}
+
 DEFUN ("garbage-collect", Fgarbage_collect, Sgarbage_collect, 0, 0, "",
        doc: /* Reclaim storage for Lisp objects no longer needed.
 Garbage collection happens automatically if you cons more than
@@ -7416,6 +7438,7 @@ than 2**N, where N is this variable's value.  N should be nonnegative.  */);
   defsubr (&Smake_finalizer);
   defsubr (&Spurecopy);
   defsubr (&Sgarbage_collect);
+  defsubr (&Sgarbage_collect_maybe);
   defsubr (&Smemory_info);
   defsubr (&Smemory_use_counts);
   defsubr (&Ssuspicious_object);
diff --git a/src/keyboard.c b/src/keyboard.c
index dff8f6b2fc..237ced19ca 100644
--- a/src/keyboard.c
+++ b/src/keyboard.c
@@ -2728,7 +2728,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_gc (); /* FIXME: Why?  */
     }
 
   /* Notify the caller if an autosave hook, or a timer, sentinel or

Re: Opportunistic garbage collection

[Paul Eggert]

That sounds like a good idea. Some minor points:

On 4/24/19 1:54 PM, Stefan Monnier wrote:
> +needed to triger automatic allocation took place.  */)

triger -> trigger

> +  (Lisp_Object factor)

Instead of having a factor argument, how about hardwiring in a factor of
2? We can always generalize it later, and maybe we'll never need to
generalize it.

> +  byte_ct new_csgc = consing_since_gc * fact;
> +  if (new_csgc / fact != consing_since_gc)
> +    /* Overflow!  */
> +    garbage_collect ();

This assumes byte_ct is not narrower than EMACS_INT, which isn't true on
32-bit platforms --with-wide-int. It also assumes 'fact' is nonzero,
which might not be true. (Two more reasons to hardwire 2.)

> +      consing_since_gc = new_csgc;
> +      maybe_gc ();
> +      consing_since_gc /= fact;
>
I'd feel better if we didn't muck with the global variable and passed
the smaller consing value directly to a variant of maybe_gc.

>  
>        /* If there is still no input available, ask for GC.  */
>        if (!detect_input_pending_run_timers (0))
> -	maybe_gc ();
> +	maybe_gc (); /* FIXME: Why?  */
>      }
If we don't know why, let's get rid of it....

Re: Opportunistic garbage collection

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Wed, 24 Apr 2019 17:17:45 -0700
> Cc: emacs-devel@gnu.org
> 
> >        /* If there is still no input available, ask for GC.  */
> >        if (!detect_input_pending_run_timers (0))
> > -	maybe_gc ();
> > +	maybe_gc (); /* FIXME: Why?  */
> >      }
> If we don't know why, let's get rid of it....

We know why, we just think this actually causes GC only very rarely.

Re: Opportunistic garbage collection

[Stefan Monnier]

>> >        /* If there is still no input available, ask for GC.  */
>> >        if (!detect_input_pending_run_timers (0))
>> > -	maybe_gc ();
>> > +	maybe_gc (); /* FIXME: Why?  */
>> >      }
>> If we don't know why, let's get rid of it....
> We know why, we just think this actually causes GC only very rarely.

Indeed, I kept it because I'm not 100% sure I understand it enough to
remove it.


        Stefan

Re: Opportunistic garbage collection

[Stefan Monnier]

>> +needed to triger automatic allocation took place.  */)
> triger -> trigger

Thanks.

>> +  byte_ct new_csgc = consing_since_gc * fact;
>> +  if (new_csgc / fact != consing_since_gc)
>> +    /* Overflow!  */
>> +    garbage_collect ();
>
> This assumes byte_ct is not narrower than EMACS_INT, which isn't true on
> 32-bit platforms --with-wide-int.

Does it?  My understanding is that if byte_ct is narrower what happens
is:

1- consing_since_gc is widened to EMACS_INT, preserving the mathematical value.
2- multiplication with `fact`.
3- narrowing the result to byte_ct which will perform the equivalent of
   a "modulo 2^N".  So new_csgc should be mathematically equal to

       (consing_since_gc * fact) mod 2^N

4- widen new_csgs to an EMACS_INT, again without any loss
5- divide by `fact` the result can't be larger than new_csgs.
6- widen consing_since_gc to EMACS_INT
7- compare

So in the end, I believe that we compare

    truncation((consing_since_gc * fact) mod 2^N) / fact

with

    consing_since_gc

so I believe that the inequality test is a reliable way to detect overflow.
What am I missing?

> It also assumes 'fact' is nonzero,

Indeed, I should probably add a check for it.

> which might not be true. (Two more reasons to hardwire 2.)
>
>> +      consing_since_gc = new_csgc;
>> +      maybe_gc ();
>> +      consing_since_gc /= fact;
>>
> I'd feel better if we didn't muck with the global variable and passed
> the smaller consing value directly to a variant of maybe_gc.

Agreed.


        Stefan

Re: Opportunistic garbage collection

[Paul Eggert]

On 4/25/19 11:18 AM, Stefan Monnier wrote:
>
>> This assumes byte_ct is not narrower than EMACS_INT, which isn't true on
>> 32-bit platforms --with-wide-int.
> Does it?  My understanding is that if byte_ct is narrower what happens
> is:
>
> 1- consing_since_gc is widened to EMACS_INT, preserving the mathematical value.
> 2- multiplication with `fact`.

And since that's signed integer multiplication, it can overflow with
undefined behavior.

Re: Opportunistic garbage collection

[Stefan Monnier]

> And since that's signed integer multiplication, it can overflow with
> undefined behavior.

Ah, right, so it's not really the size but the sign: it should be

    EMACS_UINT fact = XFIXNAT (factor);
    

-- Stefan