4 ms·

As someone woefully uninformed about these things, why can't GC be implemented as a separate thread, maybe with a lower priority than the primary interpreter?

As someone woefully uninformed about these things, why can't GC be implemented as a separate thread, maybe with a lower priority than the primary interpreter? Would a separate thread not be able to count references to objects or something?

eternalban 13y ago
One issue is shared mutable state. Typically a GC requires some sort of snapshot of the world state to determine liveness of memory objects.
- riffraff 13y ago
  still, some of the work can be done in parallel I.e. the jvm has had UseConcMarkSweepGC for many many years. EDIT: what I mean is that there is still a need for locks, but a lot of work can be done concurrently.
wingo 13y ago
GC needs to know about all references in the program. If the mutator (the program) is running concurrently with the collector, it's difficult (though not impossible) for the collector to construct this consistent view. Here is a good introductory talk: http://www.infoq.com/presentations/Understanding-Java-Garbage-Collection http://www.infoq.com/presentations/Understanding-Java-Garbag...
judofyr 13y ago
Quoting ko1 (https://bugs.ruby-lang.org/issues/8339#note-11 https://bugs.ruby-lang.org/issues/8339#note-11): > Parallel tracing needs an assumption that "do not move (free) memory > area except sweeping timing". Current CRuby does. > For example: "ary << obj". Yes, the CRuby's memory management strategy > (assumption) is different from normal interpreters.
- m0th87 13y ago
  Isn't memory only shuffled around during compaction? Why not mark/sweep in parallel, then stop-the-world at compaction time?
  - Skinney 13y ago
    In a nutshell, generational GCs works by scanning live data. Thus, anything not scanned is garbage. While the application is running, it also allocates new data. If you allocate an object somewhere --after-- that area has been scanned, the GC will treat that area as garbage, and then you will have memory corruption, leading to segfaults and other nice things. While parallel mark/sweep is certainly doable (Java does this) it's not easy to get right.
- riffraff 13y ago
  notice that refers to parallel (multiple GC threads) but doesn't rule out concurrent (one gc thread concurrent to the application thread)
  - Skinney 13y ago
    Wouldn't two threads possibly run in parallel in a multi-core system? Concurrency, as I understand it, is dividing things into tasks that can run (to some degree) independantly of eachother. Parallelism is two or more concurrent tasks running simultaniously. This if you have one gc thread and one application thread, you have the possibility of them running in parallel.
    - riffraff 13y ago
      yes, they can run in parallel. But in the context of GC (in my understanding) the distinction goes like * concurrent GC is when (some phases of) the garbage collection happen in a separate thread from the main program. * parallel GC is when (some phases of) the collection are performed by multiple threads. So e.g. in a mark&sweep collector you can have a background thread that performs the mark phase concurrently or you can have a parallel collector that uses multiple threads to perform the mark phase. In MRI you can't do the latter but it could be possible to do the former, according to the thread referenced earlier.
mcguire 13y ago
Many styles are implemented that way. Check out Java for (many) examples.[1] Naively, with Ruby's mark-sweep collector[2], you might want to do the sweep phase in parallel, adding garbage blocks to the free list. You could do the mark phase as well, with I believe a pause to make the marks a consistent snapshot. [1] http://www.oracle.com/technetwork/java/javase/tech/g1-intro-jsp-135488.html http://www.oracle.com/technetwork/java/javase/tech/g1-intro-..., for one. [2] http://tmm1.net/ruby21-rgengc/ http://tmm1.net/ruby21-rgengc/

eternalban 13y ago

One issue is shared mutable state. Typically a GC requires some sort of snapshot of the world state to determine liveness of memory objects.

riffraff 13y ago
still, some of the work can be done in parallel I.e. the jvm has had UseConcMarkSweepGC for many many years. EDIT: what I mean is that there is still a need for locks, but a lot of work can be done concurrently.

wingo 13y ago

GC needs to know about all references in the program. If the mutator (the program) is running concurrently with the collector, it's difficult (though not impossible) for the collector to construct this consistent view. Here is a good introductory talk: http://www.infoq.com/presentations/Understanding-Java-Garbage-Collection http://www.infoq.com/presentations/Understanding-Java-Garbag...

judofyr 13y ago

Quoting ko1 (https://bugs.ruby-lang.org/issues/8339#note-11 https://bugs.ruby-lang.org/issues/8339#note-11): > Parallel tracing needs an assumption that "do not move (free) memory > area except sweeping timing". Current CRuby does. > For example: "ary << obj". Yes, the CRuby's memory management strategy > (assumption) is different from normal interpreters.

m0th87 13y ago
Isn't memory only shuffled around during compaction? Why not mark/sweep in parallel, then stop-the-world at compaction time?
- Skinney 13y ago
  In a nutshell, generational GCs works by scanning live data. Thus, anything not scanned is garbage. While the application is running, it also allocates new data. If you allocate an object somewhere --after-- that area has been scanned, the GC will treat that area as garbage, and then you will have memory corruption, leading to segfaults and other nice things. While parallel mark/sweep is certainly doable (Java does this) it's not easy to get right.
riffraff 13y ago
notice that refers to parallel (multiple GC threads) but doesn't rule out concurrent (one gc thread concurrent to the application thread)
- Skinney 13y ago
  Wouldn't two threads possibly run in parallel in a multi-core system? Concurrency, as I understand it, is dividing things into tasks that can run (to some degree) independantly of eachother. Parallelism is two or more concurrent tasks running simultaniously. This if you have one gc thread and one application thread, you have the possibility of them running in parallel.
  - riffraff 13y ago
    yes, they can run in parallel. But in the context of GC (in my understanding) the distinction goes like * concurrent GC is when (some phases of) the garbage collection happen in a separate thread from the main program. * parallel GC is when (some phases of) the collection are performed by multiple threads. So e.g. in a mark&sweep collector you can have a background thread that performs the mark phase concurrently or you can have a parallel collector that uses multiple threads to perform the mark phase. In MRI you can't do the latter but it could be possible to do the former, according to the thread referenced earlier.

mcguire 13y ago

Many styles are implemented that way. Check out Java for (many) examples.[1] Naively, with Ruby's mark-sweep collector[2], you might want to do the sweep phase in parallel, adding garbage blocks to the free list. You could do the mark phase as well, with I believe a pause to make the marks a consistent snapshot. [1] http://www.oracle.com/technetwork/java/javase/tech/g1-intro-jsp-135488.html http://www.oracle.com/technetwork/java/javase/tech/g1-intro-..., for one. [2] http://tmm1.net/ruby21-rgengc/ http://tmm1.net/ruby21-rgengc/