conservative stack scanning?

[StefanKarpinski]

Instead of maintaining our own GC stack frames – which is slow and easy to mess up, likely accounting for a large portion of our tough-to-track-down core Julia bugs in the past years – we've occasionally talked about doing conservative stack scanning. That is, scanning the stack and conservatively assuming that anything that happens to look like a pointer to a valid heap-allocated Julia object actually is.

Pros:

• much simpler
• faster (RFC: Create local gc frame for throw #11508, Throw exceptions with arguments without creating a GC frame #11284)
• makes stack allocation much easier (WIP: on-stack gc allocation #8134)
• immutables with references trivially become as efficient as reference-free immutables
• fewer segfaults

Cons:

• might retain objects that should be freed
• pointers passed into C code could still expect objects to live but not point to the head of the object
• performance of stack scanning

The second con seems like it can be avoided with the same kind of rooting we do now, except only needed at the ccall entry point. The chances of the first con happening – i.e. random values in the stack pointing valid heap objects – seems pretty slim. There might be situations like when you take a pointer to an array and then use it – but in that case you probably want the array to remain rooted while someone has a pointer to it. Are there other potential cons that I'm not seeing?

Related: #10725, #10317.

cc: @carnaval, @vtjnash, @JeffBezanson

[yuyichao]

The only thing I know about conservative vs precise stack scan is based on this and I quote.

...... Language implementations with automatic memory management often start out using exact rooting. At some point, all the careful rooting code gets to be so painful to maintain that a conservative scanner is introduced. The embedding API gets dramatically simpler, everyone cheers and breathes a sigh of relief, and work moves on (at a quicker pace!)

Sadly, conservative collection has a fatal flaw: GC things cannot move. If something moved, you would need to update all pointers to that thing — but the conservative scanner can only tell you what might be a pointer, not what definitely is a pointer. Your program might be using an integer whose value happens to look like a pointer to a GC thing that is being moved, and updating that “pointer” will corrupt the value. Or you might have a string whose ASCII or UTF8 encoded values happen to look like a pointer, and updating that pointer will rewrite the string into a devastating personal insult.

I know that we are propably even further from compacting but I'd like to know what the experts on these think...

[StefanKarpinski]

Our large amount of C interop makes it fairly unlikely that we'll ever be able to do moving GC.

[JeffBezanson]

It's not clear that we need to move objects. If we did, it would already require a lot of work, since the current rooting API assumes non-moving. That article seems to assume that moving is required for generational GC, but that isn't strictly true. You only need it for compacting or for a copying implementation of generational gc.

For us it's possible the conservative stack scan would be a bigger win than moving objects, especially given how important C interop is.

[carnaval]

To the pros I would add that we would be able to do many optimizations we do for bitstype on immutable types with no additional work. That's huge.

On the moving debate : we will never be able to do a fully relocating collector, because of C interop as Stefan said. However, it would be perfectly ok to do a so called "mostly copying" scheme, and we would need conservative stack scanning (to pin "C" objects) anyway.

The thing I don't agree on is that the chance of something on the stack looking falsely like a pointer is slim. The problem is that the stack is never cleaned up, so as it grows back you can end up overwriting parts (because of padding, alignment) of what was a pointer before. If you overwrite the LSB part you are on the contrary almost guaranteed to point inside a (different) julia object.

On the implementation side, the part taking care of pooled object is already "done" in my PR (which is where I encountered the partial pointer stuff btw). It's the easy one though because they are fixed size. To do this for "big" objects we need a datastructure to query if a pointer falls into a range of memory.

[JeffBezanson]

We can only properly evaluate false retention once we have a full implementation, and measure memory use in real workloads. Until then I'm not worried.

[carnaval]

As we already discussed, I'm not worried too much about the memory usage of false retention, but about the angry "my finalizer was not run after gc()" crowd. Anyway, you're right, we would need to implement big object conservative scanning first to see it in real life.

[JeffBezanson]

Well, you know how I feel about that. The only real solution is to use finalizers less and rely on them less.