Requiring multithreading/concurrency for implementation of scripting language

Question

Here's the deal: I'm looking at designing my own scripting/interpreted language for fun. I'm only in the planning stages right now; I want to make sure I have a very strong hold on exactly how I will implement everything before I start coding.

What I'm currently struggling with is concurrency. It seems to me like an easy way to avoid the unpredictable performance that comes with garbage collection would be to put the garbage collector in its own thread, and have it run concurrently with the interpreter itself. (To be clear, I don't plan to allow the scripts to be multithreaded themselves; I would simply put a garbage collector to work in a different thread than the interpreter.) This doesn't seem to be a common strategy for many popular scripting languages, probably for portability reasons; I would probably write the interpreter in the UNIX/POSIX threading framework initially and then port it to other platforms (Windows, etc.) if need be.

Does anyone have any thoughts in this issue? Would whatever gains I receive by exploiting concurrency be nullified by the portability issues that will inevitably arise? (On that note, am I really correct in my assumption that I would experience great performance gains with a concurrent garbage collector?) Should I move forward with this strategy or step away from it?

Answer 1

writing anything multithreaded is hard

I can think of at least one race condition of the top of my head you'll need to be aware of:

• there is an object A with field foo
• the GC just started its mark phase and has examined field A.foo and is currently examining some other part of the object tree
• meanwhile the interpreter has allocated a new object B and the script assigns it to A.foo and the local variable it was in goes out of scope (deleting any other references to B)
• the GC finishes and won't notice the change to A.foo so B won't be marked alive
• B gets cleaned up and you have a dangling pointer in A.foo

this doesn't need to be allocation (any method of getting to be the sole owner of a yet unmarked B and then assigning to an already examined field will cause trouble)

this can be solved by putting any object handled by the interpreter (not yet marked alive in the sweep) in a to-be-examined list so it gets marked alive during the sweep

so essentially in each object you have a bit field with an "alive" flag and a "handled by interpreter" flag

and on each object the script uses the interpreter will have to do

if(!obj.alive && !obj.alreadyHandled){
     obj.alreadyHandled=true;
     GC.addToQueue(obj);
}

this will delay cleanup for some objects but that is acceptable

I'm sure there are many other things to be aware of (like plain memory visibility effects) that will make things harder and this is probably a large reason why concurrent GCs are rare

Answer 2

am I really correct in my assumption that I would experience great performance gains with a concurrent garbage collector?

I don't think so.

First of all, even if you manage to build a totally cost-free GC, you'd only get "great performance gains" if current in-thread GC's were great performance sinks. Experience in modern GC implementations point otherwise. Some of them are quite light.

Second, by nature, a GC touches lots of memory while other thread(s) are working on it, so you have to be really careful to avoid quite nasty race conditions. Any lock you put there will be significantly contented, making them expensive operations. Even if you manage to use lock-free structures (not for the faint of heart!), tight coupling between the GC thread and the interpreter would make each CAS operation a cache-trashing point.

In my opinion, the extra complexity required for an out-of-thread GC makes them impractical unless you want to go for full multi-threading. In that case, you've already paid most of the contention costs, so dedicating a thread to GC makes sense.

Note that most heavily multithreaded JVM implementations (like Azul's one) do have an out-of-thread GC, but still try to do most management in-thread to avoid the fail-and-retry pattern that lock-free structures are prone to in heavy load.

Answer 3

This is an old question, but in case you are still interested, you might look at Qore, which is an interpreted language with fundamental support for multithreading and also has a unique garbage collection approach (Prompt Collection) which allows for the language to support the RAII idiom (c++-like destructors for resource management and exception-safe programming) even in the case of cyclic directed graphs of objects.

Since you don't (or didn't since the question is old!) plan on making your language multi-threaded, the deterministic graph analysis would be much simpler, because due to its multithreaded nature, the deadlock avoidance and notification aspects of Qore' prompt collection algorithm adds considerable complexity to an already complex challenge.

Then you wouldn't need a separate garbage collection thread and could still implement support for C++-like destructors in your language to support the RAII idiom (if applicable).