GNU bug report logs - #54698
non-recursive GC marking [PATCH]

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 54698 in the body.
You can then email your comments to 54698 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: bug-gnu-emacs <at> gnu.org
Subject: non-recursive GC marking [PATCH]
Date: Sun, 3 Apr 2022 20:40:57 +0200

[Message part 1 (text/plain, inline)]

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.

[gc-mark-stack.diff (application/octet-stream, attachment)]

Message #8 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 04 Apr 2022 13:01:46 +0200

Mattias Engdegård <mattiase <at> 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

Message #11 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 4 Apr 2022 13:16:26 +0200

4 apr. 2022 kl. 13.01 skrev Lars Ingebrigtsen <larsi <at> 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.

Message #14 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 04 Apr 2022 13:29:09 +0200

Mattias Engdegård <mattiase <at> 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

Message #17 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 04 Apr 2022 13:31:27 +0200

(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

Message #20 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: larsi <at> gnus.org, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 04 Apr 2022 14:38:44 +0300

> From: Mattias Engdegård <mattiase <at> acm.org>
> Date: Mon, 4 Apr 2022 13:16:26 +0200
> Cc: 54698 <at> 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?

Message #23 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: larsi <at> gnus.org, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 4 Apr 2022 13:57:54 +0200

4 apr. 2022 kl. 13.38 skrev Eli Zaretskii <eliz <at> 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?

Message #26 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: larsi <at> gnus.org, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 04 Apr 2022 15:25:07 +0300

> Feedback-ID:mattiase <at> acm.or
> From: Mattias Engdegård <mattiase <at> acm.org>
> Date: Mon, 4 Apr 2022 13:57:54 +0200
> Cc: larsi <at> gnus.org, 54698 <at> debbugs.gnu.org
> 
> 4 apr. 2022 kl. 13.38 skrev Eli Zaretskii <eliz <at> 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).

Message #29 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <akrl <at> sdf.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 04 Apr 2022 14:32:51 +0000

Mattias Engdegård <mattiase <at> 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

Message #32 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Andrea Corallo <akrl <at> sdf.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 4 Apr 2022 16:39:58 +0200

4 apr. 2022 kl. 16.32 skrev Andrea Corallo <akrl <at> 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?

Message #35 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <akrl <at> sdf.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 04 Apr 2022 15:44:32 +0000

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

> 4 apr. 2022 kl. 16.32 skrev Andrea Corallo <akrl <at> 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

Message #38 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Andrea Corallo <akrl <at> sdf.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 4 Apr 2022 18:04:55 +0200

4 apr. 2022 kl. 17.44 skrev Andrea Corallo <akrl <at> 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.

Message #43 received at 54698-done <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54698-done <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Mon, 4 Apr 2022 19:18:31 +0200

4 apr. 2022 kl. 14.25 skrev Eli Zaretskii <eliz <at> 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 <at> 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).

Message #46 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 05 Apr 2022 09:15:09 +0800

Mattias Engdegård <mattiase <at> 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.

Message #49 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 5 Apr 2022 10:08:11 +0200

5 apr. 2022 kl. 03.15 skrev Po Lu <luangruo <at> 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?

Message #52 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 05 Apr 2022 16:39:30 +0800

Mattias Engdegård <mattiase <at> 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.

Message #55 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <akrl <at> sdf.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 05 Apr 2022 09:10:55 +0000

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

> 4 apr. 2022 kl. 17.44 skrev Andrea Corallo <akrl <at> 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

Message #58 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 5 Apr 2022 13:11:44 +0200

5 apr. 2022 kl. 10.39 skrev Po Lu <luangruo <at> 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.

Message #61 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 05 Apr 2022 19:26:18 +0800

Mattias Engdegård <mattiase <at> 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.

Message #64 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: luangruo <at> yahoo.com, larsi <at> gnus.org, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 05 Apr 2022 14:43:15 +0300

> From: Mattias Engdegård <mattiase <at> acm.org>
> Date: Tue, 5 Apr 2022 10:08:11 +0200
> Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54698 <at> debbugs.gnu.org
> 
> 5 apr. 2022 kl. 03.15 skrev Po Lu <luangruo <at> 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.

Message #67 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Philipp Stephani <p.stephani2 <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: Po Lu <luangruo <at> yahoo.com>,
 Mattias Engdegård <mattiase <at> acm.org>,
 Lars Ingebrigtsen <larsi <at> gnus.org>, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 5 Apr 2022 14:31:17 +0200

Am Di., 5. Apr. 2022 um 13:45 Uhr schrieb Eli Zaretskii <eliz <at> 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.

Message #70 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Philipp Stephani <p.stephani2 <at> gmail.com>
Cc: luangruo <at> yahoo.com, mattiase <at> acm.org, larsi <at> gnus.org, 54698 <at> debbugs.gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Tue, 05 Apr 2022 16:12:59 +0300

> From: Philipp Stephani <p.stephani2 <at> gmail.com>
> Date: Tue, 5 Apr 2022 14:31:17 +0200
> Cc: Mattias Engdegård <mattiase <at> acm.org>, 
> 	Po Lu <luangruo <at> yahoo.com>, Lars Ingebrigtsen <larsi <at> gnus.org>, 54698 <at> 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.

Message #73 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Richard Stallman <rms <at> gnu.org>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: luangruo <at> yahoo.com, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, larsi <at> gnus.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Wed, 06 Apr 2022 00:09:25 -0400

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

Message #76 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Phil Sainty <psainty <at> orcon.net.nz>
To: rms <at> gnu.org
Cc: mattiase <at> acm.org, luangruo <at> yahoo.com, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>, larsi <at> gnus.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Wed, 06 Apr 2022 17:48:07 +1200

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.

Message #79 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: rms <at> gnu.org
Cc: luangruo <at> yahoo.com, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, larsi <at> gnus.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Wed, 06 Apr 2022 13:59:08 +0300

> From: Richard Stallman <rms <at> gnu.org>
> Cc: p.stephani2 <at> gmail.com, luangruo <at> yahoo.com, mattiase <at> acm.org,
> 	larsi <at> gnus.org, 54698 <at> 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.

Message #82 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Wed, 06 Apr 2022 20:05:14 +0800

Eli Zaretskii <eliz <at> 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.

Message #85 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Wed, 06 Apr 2022 15:23:20 +0300

> From: Po Lu <luangruo <at> yahoo.com>
> Cc: rms <at> gnu.org,  p.stephani2 <at> gmail.com,  mattiase <at> acm.org,  larsi <at> gnus.org,
>   54698 <at> 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?

Message #88 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Wed, 06 Apr 2022 20:34:52 +0800

Eli Zaretskii <eliz <at> 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.

Message #91 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: Po Lu <luangruo <at> yahoo.com>, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Wed, 06 Apr 2022 14:52:42 +0200

Eli Zaretskii <eliz <at> 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

Message #94 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Wed, 06 Apr 2022 17:10:52 +0300

> From: Po Lu <luangruo <at> yahoo.com>
> Cc: rms <at> gnu.org,  p.stephani2 <at> gmail.com,  mattiase <at> acm.org,  larsi <at> gnus.org,
>   54698 <at> debbugs.gnu.org
> Date: Wed, 06 Apr 2022 20:34:52 +0800
> 
> Eli Zaretskii <eliz <at> 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.

Message #97 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Richard Stallman <rms <at> gnu.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, eliz <at> gnu.org, 54698 <at> debbugs.gnu.org,
 p.stephani2 <at> gmail.com
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 00:24:00 -0400

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

Message #100 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Richard Stallman <rms <at> gnu.org>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, eliz <at> gnu.org, 54698 <at> debbugs.gnu.org,
 p.stephani2 <at> gmail.com
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 13:49:18 +0800

Richard Stallman <rms <at> 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.

Message #103 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 09:16:45 +0300

> From: Po Lu <luangruo <at> yahoo.com>
> Cc: eliz <at> gnu.org,  p.stephani2 <at> gmail.com,  mattiase <at> acm.org,
>   larsi <at> gnus.org,  54698 <at> debbugs.gnu.org
> Date: Fri, 08 Apr 2022 13:49:18 +0800
> 
> Richard Stallman <rms <at> 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

Message #106 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 15:41:07 +0800

Eli Zaretskii <eliz <at> 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.

Message #109 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 14:15:15 +0300

> From: Po Lu <luangruo <at> yahoo.com>
> Cc: rms <at> gnu.org,  p.stephani2 <at> gmail.com,  mattiase <at> acm.org,  larsi <at> gnus.org,
>   54698 <at> debbugs.gnu.org
> Date: Fri, 08 Apr 2022 15:41:07 +0800
> 
> Eli Zaretskii <eliz <at> 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.

Message #112 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: larsi <at> gnus.org, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 19:32:22 +0800

Eli Zaretskii <eliz <at> 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.

Message #115 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: p.stephani2 <at> gmail.com, mattiase <at> acm.org, Eli Zaretskii <eliz <at> gnu.org>,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 13:55:10 +0200

Po Lu <luangruo <at> 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

Message #118 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: p.stephani2 <at> gmail.com, mattiase <at> acm.org, Eli Zaretskii <eliz <at> gnu.org>,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 19:58:44 +0800

Lars Ingebrigtsen <larsi <at> 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.

Message #121 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: p.stephani2 <at> gmail.com, mattiase <at> acm.org, Eli Zaretskii <eliz <at> gnu.org>,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 14:07:44 +0200

Po Lu <luangruo <at> 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

Message #124 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: luangruo <at> yahoo.com, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 15:13:43 +0300

> From: Lars Ingebrigtsen <larsi <at> gnus.org>
> Cc: Eli Zaretskii <eliz <at> gnu.org>,  rms <at> gnu.org,  p.stephani2 <at> gmail.com,
>   mattiase <at> acm.org,  54698 <at> debbugs.gnu.org
> Date: Fri, 08 Apr 2022 13:55:10 +0200
> 
> Po Lu <luangruo <at> 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.

Message #127 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Po Lu <luangruo <at> yahoo.com>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: p.stephani2 <at> gmail.com, mattiase <at> acm.org, Eli Zaretskii <eliz <at> gnu.org>,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 20:16:27 +0800

Lars Ingebrigtsen <larsi <at> 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.

Message #130 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Po Lu <luangruo <at> yahoo.com>
Cc: p.stephani2 <at> gmail.com, mattiase <at> acm.org, Eli Zaretskii <eliz <at> gnu.org>,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Fri, 08 Apr 2022 15:07:20 +0200

Po Lu <luangruo <at> 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

Message #133 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Phil Sainty <psainty <at> orcon.net.nz>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: Po Lu <luangruo <at> yahoo.com>, mattiase <at> acm.org, p.stephani2 <at> gmail.com,
 54698 <at> debbugs.gnu.org, rms <at> gnu.org
Subject: Re: bug#54698: non-recursive GC marking [PATCH]
Date: Sat, 09 Apr 2022 12:28:54 +1200

On 2022-04-09 01:07, Lars Ingebrigtsen wrote:
> Po Lu <luangruo <at> 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

Message #140 received at 54698 <at> debbugs.gnu.org (full text, mbox):

From: Lynn Winebarger <owinebar <at> gmail.com>
To: 54698 <at> debbugs.gnu.org
Subject: Fwd: GC mark stack
Date: Mon, 27 Jun 2022 08:27:34 -0400

This bug was archived, so I first sent the below to the emacs-devel
list.  I'm not sure what the best/most appropriate target is for the
suggestion.

Lynn

---------- Forwarded message ---------
From: Lynn Winebarger <owinebar <at> gmail.com>
Date: Sun, Jun 26, 2022 at 11:50 AM
Subject: Re: GC mark stack
To: emacs-devel <emacs-devel <at> gnu.org>


On Sun, Jun 26, 2022 at 11:31 AM Lynn Winebarger <owinebar <at> gmail.com> wrote:
>
> I was reviewing alloc.c in the 28.1 source, and noted that it uses a
> semi-naive computation of the transitive closure of the graph of live
> data structures (weak hash tables is where I see it).
> Since the fix to https://debbugs.gnu.org/cgi/bugreport.cgi?bug=54698
> (commit 7a8798de95a57c8ff85f070075e0a0176b458578) moved to using an
> explicit stack, I was curious if you'd considered using a variant of
> Tarjan's SCC algorithm, such as the one described in
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.9019&rep=rep1&type=pdf
> ,
> to guarantee that each edge is traversed at most once.  The algorithm
> described never removes traversed objects from its stack (so it can
> tell when an object has already been traversed, even if the current
> link into it is not part of its SCC).
> The algorithm would only need to account for objects like weak hash
> tables, so a direct implementation would only leave those on the
> stack.  An alternative would be to create an additional field in the
> objects (like weak hash table) recording the order in which they were
> traversed, which also makes the algorithm more efficient since there's
> no stack search involved when determining the SCC representative of
> particular node - it's just a matter of comparing their stack
> ordering.
> Of course, I don't have any idea how much time is spent on this type
> of recursion for weak references.  The SCC-based algorithms can make a
> significant performance improvement compared to semi-naive calculation
> of transitive closure for general relational queries.  It might not be
> so useful when you don't require an explicit enumeration of the set of
> answers.

I should point out here, that with only strong references, there's
only one SCC of interest (liveness) and the mark-bit is exactly the
stack-traversal-ordering count I suggested as an alternative to
keeping items on the stack as in the implementation described in the
paper.  For the more general problem of weak references, the algorithm
requires explicitly tracking the SCC candidate sets and
representatives.  Those structures can also be "pre-allocated" in the
weak reference objects if allocation during garbage collection is an
issue.

Lynn

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.