knizhnik
Two issues
According to mark_n_sweep_gc.txt, these two are the disadvantages of reference counting. But I could not find the solution to them in mark-and-sweep GC.
- Noticeable performance penalty. Each manipulation with pointers requires update of counter. In case of multithreaded application we have to use atomic operations or synchronization primitives to avoid race conditions.
Atomic operations are only required if one thread allocates an object and passes the reference to another. However, I noticed that the mark-and-sweep MemoryAllocator is thread local, which cannot handle the shared references. If one thread A allocates an object O and passes the reference to another thread B, there are possibility that A does not hold the reference from root to O and deallocate it, while B still holds the reference. In order to handle this, all involed threads must be blocked before GC, and it brings performance penalty. Therefore, high performance GC in multi-thread context is not an easy thing.
- Deleting last reference to huge tree of objects can cause large number of cascade (recursive) deletes which can cause stack overflow.
However, in mark-and-sweep collector, marking last reference to huge tree of objects can cause large number of cascade (recursive) marks which can cause stack overflow. This is easy to solve through manual implemented stack.
I mostly agree with both your arguments. But few comments:
- Quite often thread is not updating shared objects. It just create and delete its own private objects. But it can certainly refer global objects (either through local variable, either from fields of it's private objects). In case of reference counters we have to update shared reference counter. and it doesn't work without synchronization/atomic operations. But in case of mark&sweep we can perform local GC without any synchronization.
- Yes, object graphs should be carefully traversed to avoid stack overflow. Manually implemented stack is one of the possible solutions, but not the perfect one: we are not limited in this case with OS limit for stack size, but still traverse of large collection in "wrong" order can produce huge stack and cause memory exhaustion. Another alternatives is custom traverse method specific for particular collection and bitmaps. Bitmap allows to eliminate problem with too deep recursion, but traversing bitmap may be much more expensive than manipulations with stack. Bitmaps are mostly used for collecting garbage in persistent storages, because in this case locality of object access is most critical.
