3 ms·

There is: you either have to use atomic operations on all the reference counters, which is costly, and not available on all platforms, or you can have only one

by foobar2020 12y ago

There is: you either have to use atomic operations on all the reference counters, which is costly, and not available on all platforms, or you can have only one thread active at a time. This is the most classic problem: "x == 0"; parallel execution of "x += 1" and "x += 1"; now "x == 1" or "x == 2". I don't see why tracing collectors need GIL in particular to stop all threads, i.e. why should only one thread be running at a time.

stormbrew 12y ago
I'm not sure why you seem to feel your first paragraph here is a disagreement with what I said. As you point out, there is a well known way to have refcounting act correctly in the face of multiple threads. There are other ways as well involving per-thread shadow counts and such, but that is the most basic way to (as I said) trade throughput for latency. Re. your second paragraph, it is again not inherent to the algorithm, but it does greatly simplify things. In particular, pretty much all tracing algorithms require at least some kind of stop the world event, though some can make this event very limited in duration. It is much much easier (and results in greater throughput) to stop the world if only one thread is running at a time, because you just do your collection when that one thread triggers a heap mutation. If you have multiple threads running at once you need to coordinate when you stop the world, which means waiting for the threads to all wind up in a state where they can be stopped (which gets a lot harder if, say, one of the threads never allocates because it's in a tight loop). If it takes too long to do this coordination, your heap might explode on you. Again, what I'm saying is that a GIL is not an inherent feature of either garbage collection mechanism. This is really pretty obvious when you consider that there's an abundance of implementations of all combinations of (RC, tracing)(GIL, no GIL). Python and Ruby's main implementations both chose a GIL for simplicity's sake (and an at the time safe assumption that single-core performance was more important than multi-core), but most C++ refcounting code uses interlocked counters and the JVM has obviously never used a GIL.

stormbrew 12y ago

I'm not sure why you seem to feel your first paragraph here is a disagreement with what I said. As you point out, there is a well known way to have refcounting act correctly in the face of multiple threads. There are other ways as well involving per-thread shadow counts and such, but that is the most basic way to (as I said) trade throughput for latency. Re. your second paragraph, it is again not inherent to the algorithm, but it does greatly simplify things. In particular, pretty much all tracing algorithms require at least some kind of stop the world event, though some can make this event very limited in duration. It is much much easier (and results in greater throughput) to stop the world if only one thread is running at a time, because you just do your collection when that one thread triggers a heap mutation. If you have multiple threads running at once you need to coordinate when you stop the world, which means waiting for the threads to all wind up in a state where they can be stopped (which gets a lot harder if, say, one of the threads never allocates because it's in a tight loop). If it takes too long to do this coordination, your heap might explode on you. Again, what I'm saying is that a GIL is not an inherent feature of either garbage collection mechanism. This is really pretty obvious when you consider that there's an abundance of implementations of all combinations of (RC, tracing)(GIL, no GIL). Python and Ruby's main implementations both chose a GIL for simplicity's sake (and an at the time safe assumption that single-core performance was more important than multi-core), but most C++ refcounting code uses interlocked counters and the JVM has obviously never used a GIL.