9 ms·

Let's make the Emacs GC safe and iterative

208 points by noch 9y ago

deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
mav3r1ck 9y ago
Interesting. So that's why emacs whigs out sometimes when trying to open very large files: because it has a recursive GC that has trouble when it runs out of stack space. Assuming I read the first statement correctly. Seems like a welcome change. I'm not too well versed with the internals, but does 4.6MB seem reasonable for a memory footprint? I mean, compared to Slack, not bad. > The naive version of this scheme needs about 4.6MB of overhead on my current 20MB Emacs heap, but it should be possible to reduce the overhead significantly by taking advantage of the block allocation we do for conses and other types --- we can put whole blocks on the queue instead of pointers to individual block parts, so we can get away with a much smaller queue.
- harrygeez 9y ago
  Not to be rude but Electron apps' level of footprint has always been a compromise and should not be used to justify extraneous resource usage. Emacs must be able to run from the console and resource-constrained systems like AWS instances, where 5mb of RAM can make a difference.
  - AceJohnny2 9y ago
    Remember when people joked that EMACS stood for "Eats Memory And CPU Superbly?" And then each generation reinvents its state-of-the-art abstracted memory hog... Edit: more jokes, from 1985: https://github.com/sbp/lemacs/blob/master/etc/emacs.names https://github.com/sbp/lemacs/blob/master/etc/emacs.names
    - s_kilk 9y ago
      Eight Megs And Constantly Swapping
      - kazinator 9y ago
        Precisely relevant to the issue at hand: Eight Megs Ain't Comfortable Stack
  - craftkiller 9y ago
    If 5mb of ram makes the difference wouldn't that be the time to try mg[1] or edit remotely using tramp? Certainly agree that Electron should not be used as a justification. [1] https://en.wikipedia.org/wiki/Mg_(editor) https://en.wikipedia.org/wiki/Mg_(editor)
    - defgeneric 9y ago
      As of late I've been using `emacs --daemon=some-name` on instances. I attach with `emacs-client -s some-name -t` after I ssh in and detach with `C-x 5-0`. Sometimes I'll run multiple named emacs daemons. This has worked really well to keep persistent independent workspaces on remote instances. Tramp was always a headache and running emacs in screen tends to introduce terminal color and keybinding problems.
    - nerdponx 9y ago
      How does mg differ from Emacs proper?
      - msds 9y ago
        It's a text editor, not a lisp environment that edits text. I once had a decent amount of fun splicing it with Lua, before deciding that I don't actually care about text editors...
  - cwyers 9y ago
    https://www.gnu.org/software/emacs/manual/html_node/emacs/Remote-Files.html https://www.gnu.org/software/emacs/manual/html_node/emacs/Re...
- coldacid 9y ago
  An additional overhead between 20% and 25% definitely doesn't feel reasonable to me. Hopefully this isn't linear.
  - greglindahl 9y ago
    It must strongly depend on what you've got activated; when I edit multi-gigabyte files I start up with '-q' so my init file doesn't turn on FlySpell.
  - quotemstr 9y ago
    It's not reasonable to me either. That's the naive version. :-) There are various tricks for reducing the overhead to insignificance.
- pulisse 9y ago
  So that's why emacs whigs out sometimes when trying to open very large files: because it has a recursive GC that has trouble when it runs out of stack space. Assuming I read the first statement correctly. That doesn't seem right to me. (a) In emacs a file's contents aren't stored in a deeply nested structure, no matter what the size. It's a gap buffer. (b) Structure aside, that buffer isn't a Lisp object, but an object internal to the C level, so not subject to GC. And note that Emacs's large file behavior isn't especially different than other non-minimalist editors[1]. https://github.com/jhallen/joes-sandbox/tree/master/editor-perf#time-to-load-3-gb-file-insert-character-at-start-and-exit https://github.com/jhallen/joes-sandbox/tree/master/editor-p...
- pulisse 9y ago
  If you read further in the thread you'll see that Stefan Monnier pointed out that using a stack instead of a queue for the objects would consume less memory than the current GC implementation.
cwzwarich 9y ago
Why don't they just use the Deutsch-Schorr-Waite algorithm to store the mark stack in the heap itself with pointer-reversal tricks? This would remove the additional overhead.
- ptc 9y ago
  I believe something similar (maybe exactly that) was suggested later on in the thread.
- sillysaurus3 9y ago
  Emacs likes pointer reversal tricks! https://github.com/emacs-mirror/emacs/blob/cc8ae51e6f62f86d07c82c6ab7ce162150fae448/src/eval.c#L3710-L3716 https://github.com/emacs-mirror/emacs/blob/cc8ae51e6f62f86d0... (Unrelated, but an amusing coincidence.)
- rurban 9y ago
  Much better would be a copying collector, like a twofinger collector, because emacs doesn't have much foreign pointers for political reasons, which can be handled separately. No stack, much faster, much slimmer.
  - sillysaurus3 9y ago
    emacs doesn't have much foreign pointers for political reasons This is an interesting connection. Could you elaborate on this?
    - quotemstr 9y ago
      We support external modules these days. I specifically designed its interface to allow for a moving collector. The current implementation of the C core, however, precludes such a thing.
  - kazinator 9y ago
    Copying collectors can handle foreign pointers. Why? Because foreign pointers can be managed via handle records. Those handle records are GC objects with a type tag and all that; they hold the foreign pointer as an opaque machine word in one of their fields. The handles themselves can be moved around by a copying/compacting allocator. Of course, the foreign objects aren't. You typically don't even know their size. They could be things like a library handle returned by dlopen(): don't even think about moving that. They could also be pointers into the middle of some object; a displaced C pointer can enter the GC world as a foreign pointer.
kazinator 9y ago
It alrady handles long lists without recursion: case Lisp_Cons: { register struct Lisp_Cons *ptr = XCONS (obj); if (CONS_MARKED_P (ptr)) break; CHECK_ALLOCATED_AND_LIVE (live_cons_p); CONS_MARK (ptr); /* If the cdr is nil, avoid recursion for the car. */ if (EQ (ptr->u.s.u.cdr, Qnil)) { obj = ptr->u.s.car; cdr_count = 0; goto loop; } mark_object (ptr->u.s.car); obj = ptr->u.s.u.cdr; cdr_count++; if (cdr_count == mark_object_loop_halt) emacs_abort (); goto loop; } The "goto loop" chases the cdr pointer iteratively. So with regard to list structure, this will only blow the stack if you have deep car recursion. When conses are used to represent nested lists, you don't get that much depth on the CAR side. I'm just wondering what is the exact scenario, involving what structure. Of course there can be other kinds of linked objects. E.g. a huge graph structure, where the GC happens to traverse a very long path through the graph before bottoming out somewhere. BTW, "[i]f the cdr is nil, avoid recursion for the car." Initial reaction: good frickin' idea and I'm stealing it immediately. Though, wait, not sure what it buys you in practical terms; who the heck builds a deep structure of conses where the linkage is through car and the cdr-s are nil. A better test might be for the cdr being any atom at all. Though obviously some kinds of atoms are structures with pointers that can have depth behind them, many kinds of atoms are shallow. If a cons has any atom whatsoever as its cdr, then maybe we should recurse on the cdr and tail loop on the car. Analysis required.
- sebcat 9y ago
  > I'm just wondering what is the exact scenario, involving what structure. > Was: Re: bug#30626 (seq-doseq (_ (stream-range 1 1000000)) nil)
  - kazinator 9y ago
    https://debbugs.gnu.org/cgi/bugreport.cgi?bug=+bug%2330626 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=+bug%2330626 Looks like an X Y problem here. Let's fix the garbage collector (X) because of some badly implemented lazy processing (Y) where the real issue is. I don't believe anyone has a filesystem that can't be traversed by a lazy data structure in Lisp, with a recursive GC, in 8 megs of stack. (Unless, say, the traversal is being fooled by cycles created by directory symlinks.)
kazinator 9y ago
> We need to fix GC being deeply recursive once and for all. Tweaking stack sizes on various platforms and trying to spot-fix GC for the occasional deeply recursive structure is annoying. Here's my proposal: There is still a default stack size limit of 8 megabytes on Linux, even though consumer machines nowadays have RAM measured in double-digit gigabytes. On an Ubuntu 16.x machine: $ ulimit -a | grep stack stack size (kbytes, -s) 8192 $ free -h total used free shared buff/cache available Mem: 15G 4.1G 2.8G 600M 8.7G 10G Swap: 14G 626M 13G This 8192 kbytes has not changed in at least 15 years, unlike that 15G. Slight disconnect there. This 8192 is just the soft limit; applications can raise it up to the root-imposed hard limit. Unfortunately, that tends to be only 4X larger than the 8192: $ ulimit -s 32769 bash: ulimit: stack size: cannot modify limit: Operation not permitted $ ulimit -s 32768 $ # OK Clearly, the hard limit needs revision too. Threads are another issue; if you have a "can run in any thread" garbage collector, it has to live within a thread stack. You can't have huge stacks for each of a large number of threads. A thread's stack cannot be temporarily extended; there may be something in the address space preventing it, since it's just another mmap. (Don't think Emacs has this problem. :)
- quotemstr 9y ago
  > There is still a default stack size limit of 8 megabytes on Linux, even though consumer machines nowadays have RAM measured in double-digit gigabytes. Current stack sizes are fine; storing large amounts of information on the stack usually isn't a good idea anyway, and makes tools like debuggers and perf(1) slow and awkward. Besides, the ulimit means nothing. If you really want, you can allocate your own "stack", as large as you want, and switch to it. I just wouldn't recommend it. > A thread's stack cannot be temporarily extended; there may be something in the address space preventing it, since it's just another mmap. You might be interested in the split stack model, described here [1]. You definitely can grow a thread's stack as needed. The approach has various issues (which is why Rust eventually went with conventional stacks), but it certainly works. [1] https://gcc.gnu.org/wiki/SplitStacks https://gcc.gnu.org/wiki/SplitStacks
  - 9y ago
kazinator 9y ago
I wonder if a hybrid approach is possible. Run GC recursively. Arrange for the segfault to run on an alternative stack (sigaltstack). If a segfault occurs due to insufficient stack space, then do the rest of the GC using the "queue draining loop" approach, within the small amount of alternative stack memory. Then longmp to some point in the original GC to bail out the original stack.
- kazinator 9y ago
  In my TXR Lisp, the "alt stack" is used transparently to the programmer. So we can catch a stack segfault. This is exploited in the solution to the Rosetta Code "Find Limits of Recursion" task: https://rosettacode.org/wiki/Find_limit_of_recursion#TXR https://rosettacode.org/wiki/Find_limit_of_recursion#TXR The implementation code is here: http://www.kylheku.com/cgit/txr/tree/signal.c http://www.kylheku.com/cgit/txr/tree/signal.c Search for "setup_alt_stack" and "teardown_alt_stack". Basically, this allows a Lisp signal handler lambda to execute even though the stack has been blown. What if this is in the middle of gc? We can't run Lisp code with a heap that is the middle of gc, due to objects being marked and such. That situation is detected and a function called gc_cancel is called to simply cancel gc. Everything that has been marked is unmarked. To bring the gc machine to the most obvious safe state, all the structures related to generational gc are reset, and a full gc is scheduled. With that implemented, the above Rosetta task became reliable; the random failures it exhibited were gone. Users programs (on platforms supporting sigaltstack) have a fighting chance to do something if gc runs out of stack, like save some data to disk or whatever.
- quotemstr 9y ago
  Why would you bother supporting both approaches? It's not as if the recursive approach is any more efficient --- and whether or not you start with the recursive approach, you need to keep memory reserved for a worst case queue traversal.
  - kazinator 9y ago
    For one thing, because the recursive approach is debugged. If we can show that the new code doesn't change what the old code is doing when that case is not triggered, then then we can be confident that a bug hasn't been introduced.
dawg 9y ago
Did sth. similar a while ago for our not so great D GC. https://github.com/dlang/druntime/pull/1073 https://github.com/dlang/druntime/pull/1073
gnufx 9y ago
This talks about possible generational GC. Incremeantal/generational was available many years ago with a port to the Boehm collector. I never understood rejecting it and generally spending effort on a bespoke collector. (I don't remember whether the Ravenbrook system was available at the time, or if it was unsuitable for some reason.)
olliej 9y ago
Super dumb question: why not just use a queue, and visit the objects iteratively? Eg each visited object appends/prepends its children to the queue of objects to visit, and you just repeatedly drain until you have an empty list. That’s what I had to do many years ago for the GC I was working on. Then any special cases (like the cons case referenced elsewhere) just becomes performance optimization rather than “don’t crash” correctness

208 points by noch 9y ago

deleted 9y ago

[deleted]

deleted 9y ago

[deleted]

mav3r1ck 9y ago

Interesting. So that's why emacs whigs out sometimes when trying to open very large files: because it has a recursive GC that has trouble when it runs out of stack space. Assuming I read the first statement correctly. Seems like a welcome change. I'm not too well versed with the internals, but does 4.6MB seem reasonable for a memory footprint? I mean, compared to Slack, not bad. > The naive version of this scheme needs about 4.6MB of overhead on my current 20MB Emacs heap, but it should be possible to reduce the overhead significantly by taking advantage of the block allocation we do for conses and other types --- we can put whole blocks on the queue instead of pointers to individual block parts, so we can get away with a much smaller queue.

harrygeez 9y ago
Not to be rude but Electron apps' level of footprint has always been a compromise and should not be used to justify extraneous resource usage. Emacs must be able to run from the console and resource-constrained systems like AWS instances, where 5mb of RAM can make a difference.
- AceJohnny2 9y ago
  Remember when people joked that EMACS stood for "Eats Memory And CPU Superbly?" And then each generation reinvents its state-of-the-art abstracted memory hog... Edit: more jokes, from 1985: https://github.com/sbp/lemacs/blob/master/etc/emacs.names https://github.com/sbp/lemacs/blob/master/etc/emacs.names
  - s_kilk 9y ago
    Eight Megs And Constantly Swapping
    - kazinator 9y ago
      Precisely relevant to the issue at hand: Eight Megs Ain't Comfortable Stack
- craftkiller 9y ago
  If 5mb of ram makes the difference wouldn't that be the time to try mg[1] or edit remotely using tramp? Certainly agree that Electron should not be used as a justification. [1] https://en.wikipedia.org/wiki/Mg_(editor) https://en.wikipedia.org/wiki/Mg_(editor)
  - defgeneric 9y ago
    As of late I've been using `emacs --daemon=some-name` on instances. I attach with `emacs-client -s some-name -t` after I ssh in and detach with `C-x 5-0`. Sometimes I'll run multiple named emacs daemons. This has worked really well to keep persistent independent workspaces on remote instances. Tramp was always a headache and running emacs in screen tends to introduce terminal color and keybinding problems.
  - nerdponx 9y ago
    How does mg differ from Emacs proper?
    - msds 9y ago
      It's a text editor, not a lisp environment that edits text. I once had a decent amount of fun splicing it with Lua, before deciding that I don't actually care about text editors...
- cwyers 9y ago
  https://www.gnu.org/software/emacs/manual/html_node/emacs/Remote-Files.html https://www.gnu.org/software/emacs/manual/html_node/emacs/Re...
coldacid 9y ago
An additional overhead between 20% and 25% definitely doesn't feel reasonable to me. Hopefully this isn't linear.
- greglindahl 9y ago
  It must strongly depend on what you've got activated; when I edit multi-gigabyte files I start up with '-q' so my init file doesn't turn on FlySpell.
- quotemstr 9y ago
  It's not reasonable to me either. That's the naive version. :-) There are various tricks for reducing the overhead to insignificance.
pulisse 9y ago
So that's why emacs whigs out sometimes when trying to open very large files: because it has a recursive GC that has trouble when it runs out of stack space. Assuming I read the first statement correctly. That doesn't seem right to me. (a) In emacs a file's contents aren't stored in a deeply nested structure, no matter what the size. It's a gap buffer. (b) Structure aside, that buffer isn't a Lisp object, but an object internal to the C level, so not subject to GC. And note that Emacs's large file behavior isn't especially different than other non-minimalist editors[1]. https://github.com/jhallen/joes-sandbox/tree/master/editor-perf#time-to-load-3-gb-file-insert-character-at-start-and-exit https://github.com/jhallen/joes-sandbox/tree/master/editor-p...
pulisse 9y ago
If you read further in the thread you'll see that Stefan Monnier pointed out that using a stack instead of a queue for the objects would consume less memory than the current GC implementation.

cwzwarich 9y ago

Why don't they just use the Deutsch-Schorr-Waite algorithm to store the mark stack in the heap itself with pointer-reversal tricks? This would remove the additional overhead.

ptc 9y ago
I believe something similar (maybe exactly that) was suggested later on in the thread.
sillysaurus3 9y ago
Emacs likes pointer reversal tricks! https://github.com/emacs-mirror/emacs/blob/cc8ae51e6f62f86d07c82c6ab7ce162150fae448/src/eval.c#L3710-L3716 https://github.com/emacs-mirror/emacs/blob/cc8ae51e6f62f86d0... (Unrelated, but an amusing coincidence.)
rurban 9y ago
Much better would be a copying collector, like a twofinger collector, because emacs doesn't have much foreign pointers for political reasons, which can be handled separately. No stack, much faster, much slimmer.
- sillysaurus3 9y ago
  emacs doesn't have much foreign pointers for political reasons This is an interesting connection. Could you elaborate on this?
  - quotemstr 9y ago
    We support external modules these days. I specifically designed its interface to allow for a moving collector. The current implementation of the C core, however, precludes such a thing.
- kazinator 9y ago
  Copying collectors can handle foreign pointers. Why? Because foreign pointers can be managed via handle records. Those handle records are GC objects with a type tag and all that; they hold the foreign pointer as an opaque machine word in one of their fields. The handles themselves can be moved around by a copying/compacting allocator. Of course, the foreign objects aren't. You typically don't even know their size. They could be things like a library handle returned by dlopen(): don't even think about moving that. They could also be pointers into the middle of some object; a displaced C pointer can enter the GC world as a foreign pointer.

kazinator 9y ago

It alrady handles long lists without recursion: case Lisp_Cons: { register struct Lisp_Cons *ptr = XCONS (obj); if (CONS_MARKED_P (ptr)) break; CHECK_ALLOCATED_AND_LIVE (live_cons_p); CONS_MARK (ptr); /* If the cdr is nil, avoid recursion for the car. */ if (EQ (ptr->u.s.u.cdr, Qnil)) { obj = ptr->u.s.car; cdr_count = 0; goto loop; } mark_object (ptr->u.s.car); obj = ptr->u.s.u.cdr; cdr_count++; if (cdr_count == mark_object_loop_halt) emacs_abort (); goto loop; } The "goto loop" chases the cdr pointer iteratively. So with regard to list structure, this will only blow the stack if you have deep car recursion. When conses are used to represent nested lists, you don't get that much depth on the CAR side. I'm just wondering what is the exact scenario, involving what structure. Of course there can be other kinds of linked objects. E.g. a huge graph structure, where the GC happens to traverse a very long path through the graph before bottoming out somewhere. BTW, "[i]f the cdr is nil, avoid recursion for the car." Initial reaction: good frickin' idea and I'm stealing it immediately. Though, wait, not sure what it buys you in practical terms; who the heck builds a deep structure of conses where the linkage is through car and the cdr-s are nil. A better test might be for the cdr being any atom at all. Though obviously some kinds of atoms are structures with pointers that can have depth behind them, many kinds of atoms are shallow. If a cons has any atom whatsoever as its cdr, then maybe we should recurse on the cdr and tail loop on the car. Analysis required.

sebcat 9y ago
> I'm just wondering what is the exact scenario, involving what structure. > Was: Re: bug#30626 (seq-doseq (_ (stream-range 1 1000000)) nil)
- kazinator 9y ago
  https://debbugs.gnu.org/cgi/bugreport.cgi?bug=+bug%2330626 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=+bug%2330626 Looks like an X Y problem here. Let's fix the garbage collector (X) because of some badly implemented lazy processing (Y) where the real issue is. I don't believe anyone has a filesystem that can't be traversed by a lazy data structure in Lisp, with a recursive GC, in 8 megs of stack. (Unless, say, the traversal is being fooled by cycles created by directory symlinks.)

kazinator 9y ago

> We need to fix GC being deeply recursive once and for all. Tweaking stack sizes on various platforms and trying to spot-fix GC for the occasional deeply recursive structure is annoying. Here's my proposal: There is still a default stack size limit of 8 megabytes on Linux, even though consumer machines nowadays have RAM measured in double-digit gigabytes. On an Ubuntu 16.x machine: $ ulimit -a | grep stack stack size (kbytes, -s) 8192 $ free -h total used free shared buff/cache available Mem: 15G 4.1G 2.8G 600M 8.7G 10G Swap: 14G 626M 13G This 8192 kbytes has not changed in at least 15 years, unlike that 15G. Slight disconnect there. This 8192 is just the soft limit; applications can raise it up to the root-imposed hard limit. Unfortunately, that tends to be only 4X larger than the 8192: $ ulimit -s 32769 bash: ulimit: stack size: cannot modify limit: Operation not permitted $ ulimit -s 32768 $ # OK Clearly, the hard limit needs revision too. Threads are another issue; if you have a "can run in any thread" garbage collector, it has to live within a thread stack. You can't have huge stacks for each of a large number of threads. A thread's stack cannot be temporarily extended; there may be something in the address space preventing it, since it's just another mmap. (Don't think Emacs has this problem. :)

quotemstr 9y ago
> There is still a default stack size limit of 8 megabytes on Linux, even though consumer machines nowadays have RAM measured in double-digit gigabytes. Current stack sizes are fine; storing large amounts of information on the stack usually isn't a good idea anyway, and makes tools like debuggers and perf(1) slow and awkward. Besides, the ulimit means nothing. If you really want, you can allocate your own "stack", as large as you want, and switch to it. I just wouldn't recommend it. > A thread's stack cannot be temporarily extended; there may be something in the address space preventing it, since it's just another mmap. You might be interested in the split stack model, described here [1]. You definitely can grow a thread's stack as needed. The approach has various issues (which is why Rust eventually went with conventional stacks), but it certainly works. [1] https://gcc.gnu.org/wiki/SplitStacks https://gcc.gnu.org/wiki/SplitStacks
- 9y ago

kazinator 9y ago

I wonder if a hybrid approach is possible. Run GC recursively. Arrange for the segfault to run on an alternative stack (sigaltstack). If a segfault occurs due to insufficient stack space, then do the rest of the GC using the "queue draining loop" approach, within the small amount of alternative stack memory. Then longmp to some point in the original GC to bail out the original stack.

kazinator 9y ago
In my TXR Lisp, the "alt stack" is used transparently to the programmer. So we can catch a stack segfault. This is exploited in the solution to the Rosetta Code "Find Limits of Recursion" task: https://rosettacode.org/wiki/Find_limit_of_recursion#TXR https://rosettacode.org/wiki/Find_limit_of_recursion#TXR The implementation code is here: http://www.kylheku.com/cgit/txr/tree/signal.c http://www.kylheku.com/cgit/txr/tree/signal.c Search for "setup_alt_stack" and "teardown_alt_stack". Basically, this allows a Lisp signal handler lambda to execute even though the stack has been blown. What if this is in the middle of gc? We can't run Lisp code with a heap that is the middle of gc, due to objects being marked and such. That situation is detected and a function called gc_cancel is called to simply cancel gc. Everything that has been marked is unmarked. To bring the gc machine to the most obvious safe state, all the structures related to generational gc are reset, and a full gc is scheduled. With that implemented, the above Rosetta task became reliable; the random failures it exhibited were gone. Users programs (on platforms supporting sigaltstack) have a fighting chance to do something if gc runs out of stack, like save some data to disk or whatever.
quotemstr 9y ago
Why would you bother supporting both approaches? It's not as if the recursive approach is any more efficient --- and whether or not you start with the recursive approach, you need to keep memory reserved for a worst case queue traversal.
- kazinator 9y ago
  For one thing, because the recursive approach is debugged. If we can show that the new code doesn't change what the old code is doing when that case is not triggered, then then we can be confident that a bug hasn't been introduced.

dawg 9y ago

Did sth. similar a while ago for our not so great D GC. https://github.com/dlang/druntime/pull/1073 https://github.com/dlang/druntime/pull/1073

gnufx 9y ago

This talks about possible generational GC. Incremeantal/generational was available many years ago with a port to the Boehm collector. I never understood rejecting it and generally spending effort on a bespoke collector. (I don't remember whether the Ravenbrook system was available at the time, or if it was unsuitable for some reason.)

olliej 9y ago

Super dumb question: why not just use a queue, and visit the objects iteratively? Eg each visited object appends/prepends its children to the queue of objects to visit, and you just repeatedly drain until you have an empty list. That’s what I had to do many years ago for the GC I was working on. Then any special cases (like the cons case referenced elsewhere) just becomes performance optimization rather than “don’t crash” correctness