>It must be non-copying, due to various constraints in the Lua/C API.
I don't see this. The Lua GC has to know what's visible from C, in order to avoid freeing those objects. If it knows what's visible from C, then it strictly just needs to avoid copying those objects. If it moves them to an uncollected area when C references them, and back when C dereferences them, then it can use a copying collector on the Lua-only objects.
This actually might work very well, if C-referenced objects are going to tend to be much longer lived. Of course, copying the objects into and out of the uncollected region will itself be some work.
I have no idea if the ideal algorithm is in this space, I just think that either they discarded copying collectors prematurely, or there's something I'm missing, so either I get to learn something or they do; is there a constraint I've missed?
There's no explicit API to pin objects from the C side. Ok, so there's an implicit contract on which pointers to internal VM objects are still valid, once the C side has gotten them (const char *lua_tostring() is the biggest offender). But this contract a) does not lead to a practical implementation and b) is violated by plenty of C modules for Lua, because Lua didn't have a moving GC, so nobody bothered to follow it.
Now ... the interesting objects, that benefit most from the defragmentation effects of a moving GC, are the variable-sized objects. Sadly, userdata cannot be moved at all and strings are the only other interesting object type. Well ... see above.
[Table objects are not variable-size. Only their array and hash parts are. But these are singly-linked from the table object and can easily be moved around, anyway. The addresses of these memory blocks are never exposed by the VM.]
If you had a bit free, you could track which objects escape to C. But it's probably not worth going that way. Well, maybe. Programs that generate tons of strings may only occasionally escape them, so maybe moving them as part of the C call would be a good idea.
I would argue in recent years people have been more aware of the non-guarantee of static pointers in the lua api; and a moving GC would be feasible.
There was talk that the next lua version (after 5.2) would have a moving GC...
I don't see this. The Lua GC has to know what's visible from C, in order to avoid freeing those objects. If it knows what's visible from C, then it strictly just needs to avoid copying those objects. If it moves them to an uncollected area when C references them, and back when C dereferences them, then it can use a copying collector on the Lua-only objects.
This actually might work very well, if C-referenced objects are going to tend to be much longer lived. Of course, copying the objects into and out of the uncollected region will itself be some work.
I have no idea if the ideal algorithm is in this space, I just think that either they discarded copying collectors prematurely, or there's something I'm missing, so either I get to learn something or they do; is there a constraint I've missed?