[EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Pip Cet]

Hello everyone,

I'm typing this in a version of Emacs that uses the SpiderMonkey
(Mozilla's JavaScript engine) garbage collector, which I've just
succeeded in starting for the first time.  It's an experiment, and I'm
perfectly happy to abandon it and leave with what I've learned; but I
think it's an interesting experiment, and it might help those actually
wanting to use a different garbage collector in the official version
of Emacs. Most of the code is available at
https://github.com/pipcet/emacs/tree/c%2B%2B (This code won't work
as-is yet, I'm afraid. I'm trying to figure out how to get the gnulib
files to build for C++. It's also missing some very recent changes.
I'm hoping to fix that soon, but if you actually want to try things,
it might be best to contact me by email. Also, if anyone could help me
find a better place to host free software, that would be very much
appreciated).

Again, this is an experiment. It's currently slow, unstable, contains
known bugs, will not work except on GNU/Linux with X (and with a
specific hacked version of the SpiderMonkey library), leaks memory,
and provides no practical advantages over official Emacs. I'm writing
this now because I'm trying to decide how much more time to spend on
it, and would appreciate comments and feedback. And, of course,
questions!

The main difference between the current mark-and-sweep garbage
collector and the SpiderMonkey garbage collector is that the latter is
a copying garbage collector and precise, meaning that objects may
change address during GC and that only typed values, not memory
locations that might or might not be, must be traced.  A minor
difference is that GC can happen at any time the code is in the
JavaScript API, meaning that we can no longer get away with stretches
of code that "never GC".

I was hoping to find some bugs in official Emacs during this process,
but have been mostly[1] unsuccessful--I have found bugs, but only ones
introduced by my previous changes.

Let me describe in detail some of the changes I made and how I made them:

1. Make Emacs compile with CC="g++" CFLAGS="-fpermissive"

This was harder than it sounds. In fact, I ended up writing a simple
parser for "Emacs C", the unpreprocessed source code as it appears in
the repository, and performing the necessary replacements
automatically.  As a side effect, declarations of the form

    int x, y;

are rewritten to

    int x; int y;

2. Replace Lisp_Object in the source code

My plan was to use JS::Value objects instead of Lisp_Object.

In order to properly use SpiderMonkey, stack objects must be rooted:
I've decided to use separate types for (a) stack values and values in
structs that live on the stack (b) values on the heap (c) values on
structs that live on the heap (d) return values (e) function
arguments. (In order, ELisp_Value, ELisp_Heap_Value,
ELisp_Struct_Value, ELisp_Return_Value, ELisp_Handle).  While
Lisp_Object values need to be protected, pointers to Lisp_Object need
not, so there is a simple ELisp_Pointer type (which is currently
bloated because it determines at run time whether it's pointing to an
ELisp_Value or an ELisp_Struct_Value), as well as vector (resizeable
arrays) and array (fixed size) types.

Luckily, I was able to modify the C-to-C++ conversion script to
determine automatically which of the replacement types to use for most
of the ~10k instances of "Lisp_Object" in the Emacs source code. In
fact, I decided to keep this approach, modifying the C source code as
little as necessary, then turning each .c or .h file in the src
directory into a C++ .c.cc or .h.hh file, then (ideally) not modifying
the resulting C++ files.  It's currently not quite clean that way.

3. Replace lisp.h

The replacement, jslisp.h.hh, defines ELisp_Value etc. to be C++ types
based on SpiderMonkey's JS::Value, which can be a non-NaN double, or
an NaN-boxed object pointer, 32-bit integer[2], undefined, null, or a
JavaScript symbol or string.  I'm only using doubles, integers, and
JavaScript objects. (So strings and symbols are JavaScript objects,
including Qnil). Each object points (using the JS_GetPrivate pointer)
to an unmovable structure in memory, which in turn contains a copy of
the JavaScript value that represents it. This combines the
disadvantages of a moving and a non-moving garbage collector, but it
was good enough for this experiment.

ELisp_Value, for example, is a rooted type which has a non-trivial
constructor which registers the JS::Value it contains in a "root list"
and a destructor that removes it. In ordinary code, you can otherwise
use it much like a Lisp_Object.

Apart from beginning with a JavaScript value, the actual
constant-address structures are mostly unchanged (I moved some
Lisp_Object struct members that previously weren't GC'd (because they
didn't need to be) to the pseudovector Lisp-Object area so I could
trace them).

4. Replace alloc.c

Most of alloc.c is married to the current garbage collector and needed
to be replaced or simplified, in order to leave memory management to
SpiderMonkey.

Instead, a new file, js.c.cc, contains the new rooting/tracing code:
it registers a hook with SpiderMonkey's garbage collector which
traces, directly or indirectly, all Emacs data except for stack
values, which are traced by SpiderMonkey.

5. Stack unwinding

Emacs uses setjmp()/longjmp(). While I think this code can be
converted to use C++ exceptions instead, I decided it would be easier
to make stack unwinding work with SpiderMonkey. The problem is
destructors of intervening stack frames are not called when unwinding
the stack, so we must find and destroy objects in unwind_to_catch.
This turns out to be easily possible, though we violate the
SpiderMonkey API by accessing fields in a private structure: we save a
stack pointer in the struct handler structure, then compare it to the
current stack pointer upon entering unwind_to_catch.  We then walk the
root lists to find all rooted objects that live in the intervening
stack region and destroy them (and do the same for auto-rooted
vectors, which work the same way but use slightly different code).

6. Calling convention

The usual SpiderMonkey calling convention is that functions do not
return GC types; their arguments are "handles", essentially read-only
pointers to JS::Values.  I decided to return JS::Value objects
directly (except for being wrapped in another class), which opens up
 a race condition:  If f1 and f2 are functions returning
ELisp_Return_Type values, it's illegal to call another function g as
g(f1(...), f2(...)).  f1's return value will not be traced if f2
triggers a GC, so if it is moved there will be a segfault (or worse).
It should be possible to further extend my C-to-C++ script to deal
with this by automatically assigning ELisp_Value temporaries in this
situation. I also decided to pass function arguments as JS::Value
objects, rooting them in the callee instead. Both of these decisions
are open to revision.

7. Misc

Some unions were turned into structs in order to ease tracing them.
Some structs had to be duplicated into a stack and a heap version.
Many previously-unrooted (again, because they didn't need to be)
objects were staticpro'd or added directly to the tracing code.
ELisp_Pointer, a data type representing a pointer to a JS::Value, was
modified to require explicitly-named methods rather than operator
overloading to catch bugs. This introduced new bugs. Finally, after
much debugging, Emacs showed me a usable frame.

8. What now?

While I don't think it's right to have SpiderMonkey-specific code in
Emacs, we don't need to: there's pretty much an automatic API between
Emacs and its garbage collector that's good enough for SpiderMonkey,
but can be trivially implemented by the existing mark-and-sweep
garbage collector. I'd like to make that work, by making as little
code as possible depend on the innards of ELisp_Value etc.

I do not advocate switching to this garbage collection mechanism in
the official Emacs, converting the official Emacs to C++, or renaming
all Lisp_Objects in the official Emacs. I do advocate making the
official Emacs compile with G++ with the -fpermissive option, to help
further experiments. I also think that if there are other ways to make
it easier in the future to switch to a more complicated garbage
collector, we should investigate them, but I need to think about this
more.

The C-to-C++ converter seems potentially useful for other projects (my
initial approach was to try coccinelle, but I never got that to work
right), and should be extended to provide temporary variables
automatically, at which point we can change the calling convention
back to one that uses handles for read-only arguments.

Using JSObject structures for everything is wasteful, particularly in
the case of cons cells, which should require only 16 bytes each. I
think it should be possible to modify SpiderMonkey to assign a unique
tag to cons cells, allowing us to get them down to 24 bytes (car, cdr,
and a hash value (we can no longer use the address because that might
change).

I'd like to get away from the dual
constant-address-structure/pointer-only-JSObject approach. We could
use JSObjects to store rarely-needed properties as JavaScript
properties, and store only commonly-used data in the private
structure. In some cases, we can forego a private structure entirely
(cons cells).

9. Unimplemented

This list is incomplete:
 - non-X environments
 - non-GNU/Linux environments
 - weak hash tables
 - finalizers
 - finalizing markers
 - threads (it's unclear to me whether this is possible)
 - modules
 - images and sounds
 - debugging/backtraces
 - dumping (I'm currently using CANNOT_DUMP=yes. Is that supposed to
work? Because it doesn't without a few changes to the initial Lisp
files.) (Again, I'm not sure this will ever work).
 - reduce warnings (-fpermissive produces copious warnings, most of
which are valid and need to be fixed in the code. Right now, I'm
ignoring them as long as the result works.)
 - remove -fpermissive
 - signal handlers need to be protected specially

In the C-to-C++ converter:
 - operator precedence
 - global (not per-chunk) data, such as function prototypes
 - performance

[1] - there's one place that uses "false" for "NULL", and garbage
collection of markers is O(n^2) in the number of markers per buffer,
which means it tends to dominate GCs in some scenarios (including my
typical usage).  Both are trivial to fix.
[2] - JavaScript doesn't distinguish integers from floating-point
numbers, but SpiderMonkey does. This is relevant because Emacs
sometimes uses a floating-point argument to mean something different
from the equivalent integer argument.

Sorry this got quite long! Any comments, private or public, would be
appreciated.

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Paul Eggert]

Wow, sounds like you've done some interesting things, and it's interesting to 
see that you got it to work at all with a copying collector.

> I do advocate making the
> official Emacs compile with G++ with the -fpermissive option, to help
> further experiments.

What changes would this entail? If you're already running Emacs through a 
C-to-C++ converter, why can't the converter arrange for the changes itself?

>  - dumping (I'm currently using CANNOT_DUMP=yes. Is that supposed to
> work? Because it doesn't without a few changes to the initial Lisp
> files.) 

It is supposed to work. Admittedly it's not tested much. We really need to move 
away from the current dumping model anyway, so CANNOT_DUMP mode will grow in 
importance (in some sense).

> [1] - there's one place that uses "false" for "NULL"

Please let us know where, and we'll fix it.

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Pip Cet]

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

On Fri, Nov 24, 2017 at 8:07 AM, Paul Eggert <eggert@cs.ucla.edu> wrote:
> Wow

Thank you.

> sounds like you've done some interesting things, and it's interesting
> to see that you got it to work at all with a copying collector.

"At all" being about the limit of it, at present. While I managed to
write that email without a segfault, there are plenty of race
conditions that I'm aware of. I think we're fine in theory, though,
once we make sure that signal handlers cannot trigger GC. (If my
understanding is correct, signals can occur after every instruction,
including in the middle of a call sequence while the argument, or
return value, is unprotected).

>> I do advocate making the
>> official Emacs compile with G++ with the -fpermissive option, to help
>> further experiments.
>
> What changes would this entail? If you're already running Emacs through a
> C-to-C++ converter, why can't the converter arrange for the changes itself?

You're right, I should be clearer on this point: I want to help out
others who decide not to use my converter, not myself.

One thing that current stable versions of g++ are missing is
structured initializers, and I decided to convert the few instances we
have of those by hand rather than write code to do it. I think, but
I'm not sure, that the current development version of g++ will
correctly deal with those, though.

Another thing is nested structs/enums/unions. I think those are bad
style in addition to presenting a portability concern, even though
they're easy to catch for the converter.

The most vexing issue for me right now is that I haven't figured out
how to get gnulib working with g++ without modifying files after every
sh autogen.sh, though. I admit I don't understand the gnulib build
process at all, so any hints would be appreciated.

The other issues are minor (a union and a typedef sharing a name, C++
keywords, enums treated as ints), but overall it seems a potential
deterrent to people who want to just try linking a C++ library to
Emacs as an experiment, without using my converter.

>>  - dumping (I'm currently using CANNOT_DUMP=yes. Is that supposed to
>> work? Because it doesn't without a few changes to the initial Lisp
>> files.)

> It is supposed to work. Admittedly it's not tested much. We really need to
> move away from the current dumping model anyway, so CANNOT_DUMP mode will
> grow in importance (in some sense).

I'll open a bug for the CANNOT_DUMP issue. While I've got a fairly
good overview regarding the C code, now, I don't understand the Lisp
bootstrapping process, which appears to be the issue...

What do you think about the future of pure space? That also seems to
me to be an optimization that might no longer be worth it, and perhaps
to add even more complexity to the code than dumping does.

>> [1] - there's one place that uses "false" for "NULL"
>
> Please let us know where, and we'll fix it.

Patch attached.

[-- Attachment #2: 0001-Use-NULL-for-NULL-rather-than-false.patch --]
[-- Type: text/x-patch, Size: 878 bytes --]

From eac5f78117b07c76eb725a4653b5d8f70382c165 Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@gmail.com>
Date: Fri, 24 Nov 2017 08:33:22 +0000
Subject: [PATCH] Use NULL for NULL rather than false.

---
 src/xdisp.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/xdisp.c b/src/xdisp.c
index 016e7044caf..7e47c06c2d7 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -31872,7 +31872,7 @@ x_draw_bottom_divider (struct window *w)
       int x1 = WINDOW_RIGHT_EDGE_X (w);
       int y0 = WINDOW_BOTTOM_EDGE_Y (w) - WINDOW_BOTTOM_DIVIDER_WIDTH (w);
       int y1 = WINDOW_BOTTOM_EDGE_Y (w);
-      struct window *p = !NILP (w->parent) ? XWINDOW (w->parent) : false;
+      struct window *p = !NILP (w->parent) ? XWINDOW (w->parent) : NULL;
 
       /* If W is vertically combined and has a sibling below, don't draw
 	 over any right divider.  */
-- 
2.15.0.rc2

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Paul Eggert]

Pip Cet wrote:

> If my understanding is correct, signals can occur after every instruction,
> including in the middle of a call sequence while the argument, or
> return value, is unprotected).

Yes, that's right.

> Another thing is nested structs/enums/unions. I think those are bad
> style in addition to presenting a portability concern, even though
> they're easy to catch for the converter.

It should be OK to fix these, on style grounds. I assume the changes are 
relatively minor.

> The most vexing issue for me right now is that I haven't figured out
> how to get gnulib working with g++ without modifying files after every
> sh autogen.sh, though. I admit I don't understand the gnulib build
> process at all, so any hints would be appreciated.

Emacs has a special way of using Gnulib, unfortunately. I wrote the Gnulib 
interface (sorry! :-) and so can perhaps be of help here. What sort of 
modifications are needed after autogen.sh? Perhaps we can lessen and/or 
eliminate the need for them.

> The other issues are minor (a union and a typedef sharing a name, C++
> keywords, enums treated as ints),

If you would submit patches to fix these, that might help you in future merges. 
Of the three, enums treated as ints seems like it'd be the most hassle, as enums 
are the only way that C has to name small ints that can be used where an integer 
constant expression can be used. I'd hate to have to cast these names to int 
every time I used them, just to pacify C++. Perhaps the enum-to-int business 
could be handled by the C-to-C++ translator instead.

> What do you think about the future of pure space? That also seems to
> me to be an optimization that might no longer be worth it, and perhaps
> to add even more complexity to the code than dumping does.

I tend to agree that pure space is no longer worth the hassle.

>>> [1] - there's one place that uses "false" for "NULL"
> Patch attached.

Thanks, I installed that in your name in the master branch.

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Stefan Monnier]

I must say, this is quite an experiment!

I'm not sure what we should do with it, tho:

- I don't think building Emacs by preprocessing all files through
  a C->C++ converter is going to be a very popular proposition
  (e.g. will make debugging the "C" code even more fun).

- Using a precise GC with the current code base is unrealistic:
  a mostly moving GC is possible, but a fully moving GC would require
  a preprocessing step (see above point).


        Stefan

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Pip Cet]

> I'm not sure what we should do with it, tho:

I think the simple awareness that doing the switch at some point in
the future is feasible is quite enough to satisfy me. Part of what
triggered this was what I perceived as a "switching GCs is impossible,
so let's not worry about it at all" attitude.

My main reason for writing a converter in the first place is that as
the Emacs code base is relatively stable, at least as far as using
regular and well-structured C code goes, there's no rush to do
anything. I'll probably just continue to lurk on the list until I hear
someone say something that makes me think they'd benefit from running
(part of) the converter, then pounce :-), and I hope my converter will
still work then.

> I don't think building Emacs by preprocessing all files through a C->C++ converter is going to be a very popular proposition (e.g. will make debugging the "C" code even more fun).

I agree completely. The current converter uses Perl and Marpa, which
are Free Software but not GNU, so it's definitely not an option.

But let's not make it any harder to eventually move to a moving GC. In
particular, let's require save values to know where their Lisp_Objects
are! I've ignored that issue for now, but "potential Lisp_Object" is a
bad thing to have. (For the same reason, I would like to submit a
patch to change SAFE_ALLOCA to SAFE_ALLOCA_LISP where the latter is
appropriate). I think the current compromise whereby stack values are
conservatively marked and heap values are precisely Lisp Objects or
not is good.

We could, at some point in the future that's definitely not now, have
a flag day and run the preprocessor once[1] to disambiguate what are
currently Lisp_Objects by their uses, all typedef'd to Lisp_Object.
Then switching garbage collectors becomes a matter of providing the
right header file rather than having to go through all the source
code, manually or with a converter. Again, there's no rush and no need
to do everything at once. So

Lisp_Object f(Lisp_Object arg)
{
    Lisp_Object val = XCDR (arg);
    return val;
}

would become

Lisp_Return_Value f(Lisp_Handle arg)
{
     Lisp_Value val = XCDR (arg);
     return val;
}

I don't think that's horrible, though better names could surely be
found, but others might disagree.

[1] I don't think there's a legal issue with merely using Perl and
Marpa to run a converter that I'd gladly transfer copyright of to the
FSF. If there is, please let me know!

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Pip Cet]

On Fri, Nov 24, 2017 at 6:20 PM, Paul Eggert <eggert@cs.ucla.edu> wrote:
> Pip Cet wrote:
>> The most vexing issue for me right now is that I haven't figured out
>> how to get gnulib working with g++ without modifying files after every
>> sh autogen.sh, though. I admit I don't understand the gnulib build
>> process at all, so any hints would be appreciated.
>
> Emacs has a special way of using Gnulib, unfortunately. I wrote the Gnulib
> interface (sorry! :-) and so can perhaps be of help here. What sort of
> modifications are needed after autogen.sh? Perhaps we can lessen and/or
> eliminate the need for them.

I have to remove the memrchr prototype. Editing gnulib.mk seems like
it should help, but for some reason it doesn't; is gnulib.mk
regenerated by autogen.sh, and, if so, how do I change its options?

>> The other issues are minor (a union and a typedef sharing a name, C++
>> keywords, enums treated as ints),
>
>
> If you would submit patches to fix these, that might help you in future
> merges.
> Of the three, enums treated as ints seems like it'd be the most
> hassle, as enums are the only way that C has to name small ints that can be
> used where an integer constant expression can be used. I'd hate to have to
> cast these names to int every time I used them, just to pacify C++. Perhaps
> the enum-to-int business could be handled by the C-to-C++ translator
> instead.

So let's do the first and maybe the keywords, but leave the enums in.

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Paul Eggert]

Pip Cet wrote:

> I have to remove the memrchr prototype.

Why just memrchr? I would think that if it has problems, other gnulib functions 
will have similar problems.

? Editing gnulib.mk seems like
> it should help, but for some reason it doesn't; is gnulib.mk
> regenerated by autogen.sh, and, if so, how do I change its options?

lib/gnulib.mk is regenerated by 'configure'. You can change how this happens by 
changing 'configure.ac', which is the source code for 'configure'.

'configure' creates lib/gnulib.mk by using lib/gnulib.mk.in as a template. This 
template file is created by admin/merge-gnulib, a script that is so obscure and 
so slow that we put its output into the repository (so most developers don't 
have to worry about it or run it).

admin/merge-gnulib gets the template text by running ../gnulib/gnulib-tool, 
which in turn gets the template text from files in ../gnulib/modules/*. Here I'm 
ssuming the Gnulib source code is in a sibling directory to the Emacs source code.

>>> The other issues are minor (a union and a typedef sharing a name, C++
>>> keywords, enums treated as ints),
> ...
> So let's do the first and maybe the keywords, but leave the enums in.

Sounds good.

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Stefan Monnier]

> We could, at some point in the future that's definitely not now, have
> a flag day and run the preprocessor once[1] to disambiguate what are
> currently Lisp_Objects by their uses, all typedef'd to Lisp_Object.

IIUC by that you mean to somehow instrument all Lisp_Objects that are on
the stack (and are currently traced via the conservative stack scanner),
so that we can use a precise collector.

This will only be acceptable if after the switch, invalid code
(e.g. Lisp_Objects on the stack that aren't properly instrumented)
is automatically detected.  After all, we used to have some of that info
(i.e. we used to do precise stack scanning by manually
registering/deregistering Lisp_Objects on the stack.  It wasn't precise
enough for a moving GC, tho), but it was riddled with bugs because it
was only maintained by hand.

> Then switching garbage collectors becomes a matter of providing the
> right header file rather than having to go through all the source
> code, manually or with a converter. Again, there's no rush and no need
> to do everything at once.

No doubt, the GC can be changed.  There's been some attempts at using
the Boehm GC to replace Emacs's current GC, for example.  It never went
much further than an initial proof of concept, but I think it's pretty
clear that it can be done.  It's less clear if it can bring very many
benefits, OTOH (clearly a generational or a concurrent GC would be
desirable in some corner cases, but nowadays the GC is rarely a source
of complaints).

Also I think a non-moving GC will be a lot easier to accommodate.
I'm not sure how your code deals with cases where we take a Lisp_Object
and extract a C pointer from it which we keep long enough to survive
a GC.  Does your GC also trace through char* pointers into buffer text?


        Stefan

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Pip Cet]

On Sat, Nov 25, 2017 at 12:21 AM, Paul Eggert <eggert@cs.ucla.edu> wrote:
> Pip Cet wrote:
>
>> I have to remove the memrchr prototype.
> Why just memrchr? I would think that if it has problems, other gnulib
> functions will have similar problems.

I can't really answer that. I suspect the problem is that memrchr is
overloaded in C++, and the other similarly-overloaded functions do not
require gnulib replacements on my system.

> lib/gnulib.mk is regenerated by 'configure'. You can change how this happens
> by changing 'configure.ac', which is the source code for 'configure'.
>
> 'configure' creates lib/gnulib.mk by using lib/gnulib.mk.in as a template.
> This template file is created by admin/merge-gnulib, a script that is so
> obscure and so slow that we put its output into the repository (so most
> developers don't have to worry about it or run it).
>
> admin/merge-gnulib gets the template text by running ../gnulib/gnulib-tool,
> which in turn gets the template text from files in ../gnulib/modules/*. Here
> I'm ssuming the Gnulib source code is in a sibling directory to the Emacs
> source code.

Thank you! That explanation helps a lot!

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Pip Cet]

On Sat, Nov 25, 2017 at 4:15 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>> We could, at some point in the future that's definitely not now, have
>> a flag day and run the preprocessor once[1] to disambiguate what are
>> currently Lisp_Objects by their uses, all typedef'd to Lisp_Object.
>
> IIUC by that you mean to somehow instrument all Lisp_Objects that are on
> the stack (and are currently traced via the conservative stack scanner),
> so that we can use a precise collector.

Yes, that is, I think, what I'm doing.

> This will only be acceptable if after the switch, invalid code
> (e.g. Lisp_Objects on the stack that aren't properly instrumented)
> is automatically detected.

Hmm. Is that for every build, or as a debugging option? Doing it for
every build is hard, doing it as a debug option should be possible:
after all, there'd be no more Lisp_Objects, just stack values, heap
values, and return values, which could use
__attribute__((constructor)) to check they are indeed on the heap,
stack, or that their __builtin_frame_address changes.

(I'm also treating pointers and arrays specially, but that's mere optimization.)

> After all, we used to have some of that info
> (i.e. we used to do precise stack scanning by manually
> registering/deregistering Lisp_Objects on the stack.  It wasn't precise
> enough for a moving GC, tho), but it was riddled with bugs because it
> was only maintained by hand.

You mean GCPRO? I'm not sure what you mean by "not precise enough"; I
briefly tried using the GCPRO information to keep track of stack
Lisp_Objects, but was defeated because some places didn't GCPRO
variables that they knew to be protected by upstream callers, as well
as the bugs.

>> Then switching garbage collectors becomes a matter of providing the
>> right header file rather than having to go through all the source
>> code, manually or with a converter. Again, there's no rush and no need
>> to do everything at once.
>
> No doubt, the GC can be changed.  There's been some attempts at using
> the Boehm GC to replace Emacs's current GC, for example.  It never went
> much further than an initial proof of concept, but I think it's pretty
> clear that it can be done.  It's less clear if it can bring very many
> benefits, OTOH (clearly a generational or a concurrent GC would be
> desirable in some corner cases, but nowadays the GC is rarely a source
> of complaints).

I guess I'm an exceptional user, then, because I complain about it a
lot. It's very much in embarrassing-pause territory here.

> Also I think a non-moving GC will be a lot easier to accommodate.

I suspect that I don't fully understand the benefits of a moving GC,
because memory fragmentation alone simply has never been a problem for
me.

I've compromised by, as I said, combining the disadvantages of both
approaches (though "disadvantages" can be read as "debugging
opportunities"): Lisp_Objects are JS::Values whose JS_GetPrivate
pointers are constant, even though the JS::Value isn't. So that's
essentially a non-moving GC with extra error checking (because even
Qnil can move (from one non-zero representation to another, too), and
has, which was a little confusing to debug).

> I'm not sure how your code deals with cases where we take a Lisp_Object
> and extract a C pointer from it which we keep long enough to survive
> a GC.

Right now, it doesn't, because the C pointer is constant. It should be
easy enough to convert, say, buffers and real vectors, because they
have accessor methods/macros. Frames would be a lot harder (but then
there are few enough of those that we can just accept they don't
move).

> Does your GC also trace through char* pointers into buffer text?

No.

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Stefan Monnier]

>> This will only be acceptable if after the switch, invalid code
>> (e.g. Lisp_Objects on the stack that aren't properly instrumented)
>> is automatically detected.
> Hmm. Is that for every build, or as a debugging option?

The check doesn't have to be done for every build, but it needs to be
static (i.e. performed during something like compile-time, not
run-time).

> You mean GCPRO?

Yes.

> I'm not sure what you mean by "not precise enough";

I'm referring to the problem you saw:

    ... but was defeated because some places didn't GCPRO variables that
    they knew to be protected by upstream callers...

> I guess I'm an exceptional user, then, because I complain about it a
> lot.  It's very much in embarrassing-pause territory here.

Interesting.  I wonder what part of your use patterns would cause that.
Do you remember of particular situations where this happens, or is it
just kind of all the time?

>> Also I think a non-moving GC will be a lot easier to accommodate.
> I suspect that I don't fully understand the benefits of a moving GC,
> because memory fragmentation alone simply has never been a problem
> for me.

A moving GC is not necessarily better.  It's a popular choice in
languages with high allocation rates, because allocation is extremely
efficient (just move the allocation pointer forward) and because
a stop&copy of the youngest generation can usually recover a lot of
garbage with fairly little effort (because often there are much fewer
live objects in the young region than dead ones, so copying the live
objects is cheaper than (mark&)sweeping the dead ones).

But it's not like it doesn't have downsides.


        Stefan

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Paul Eggert]

Stefan Monnier wrote:
> A moving GC is not necessarily better.  It's a popular choice in
> languages with high allocation rates, because allocation is extremely
> efficient (just move the allocation pointer forward) and because
> a stop&copy of the youngest generation can usually recover a lot of
> garbage with fairly little effort (because often there are much fewer
> live objects in the young region than dead ones, so copying the live
> objects is cheaper than (mark&)sweeping the dead ones).
> 
> But it's not like it doesn't have downsides.

... and then you stopped writing! Just when you were getting to the good part!

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Stefan Monnier]

>> But it's not like it doesn't have downsides.
> ... and then you stopped writing! Just when you were getting to the good part!

Off the top of my head:
- `sxhash-eq` is a lot more painful to implement.
- during GC you need *double* the heap space.  If you only GC a sub-part
  of your heap (e.g. just one generation), then you only need double
  that sub-part.  So if you only use a copy-GC for the youngest generation
  it's not a big deal, but if you use stop&copy over your whole heap,
  we're talking about a 100% overhead on memory usage.
- interaction with C code is significantly more tricky since you really
  need to find *all* the pointers into your objects, including random
  transient ones that aren't Lisp_Object.
  Often, the only sane way out is to disallow access to the actual
  pointers from C: e.g. the C code only manipulates "handles" into an
  array of actual pointers.
- the most obvious concurrent-GC for stop&copy requires a read-barrier
  rather than a write-barrier.

But I do recommend taking a look at the TI Explorer II's garbage
collector, described in the article below.  It's making a really neat
use of the read-barrier!


        Stefan


@Article{Courts88,
  author =       {Robert Courts},
  title =        {Improving locality of reference in garbage-collecting
                  memory management system},
  journal =      CACM,
  year =         1988,
  volume =       31,
  number =       9,
  pages =        {1128-1138},
  doi =          {http://doi.acm.org/10.1145/48529.48536},
  xnote =        {TI Explorer II's GC!!},
  abstract =     {Modern Lisp systems make heavy use of a garbage-collecting
                  style of memory management.  Generally, the locality of
                  reference in garbage-collected systems has been very poor.
                  In virtual memory systems, this poor locality of reference
                  generally causes a large amount of wasted time waiting on
                  page faults or uses excessively large amounts of main
                  memory.  An adaptive memory management algorithm,
                  described in this article, allows substantial improvement
                  in locality of reference.  Performance measurements
                  indicate that page-wait time typically is reduced
                  by a factor of four with constant memory size and disk
                  technology.  Alternately, the size of memory typically can
                  be reduced by a factor of two with constant performance.}
}

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[martin rudalics]

 > I guess I'm an exceptional user, then, because I complain about it a
 > lot. It's very much in embarrassing-pause territory here.
 >
 >> Also I think a non-moving GC will be a lot easier to accommodate.
 >
 > I suspect that I don't fully understand the benefits of a moving GC,
 > because memory fragmentation alone simply has never been a problem for
 > me.

If there is an embarrassing-pause, then using a non-incremental copying
collector won't help anyway.  OTOH XEmacs has an incremental mark and
sweep collector so Emacs should be able to remove the embarrassing-pause
without copying.  But I never looked at the respective codes of XEmacs
and SpiderMonkey so maybe I'm missing something.

martin

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Steve Fink]

> - during GC you need *double* the heap space.  If you only GC a sub-part
>    of your heap (e.g. just one generation), then you only need double
>    that sub-part.  So if you only use a copy-GC for the youngest generation
>    it's not a big deal, but if you use stop&copy over your whole heap,
>    we're talking about a 100% overhead on memory usage.

Yes. The Spidermonkey GC uses moving collection for the nursery 
generation and nonmoving collection for the tenured heap, though it will 
also periodically do a compacting GC of the tenured heap that moves 
things. But the compacting GC breaks the heap into small chunks, so the 
overhead is at most one of those chunks.

And it doesn't do semispace collection; it moves everything from the 
nursery to the tenured heap, so you don't need double the nursery size 
ever. (Not that the nursery is fixed size; it'll double itself if you're 
filling it up fast, up to a maximum size.)

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Steve Fink]

Very interesting! I'm surprised and impressed that someone could get 
this to work, especially in a C project. (Servo is a C project that uses 
spidermonkey, but they do fancy things with the Rust type system and a 
bindings generator to bridge the gap.)

> 2. Replace Lisp_Object in the source code
>
> My plan was to use JS::Value objects instead of Lisp_Object.
>
> In order to properly use SpiderMonkey, stack objects must be rooted:
> I've decided to use separate types for (a) stack values and values in
> structs that live on the stack (b) values on the heap (c) values on
> structs that live on the heap (d) return values (e) function
> arguments. (In order, ELisp_Value, ELisp_Heap_Value,
> ELisp_Struct_Value, ELisp_Return_Value, ELisp_Handle).  While
> Lisp_Object values need to be protected, pointers to Lisp_Object need
> not, so there is a simple ELisp_Pointer type (which is currently
> bloated because it determines at run time whether it's pointing to an
> ELisp_Value or an ELisp_Struct_Value), as well as vector (resizeable
> arrays) and array (fixed size) types.
>
> Luckily, I was able to modify the C-to-C++ conversion script to
> determine automatically which of the replacement types to use for most
> of the ~10k instances of "Lisp_Object" in the Emacs source code. In
> fact, I decided to keep this approach, modifying the C source code as
> little as necessary, then turning each .c or .h file in the src
> directory into a C++ .c.cc or .h.hh file, then (ideally) not modifying
> the resulting C++ files.  It's currently not quite clean that way.

Within Gecko (the Firefox rendering engine) and internally to 
SpiderMonkey, it's very similar though we don't do anything special for 
return values. For a base type of JSObject (the structure actually 
stored in the GC heap), we have

  - JSObject* - return value

  - Rooted<JSObject*> - stack value or member of stack struct.

Rooted is an RAII class that inserts/removes from a list of stack roots.

  - Heap<JSObject*> - member of struct in the heap

  - Handle<JSObject*> - constant parameter, just a type-safe alias for 
JSObject**

  - MutableHandle<JSObject*> - mutable parameter (out parameter), again 
an alias for JSObject**

If you know you're doing stuff that can't GC, then you can just use 
plain JSObject*.

For JS::Value, which boxes up various types of values or pointers, they 
would be Value, Rooted<Value>, Heap<Value>, Handle<Value>, and 
MutableHandle<Value>.

> 6. Calling convention
>
> The usual SpiderMonkey calling convention is that functions do not
> return GC types; their arguments are "handles", essentially read-only
> pointers to JS::Values.  I decided to return JS::Value objects
> directly (except for being wrapped in another class), which opens up
>   a race condition:  If f1 and f2 are functions returning
> ELisp_Return_Type values, it's illegal to call another function g as
> g(f1(...), f2(...)).  f1's return value will not be traced if f2
> triggers a GC, so if it is moved there will be a segfault (or worse).
> It should be possible to further extend my C-to-C++ script to deal
> with this by automatically assigning ELisp_Value temporaries in this
> situation. I also decided to pass function arguments as JS::Value
> objects, rooting them in the callee instead. Both of these decisions
> are open to revision.

A fair number of functions do return GC pointers directly, there's 
really nothing against doing that (in our code base, that is; see 
below). But most of those are allocation functions. The reason why we 
don't generally return GC pointers is not because of the precise GC, but 
rather because we compile without exceptions so the return value is 
reserved for a boolean status.

Early in the precise GC project (we used to have a conservative stack 
scanner), we tried using a different type for return values, but it 
didn't work out.

You are absolutely right about the hazards of g(f1(...), f2(...)). That 
is but one of the tricky patterns that we had littering our code, even 
after we supposedly went through and fixed everything up. We are 
absolutely dependent on a static "rooting hazard" analysis that we run 
on every checkin. The above is one tricky pattern we rely on it for 
detecting. Another is methods on a GC thing; the 'this' pointer will 
implicitly be on the stack and so could get invalidated anytime you GC. 
Probably the trickiest is when you have an RAII class that can GC in its 
destructor, and you're returning a GC pointer -- the pointer could get 
invalidated in between a 'return' statement and the caller resuming! The 
latter is obviously not an issue for a C embedding.

The analysis is implemented as a GCC plugin and postprocessing scripts, 
and in theory can be run on an embedding project's code. In practice, 
it's generally a pain to integrate it into the build system; there are 
wrappers you can put in your path to have it automatically called in 
place of gcc/g++ (the wrappers just invoke gcc with the correct -fplugin 
arguments), but in practice it tends to be a pain to get that to 
cooperate happily with eg configure scripts. I recently tried doing it 
for the GNOME shell, which embeds spidermonkey, but couldn't get their 
build system happy after an hour or two of trying. If you're interested 
in trying, you could find me (sfink) on irc.mozilla.org in the #jsapi 
channel. It's very straightforward to get a list of problems to fix, one 
after another, which should resolve most weird crashes.

The one big thing that the analysis doesn't handle particularly well is 
internal pointers. For now, it sounds like you're mostly safe from these 
moving because all your data is hanging off of the JS_GetPrivate 
indirection, so you wouldn't have any pointers internal to GC things. 
But you can still run into issues keeping things alive. We mostly have 
this problem with strings, since small strings are stored inline in the 
GC things and so it's very easy to end up with a char* that will move. 
We tend to work around this by either (1) passing around the GC pointer 
instead of the char*; (2) making functions that accept such a char* to 
also declare that they won't GC by requiring a reference to an 
'AutoRequireCannotGC&' token, which is validated by the static analysis; 
or (3) forcing the contents to be stored in the malloc heap if they 
aren't already, and just being careful with keeping the owning JSString* 
in a Rooted<JSString*> somewhere higher on the stack.

Collections are also an issue, if you want to index them by GC pointer 
value.

Note that if you disable the nursery (generational GC) and never request 
a compacting GC, then you should be able to use the SpiderMonkey GC as a 
nonmoving collector. It's still precise, so you still have to root 
things to make sure they stay alive, but at least they won't move around 
underneath you. Given the performance benefits of generational 
collection, though, it's probably not the best way to answer the 
question of how to make it possible to swap GC engines.

If you're still suffering from too much time on your hands, you might 
want to compare with the V8 GC embedding API. I don't know too much 
about it, but my impression is that although it's still precise, it has 
a more pleasant root scoping setup that makes it possible to safely 
embed without having a separate static analysis. My anecdotal data 
suggests that people who have used both don't seem to have a clear 
preference for one or the other, so apparently there are other issues. 
But it's another data point as to what would be required to adopt a 
different GC engine. And you've already shown a masochistic streak...

One last note: I don't know how you're doing timings, but DEBUG 
spidermonkey builds are much, much, much slower. We do a crazy amount of 
sanity checking, including redundant whole-heap scans to verify various 
invariants. So develop with DEBUG (the assertions are essential for 
using JSAPI correctly, even for experienced users) but ignore any speed 
estimates until you try a non-DEBUG, preferably optimized build.

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Pip Cet]

On Fri, Dec 1, 2017 at 5:57 PM, Steve Fink <sfink@mozilla.com> wrote:
> Very interesting! I'm surprised and impressed that someone could get this to
> work, especially in a C project. (Servo is a C project that uses
> spidermonkey, but they do fancy things with the Rust type system and a
> bindings generator to bridge the gap.)



> Within Gecko (the Firefox rendering engine) and internally to SpiderMonkey,
> it's very similar though we don't do anything special for return values. For
> a base type of JSObject (the structure actually stored in the GC heap), we
> have
>
>  - JSObject* - return value
>
>  - Rooted<JSObject*> - stack value or member of stack struct.
>
> Rooted is an RAII class that inserts/removes from a list of stack roots.
>
>  - Heap<JSObject*> - member of struct in the heap
>
>  - Handle<JSObject*> - constant parameter, just a type-safe alias for
> JSObject**
>
>  - MutableHandle<JSObject*> - mutable parameter (out parameter), again an
> alias for JSObject**
>
> If you know you're doing stuff that can't GC, then you can just use plain
> JSObject*.
>
> For JS::Value, which boxes up various types of values or pointers, they
> would be Value, Rooted<Value>, Heap<Value>, Handle<Value>, and
> MutableHandle<Value>.

I'm not currently using MutableHandle<>, though I'd like to do so for
array/vector members, which appear to have only non-mutable handle
value types pre-defined.

>> 6. Calling convention
>>
>> The usual SpiderMonkey calling convention is that functions do not
>> return GC types; their arguments are "handles", essentially read-only
>> pointers to JS::Values.  I decided to return JS::Value objects
>> directly (except for being wrapped in another class), which opens up
>>   a race condition:  If f1 and f2 are functions returning
>> ELisp_Return_Type values, it's illegal to call another function g as
>> g(f1(...), f2(...)).  f1's return value will not be traced if f2
>> triggers a GC, so if it is moved there will be a segfault (or worse).
>> It should be possible to further extend my C-to-C++ script to deal
>> with this by automatically assigning ELisp_Value temporaries in this
>> situation. I also decided to pass function arguments as JS::Value
>> objects, rooting them in the callee instead. Both of these decisions
>> are open to revision.

I've since decided to go with the SpiderMonkey calling convention, and
root arguments in the caller, since that allows us to use handles and
those appear to be a performance (and readability) gain.

> A fair number of functions do return GC pointers directly, there's really
> nothing against doing that (in our code base, that is; see below). But most
> of those are allocation functions. The reason why we don't generally return
> GC pointers is not because of the precise GC, but rather because we compile
> without exceptions so the return value is reserved for a boolean status.

Thanks for the clarification!

> You are absolutely right about the hazards of g(f1(...), f2(...)). That is
> but one of the tricky patterns that we had littering our code, even after we
> supposedly went through and fixed everything up. We are absolutely dependent
> on a static "rooting hazard" analysis that we run on every checkin. The
> above is one tricky pattern we rely on it for detecting. Another is methods
> on a GC thing; the 'this' pointer will implicitly be on the stack and so
> could get invalidated anytime you GC. Probably the trickiest is when you
> have an RAII class that can GC in its destructor, and you're returning a GC
> pointer -- the pointer could get invalidated in between a 'return' statement
> and the caller resuming! The latter is obviously not an issue for a C
> embedding.

Well, I'm rewriting the C code to use (some) constructors, so it's
good to be aware of the possibility.

> The analysis is implemented as a GCC plugin and postprocessing scripts, and
> in theory can be run on an embedding project's code. In practice, it's
> generally a pain to integrate it into the build system; there are wrappers
> you can put in your path to have it automatically called in place of gcc/g++
> (the wrappers just invoke gcc with the correct -fplugin arguments), but in
> practice it tends to be a pain to get that to cooperate happily with eg
> configure scripts. I recently tried doing it for the GNOME shell, which
> embeds spidermonkey, but couldn't get their build system happy after an hour
> or two of trying. If you're interested in trying, you could find me (sfink)
> on irc.mozilla.org in the #jsapi channel. It's very straightforward to get a
> list of problems to fix, one after another, which should resolve most weird
> crashes.

That sounds awesome! As Stefan pointed out, it's really essential to
have static analysis catch at least the most obvious bugs when some
people use a different GC from others, so that definitely sounds worth
checking out.

> The one big thing that the analysis doesn't handle particularly well is
> internal pointers. For now, it sounds like you're mostly safe from these
> moving because all your data is hanging off of the JS_GetPrivate
> indirection, so you wouldn't have any pointers internal to GC things. But
> you can still run into issues keeping things alive. We mostly have this
> problem with strings, since small strings are stored inline in the GC things
> and so it's very easy to end up with a char* that will move. We tend to work
> around this by either (1) passing around the GC pointer instead of the
> char*; (2) making functions that accept such a char* to also declare that
> they won't GC by requiring a reference to an 'AutoRequireCannotGC&' token,
> which is validated by the static analysis; or (3) forcing the contents to be
> stored in the malloc heap if they aren't already, and just being careful
> with keeping the owning JSString* in a Rooted<JSString*> somewhere higher on
> the stack.
>
> Collections are also an issue, if you want to index them by GC pointer
> value.

It seems I have two options: rewrite all hashed collections whenever
something moves, or make up a hash value and store it in a private
slot for each object upon creation. My understanding is SpiderMonkey
does the former for WeakMaps, and those seem to perform okay, so that
might be the better option long-term, but I haven't given much thought
to this and the made-up hash value seems easier to implement...

> One last note: I don't know how you're doing timings, but DEBUG spidermonkey
> builds are much, much, much slower. We do a crazy amount of sanity checking,
> including redundant whole-heap scans to verify various invariants. So
> develop with DEBUG (the assertions are essential for using JSAPI correctly,
> even for experienced users) but ignore any speed estimates until you try a
> non-DEBUG, preferably optimized build.

I'm back to developing with DEBUG after trying for a few builds to see
what performance is like. (And it's caught bugs, so I'll be careful to
keep it that way.) I suspect I'll get back to you about the
performance issues, but so far the most obvious ones are my fault.

Re: [EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Steve Fink]

On 12/2/17 4:37 PM, Pip Cet wrote:
> On Fri, Dec 1, 2017 at 5:57 PM, Steve Fink <sfink@mozilla.com> wrote:
>
>> The one big thing that the analysis doesn't handle particularly well is
>> internal pointers. For now, it sounds like you're mostly safe from these
>> moving because all your data is hanging off of the JS_GetPrivate
>> indirection, so you wouldn't have any pointers internal to GC things. But
>> you can still run into issues keeping things alive. We mostly have this
>> problem with strings, since small strings are stored inline in the GC things
>> and so it's very easy to end up with a char* that will move. We tend to work
>> around this by either (1) passing around the GC pointer instead of the
>> char*; (2) making functions that accept such a char* to also declare that
>> they won't GC by requiring a reference to an 'AutoRequireCannotGC&' token,
>> which is validated by the static analysis; or (3) forcing the contents to be
>> stored in the malloc heap if they aren't already, and just being careful
>> with keeping the owning JSString* in a Rooted<JSString*> somewhere higher on
>> the stack.
>>
>> Collections are also an issue, if you want to index them by GC pointer
>> value.
> It seems I have two options: rewrite all hashed collections whenever
> something moves, or make up a hash value and store it in a private
> slot for each object upon creation. My understanding is SpiderMonkey
> does the former for WeakMaps, and those seem to perform okay, so that
> might be the better option long-term, but I haven't given much thought
> to this and the made-up hash value seems easier to implement...

We've done it two ways, gradually shifting almost everything over to the 
second.

The first was what we called "rekeying", which is just removing and 
re-inserting anything whose pointer changed (or more generally, when any 
pointer that formed part of the key changed.) We had to do some careful 
dancing in our hashtable implementation to be certain rekeying can't 
cause the table to grow (we have tombstones, so the naive approach 
accumulates tombstones.) Most things are now switching over to the 
second approach, which is to key tables off of unique ids. We have a 
separate table mapping anything that needs one to a unique id. But 
that's still just a space optimization; if all of your objects are going 
to end up needing a unique id, then you're paying the extra memory cost 
for everything anyway and you may as well store a hash (or unique id), 
as you say.

If these tables aren't holding strong references (if being a key in the 
table shouldn't keep the key alive), then you need to sweep them too, to 
throw out all of the dead stuff. Even if nothing ever looks up those 
keys again, hash collisions will have you comparing their dead memory 
with lookup keys. And if you have code to sweep the table, I guess you 
can always reuse it during the moving part of the collection to rekey 
everything that is moving. (And if they *are* holding strong references, 
they should be traced.)

The embedder API to hook into this can be seen at 
https://searchfox.org/mozilla-central/source/js/public/GCAPI.h#926

We use GC-aware data structures within spidermonkey (GCHashMap, 
GCHashSet, GCVector) to automate most of this. See eg 
https://searchfox.org/mozilla-central/source/js/public/GCHashTable.h#28 
though even those still require something to call their sweep() methods. 
The WeakCache at 
https://searchfox.org/mozilla-central/source/js/public/SweepingAPI.h#54 
sets itself up to be swept automatically at the right time.

And like I said, those generally use unique IDs. 
https://searchfox.org/mozilla-central/source/js/public/GCHashTable.h#105 
is the hashtable that rekeys instead. (Note that our hashtable 
implementation isn't great. It uses double hashing, and probably ought 
to be replaced with one of the Robin Hood variants, which would change 
rekeying.)