Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
Papers We Love #1 - Michael Bernstein on A Uniﬁed Theory of Garbage Collection #1
added a commit
Mar 6, 2014
pushed a commit
Mar 19, 2014
referenced this issue
Nov 13, 2014
In the lecture you say that garbage collection is "batch, no cost per mutation, has long pause times and is not real-time" and reference counting is "incremental, high cost per mutation, short pause times and is real-time".
Incremental tracing algorithms were introduced in the 1970s and real-time concurrent and parallel GCs exist to day so tracing GC is not necessarily batch and does not necessarily have long pause times and can be real-time.
Immediate reference counting has to deallocate an arbitrary DAG of objects as soon as the last root is decremented to zero which incurs an arbitrarily-long pause so it is not incremental, does not necessarily have short pause times and is not real-time. The unbounded-pause-time problem with immediate reference counting is easily fixed by using deferred reference counting.
Another issue I have (with the original paper as well) is the implication that immediate reference counting does not have floating garbage. It does. Garbage can be created halfway through a callee but the decrement to zero will not occur until the caller returns in which case the garbage is floating until the callee returns.
EDIT: Also worth noting that you're assuming malloc and free are real-time.